牛客 & 力扣 | Colommar Blog

原稿：语雀 · 牛客 & 力扣 · 原目录：算法 › 牛客 & 力扣

链表

NC2 重排链表

假设4个结点，0312=》012+3；8个结点，07162534=》01234+567；5个结点04132=》012+34，由上述规律，我们可以使用双指针找到链表中点，则slow.next为后半链表的开头 2. 双指针找链表中点

slow.next即指向右子链表首元素，应该断开和左链表连接 2. 对后半段链表进行逆序（见NC78 反转列表） 4. 交叉插入

当head和after中有一个已经指向null时即合并完成

function reorderList( head ) {
    if(!head) return;
    // 1.双指针找中点
    // [0,slow][slow+1,n-1]
    // n为偶数时前一半多2个结点，奇数时多1个
    let fast = head, slow = head;
    while(fast && fast.next){
        fast = fast.next.next;
        slow = slow.next;
    }
    // 需要slow.next = null，否则左侧链表最后一个节点发生循环引用
    let curr = slow.next;
    slow.next = null;

    // 2.逆序
    let prev, next;
    while(curr){
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    // 3.合并
    let after = prev;
    let leftNext, rightNext;
    while(head && after){
        leftNext = head.next;
        head.next = after;
        head = leftNext;
        rightNext = after.next;
        after.next = head;
        after = rightNext;
    }
}

NC3 链表中环的入口节点

使用快慢指针，当fast再次遇到slow说明有环，问题是如何确定环的入口结点？

当在环上Z点相遇，slow走了a + b，fast走了a + n ( b + c ) + b，此时指针走了a+b步，则fast累计应该比slow多走a+b，可得关系式：2 ( a + b ) = a + b + n ( b + c )，解得a = ( n − 1 ) ( b + c ) + c，即a的长度一定等于(n-1)个完整的环补一个c的距离。

因此当快慢指针相遇后，两指针中一个回到head，一个留在Z，以相同的速度再次相遇的结点一定是环的入口

function detectCycle( head ) {
    let fast = head, slow = head;
    while(fast && fast.next){
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast){
            slow = head;
            while(slow !== fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

NC21 指定区间反转

思路不难，关注m-1、m、m+1、n+1这几个位置，但实现中的一些指针指向很容易搞错

function reverseBetween( head ,  m ,  n ) {
    if(!head) return head;

    let dummy = new ListNode(-1);
    dummy.next = head;

    let prev = dummy, curr = head;
    for(let i=1;i<m;i++){
        prev = curr;
        curr = curr.next;
    }
    let mm = curr, m_left = prev;
    // m->n有m-n段，循环m-n次
    let next;
    for(let i=0;i<=n-m;i++){
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    // 结束时next即n+1节点
    mm.next = next;
    m_left.next = prev;

    return dummy.next;
}

NC24 删除有序链表中重复出现的元素

本题涉及到删除，设置一个dummy head会极大方便删除
注意特殊情况已经循环的继续条件
每次while结束时

当本次while遇到重复元素时，curr最后指向第一个和前面不同的元素或null
当本次while遇到非重复元素，curr最后指向下一元素或null

循环结束后curr指向的元素一定和之前的元素不重复（不保证之后），也可以说curr指向元素之前的所有元素一定都是没有重复的元素

function deleteDuplicates( head ) {
    if(!head || !head.next) return head;

    let dummy = new ListNode(-1);
    dummy.next = head;

    let prev = dummy, curr = head;
    // curr=True保证了{1，1}情形，curr.next保证了if中可访问curr.next.val
    while(curr && curr.next){
        // 出现重复情况
        if(curr.val === curr.next.val){
            while(curr.next && curr.val === curr.next.val){
                curr = curr.next;
                // 前移后curr.next可能指向null，因此循环需判断
            }
            // 循环结束时，curr.next是第一个和前面不同的元素或null
            prev.next = curr.next;
            curr = curr.next;
        }else{
            // 暂无重复情况
            prev = curr;
            curr = curr.next;
        }
    }

    return dummy.next;
}

NC25 删除有序链表中重复的元素

与24略微区别，24题凡是重复的元素一个都不留，25题对于重复元素，留下一个

function deleteDuplicates( head ) {
    if(!head || !head.next) return head;


    let prev=head, curr=head;
    while(curr && curr.next){
        if(curr.val == curr.next.val){
            prev = curr;
            while(curr.next && curr.val == curr.next.val)
                curr = curr.next;
            prev.next = curr.next;
            curr = curr.next;
        }else{
            prev = curr;
            curr = curr.next;
        }
    }
    return head;
}

NC40 两链表相加生成链表

我最开始想先计算，读出937，63，然后相加得到1000，再把1000拆成链表，实际非常麻烦

这里采用链表更简单： 2. 两链表逆序，依次从个位开始相加，考虑进位情况 4. 当head1，head2都指向null，且无carry时说明相加完成 6. 对生成链表逆序

function addInList( head1 ,  head2 ) {
    head1 = reverse(head1);
    head2 = reverse(head2);

    let head = new ListNode(-1), curr = head;
    let sum=0,carry=0;

    while(head1 || head2 || carry){
        sum = 0;
        if(head1) {
            sum += head1.val;
            head1 = head1.next;
        }
        if(head2) {
            sum += head2.val;
            head2 = head2.next;
        }
        sum += carry;
        carry = sum > 9? 1:0;
        sum -= carry*10;
        curr.next = new ListNode(sum);
        curr = curr.next;
    }

    return reverse(head.next);
}

function reverse(head){
    if(!head) return;
    let prev, next, curr = head;
    while(curr){
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

NC51 合并K个已排序链表

可使用递归归并、堆排序、优先队列等算法。

因为js没有现成堆数据结构，这里使用递归，当数组有K个元素，共n个节点，递归深度logK，每层都需要访问n个节点，复杂度是nlogK

function mergeKLists( lists ) {
    if(!lists.length) return;
    return mergeHelper(lists,0,lists.length-1);
}

function mergeHelper(lists, m, n){
    if(m==n) return lists[m];

    let mid = ((n-m)>>1)+m;
    let p1 = mergeHelper(lists, m ,mid);
    let p2 = mergeHelper(lists,mid+1,n);

    if(!p1) return p2;
    if(!p2) return p1;

    let curr, head;
    if(p1.val < p2.val){
        curr = p1;
        p1 = p1.next;
    }else{
        curr = p2;
        p2 = p2.next;
    }
    head = curr;

    while(p1 || p2){
        if(!p1){
            curr.next = p2;
            return head;
        }else if(!p2){
            curr.next = p1;
            return head;
        }else if(p1.val < p2.val){
            curr.next = p1;
            p1 = p1.next;
            curr = curr.next;

NC53 删除链表的倒数第n个节点

NC69 链表中倒数第k个结点

两题可对比，53需要删除，69只需找出，但69给出的索引不一定是有效值

主要思路：让快指针先走k步，之后快慢一起走，当快指针抵达链表尾部，则慢指针恰好指向倒数第n个节点

如图所示，k+m = m+n=》k=n，则slow剩下的n步就是k

代码见下，需注意本题的n保证有效，当n恰好等于节点数是，说明删除正数第一个节点，可直接返回head.next

// 53：写法一，不设置空头节点
function removeNthFromEnd( head ,  n ) {
    if(!head) return;
    let fast = head, slow = head;
    for(let i=0; i<n; i++){
        fast = fast.next;
        // n有效，最多等于结点数,直接返回head.next
        if(!fast) return head.next;
    }

    let prev;
    while(fast){
        prev = slow;
        slow = slow.next;
        fast = fast.next;
    }
    // 最终slow即待删除节点
    // 如果第8行不判断fast是否已经为null，这里相当于head.next = head.next,未删除头节点
    prev.next = slow.next;
    return head;
}

// 53：写法二，设置dummy后，可以不判断fast是否已经为null
function removeNthFromEnd( head ,  n ) {
    if(!head) return;
    let slow = head, fast = head;
    let dummy = new ListNode(-1);
    dummy.next = head;

    for(let i=0;i<n;i++){
        fast = fast.next;
    }

    let prev = dummy;
    while(fast){
        prev = slow;
        slow = slow.next;
        fast = fast.next;
    }
    prev.next = slow.next;
    return dummy.next;
}

// 69
function FindKthToTail(head, k)
{
    if(!head) return;
    let fast = head, slow = head;
    for(let i=0;i<k;i++){
        fast = fast.next;
         // 本题k不一定有效,当n个结点时
        // k=n时，返回head
        if(!fast && i === k-1) return head;
        // k>n时，返回null
        if(!fast) return null;
    }
    while(fast){
        slow = slow.next;
        fast = fast.next;
    }

NC96 判断一个链表是否为回文结构

思路，快慢指针找中点，逆序后半段，依次比较

function isPail( head ) {
//     实际无需判断，当只有一个节点，最终head和prev指向相同，返回true
//     if(!head.next) return true;

    let slow = head, fast = head;
    while(fast && fast.next){
        slow = slow.next;
        fast = fast.next.next;
    }

    let prev,next,curr = slow;
    while(curr){
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    while(prev){
        if(head.val !== prev.val)
            return false;
        head = head.next;
        prev = prev.next;
    }
    return true;
}

小结快慢指针：

当n是奇数时：快指针到末尾后，slow指向⌈ 2 n ⌉处节点，即后半链表起始，则后半链表比前一半多1节点
当n是偶数时：快指针到末尾后，slow指向⌈ 2 n ⌉处节点，前后链表结点数相同

eg：结点数为5，快指针到末尾后，slow指向节点3，链表分为【1 2】【3 4 5】

数组

NC36 两个等长正序数组的上中位数

数组长度都为n，则中位数是第n大的数字，两个数组元素不断比较，直到索引和等于n-1，则index1于index2所指元素的较小者为上中位数

function merge( A, m, B, n ) {
    let temp = [];
    for(let i=0; i<m; i++){
        temp[i] = A[i];
    }
    for(let curr = m+n-1, i1 = m-1, i2 = n-1; curr>=0 ;curr--){
        if(i1 == -1 || A[i1] < B[i2])  A[curr] = B[i2--];
        else if(i2 == -1) return A;
        // A[i1] >=  B[i2]
        else A[curr] = A[i1--];
    }

    return A;
}

LC4 寻找两个正序数组的中位数

把问题转化为找第k小元素，二分查找，复杂度O(log(m+n))

var findMedianSortedArrays = function(nums1, nums2) {
    const getKthElement = (k) => {
        let index1=0, index2=0;

        while(true){
            // 当nums1被查找彻底，剩余k-1个偏小元素即nums[index2]-nums[index2+k-2]
            // 最终第k大元素即nums2[index2+k-1]
            if(index1 == m) return nums2[index2 + k-1];
            if(index2 == n) return nums1[index1 + k-1];
            if(k == 1) return Math.min(nums1[index1], nums2[index2]);

            let mid = (k>>1) - 1;
            let tempIndex1 = Math.min(index1+mid, m-1),
                tempIndex2 = Math.min(index2+mid, n-1);
            let pivot1 = nums1[tempIndex1],
                pivot2 = nums2[tempIndex2];
            if(pivot1 < pivot2){
                // 实际可排除：nums1[index]-nums1[tempIndex1]
                // 实际排除个数：tempIndex1-index1+1
                // 剩余待找出个数：k-(tempIndex1-index1+1)
                k -= tempIndex1 - index1 + 1;
                // 更新下轮查找的起点
                index1 = tempIndex1+1;
            }else{
                k -= tempIndex2 - index2 + 1;
                index2 = tempIndex2+1;
            }
        }
    }

    let m = nums1.length, n = nums2.length, total = m+n;
    if(total%2) return getKthElement(((total>>1)+1));
    else return (getKthElement((total>>1)) + getKthElement((total>>1)+1))/2;
};

NC61 两数之和

经典，使用map，但是以元素值作为key，数组索引作为value

function twoSum( numbers ,  target ) {
    let hashMap = new Map();
    let len = numbers.length;
    for(let i=0;i<len;i++){
        if(hashMap.has(target-numbers[i]))
            return [hashMap.get(target-numbers[i]), i+1];
        // 数组值作为key，i+1作为value
        hashMap.set(numbers[i],i+1);
    }
}

NC95 数组中的最长连续子序列

即LC 128，两种思路

排序+滑动窗口：先排序，通过滑动窗口操作不断右移找到最长连续子序列，处理对重复值的处理，下方代码中每次遇到重复值之后使得 l++ ，等价于不重复计算

var longestConsecutive = function(nums) {
    if(nums.length <=1 ) return nums.length;
    nums = nums.sort((a, b)=>{
        return a-b;
        });

    let ans = 0;
    let r,l;
    for(l=0, r=1;r<nums.length;r++){
        if(nums[r] != nums[r-1]+1){
            if(nums[r] == nums[r-1]) l++;
            else{
                ans = Math.max(ans, r-l);
                l = r;
            }
        }
    }

    return Math.max(ans, r-l);
};

哈希集合：把所有元素放入set中，之后遍历数组，若当前元素是一个连续序列的起点时，在哈希集中递增查找序列截至处；若当前元素不是连续序列的起点，跳过即可，因为它总会被计入一个连续序列

function MLS( arr ) {
    let len = arr.length, ans = 0;
    let hashSet = new Set(arr);
    for(let i=0, count=0;i<len;i++){
        // arr[i]不存在左邻居,作为起点
        if(!hashSet.has(arr[i]-1)){
            let curr = arr[i];
            count=1;
            // 不断搜索右邻居
            while(hashSet.has(curr+1)){
                curr++;
                count++;
            }
            ans = Math.max(ans, count);
        }
        // 若有左邻居，直接跳过,因为一定存在序列计入当前节点
    }
    return ans;
}

NC97 出现次数TopK

使用哈希map，注意因为要求对于次数相同的字符按照字典序排列，而map会保留插入的顺序，这样根据次数排序时不一定会保证字典序，因此需要在放入map前对字符数组按字典序排序

function topKstrings( strings ,  k ) {
    strings.sort();
    let map = new Map();
    let ans = [];
    for(let item of strings){
        if(!map.has(item)) map.set(item,1);
        else map.set(item, map.get(item)+1);
    }

    map.forEach((val, key) => {
        ans.push([key, val])
    })

     ans.sort((sec, fir) => {
        return fir[1] - sec[1]
    })
    return ans.slice(0, k);
}

NC110 旋转数组

解法简单巧妙，逆序三次，比如执行6,2,

1,2,3,4,5,6

整体逆序： $6 5 4 3 2 1$
前m个元素逆序： $5 6$ $4 3 2 1$
后n-m个元素逆序： $5 6$ $1 2 3 4$

注意，当m>=n时需要m = m%n

function solve( n ,  m ,  a ) {
    const reverse = (start, end, a) =>{
        while(start < end){
            let temp = a[start];
            a[start] = a[end];
            a[end] = temp;
            start++, end--;
        }
    }

    m = m%n;
    reverse(0, n-1, a);
    reverse(0, m-1, a);
    reverse(m, n-1, a);
    return a;
}

字符串

NC1 大数加法

主要注意两个carry不同，因此s

m - i - 1

不能使用 num1 + num2 + carry - carry * 10 + "" 计算

function solve(s, t) {
  s = s.split("");
  t = t.split("");
  // 保证s为较长数组
  if (s.length < t.length) [s, t] = [t, s];
  let m = s.length,
    n = t.length;

  let carry = 0;
  for (let i = 0; i < m; i++) {
    let num1 = i < m ? s[m - i - 1] * 1 : 0;
    let num2 = i < n ? t[n - i - 1] * 1 : 0;
    let sum = num1 + num2 + carry; // 上一个carry
    carry = Math.floor(sum / 10);
    s[m - i - 1] = sum - carry * 10 + "";// 下一位carry
  }
  return carry ? carry + s.join("") : s.join("");
}

NC17 最长回文子串

吐槽下这题牛客没有提供JS答题区，在力扣上找到基本一样的题：5. 最长回文子串，只是需要返回子串本身。这里采用动态规划的方法，本质上就是填状态矩阵dp[][]主对角线上半部分，当S

i...j

是一个回文串，则dp

i

j

填true，而S

i...j

是否是回文串取决于两点：①S

i+1...j-1

是否是回文串 ②S

i

==S

j

是否成立，即状态转移方程是P(i,j)=P(i+1,j−1)∧(Si==Sj)

i和j之间距由d控制：

当d==0，即为dp主对角线上元素，即每个字符本身，单字符是回文串，都填true
当d==1，即为两个相邻字符，直接通过比较S $i$ 和S $j$ 判断
当d>1，需要通过P(i,j)=P(i+1,j−1)∧(Si==Sj)判断，在矩阵上，dp $i+1$ $j-1$ 位于dp $i$ $j$ 左下角，在下方的代码中可以得到填写顺序是平行于主对角线向下，则dp $i+1$ $j-1$ 一定先于dp $i$ $j$ 获悉

👉实际填写顺序：

d=0：(0,0)(1,1)(2,2)(3,3)(4,4)

d=1：(0,1)(1,2)(2,3)(3,4)

d=2：(0,2)(1,3)(2,4)

d=3：(0,3)(1,4)

d=4：(0,4)

var longestPalindrome = function (s) {
  let len = s.length;
  let ans = "";

  // 二维数组初始化
  let dp = Array.from(new Array(len), () => {
    return new Array(len).fill(0);
  });

  // d:s[i]-s[j]距离
  for (let d = 0; d < len; d++) {
    for (let i = 0; i + d < len; i++) {
      let j = i + d;

      if (i == j) dp[i][j] = true;
      else if (j == i + 1) dp[i][j] = s[i] == s[j] ? true : false;
      else dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j] ? true : false;

      // 当s[i...j]是回文串，比较其长度d+1和当前最长回文串长度
      if (dp[i][j] && d + 1 > ans.length) ans = s.substring(i, j + 1);
    }
  }

  return ans;
};

NC41 找到字符串的最长无重复字符子串

采用滑动窗口（双指针法）： 2. 固定窗口左边界，右侧开始依次比较并加入窗口 4. 当遇到一个重复元素，当前窗口已有元素构成该左边界下最长的无重复子串 6. 之后左边界右移一个位置，不会影响窗口已有元素的非重复性，右边界开始继续搜索

function maxLength( arr ) {
    let len = arr.length
    if(!len) return 0;
    let ans = 0;

    let hashSet = new Set();
    hashSet.add(arr[0]);

    for(let l=0,r=1; l<len;l++){
        // 右指针不断右移，直到结尾或遇到重复字符
        while(r<len && !hashSet.has(arr[r])) {
            hashSet.add(arr[r]);
            r++;
        }
        // 更新当前最长无重复子串的长度
        ans = Math.max(ans, r-l);
        // 左指针右移一个，从set中移除
        hashSet.delete(arr[l]);
    }

    return ans;
}

NC92 最长公共子序列

动态规划，见LC1143的题解，填表的大概思路，力扣的题目是要求返回长度，牛客返回字符串

function LCS( s1 ,  s2 ) {
    if(!s1 || !s2) return -1;

    let m = s1.length, n = s2.length;
    let dp = Array.from(new Array(m+1), ()=>new Array(n+1).fill(''));
    for(let i=1; i<m+1; i++){
        for(let j=1; j<n+1; j++){
            if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1]+s1[i-1];
            else dp[i][j] = dp[i-1][j].length > dp[i][j-1].length ? dp[i-1][j]:dp[i][j-1];
        }
    }
    return dp[m][n] == ''?-1:dp[m][n];
}

NC103 反转字符串

三种思路 2. 调用api：split()-reverse()-join() 4. 逆序复制：迭代n次，时间复杂度O(n)，空间复杂度O(n) 6. 双指针：交换n/2次，时间复杂度O(n)，空间复杂度O(1)

function solve( str ) {
//  方法1：调用API
//  return str.split('').reverse().join('');

//  方法2：逆序复制
//     let ret = [];
//     for(let i=str.length-1; i>=0;i--){
//         ret += str[i];
//     }
//     return ret;

//  方法3：双指针（原地交换）:需要str转数组
    str = Array.from(str);
    for(let l=0, r=str.length-1 ; l<r;){
        [str[l++], str[r--]] = [str[r], str[l]];
    }
    return str.join('');
}

树

二叉树前中后序

实现二叉树三种顺序遍历的思路基本如下，以下方法难度各不相同，我自己感觉难度如下

顺序	实现难度	面试记哪种？	力扣题目
前序	递归 < BFS == 莫里斯	递归+BFS	144. 二叉树的前序遍历
中序	递归 < 莫里斯 < DFS	递归+DFS or 递归+莫里斯	94. 二叉树的中序遍历
后续	递归 < BFS < DFS < 莫里斯	递归+BFS	145. 二叉树的后序遍历

以leetcode题目为准，每种遍历给出两种简单写法（其余的写法在力扣都找到的）

前序

两种方法的复杂度：T : O ( n ) S : O ( l o g n ) ∼ O ( n )

无论使用哪种方法都需要遍历n个结点，因此时间开销都为O(n)，空间则却决于递归(隐式栈)/显式栈的深度，这取决于二叉树平衡性，当退化为链表时空间开销O(n)

// 递归
var preorderTraversal = function(root) {
    let ans =[];
    const recursion = (root) => {
        if (!root) return;

        ans.push(root.val);
        if(root.left) recursion(root.left);
        if(root.right) recursion(root.right);
    }

    recursion(root);
    return ans;
};

// BFS
var preorderTraversal = function(root) {
    if(!root) return [];

    let stk = [root], ans =[];
    while(stk.length){
        let curr = stk.pop();
        // 正序
        ans.push(curr.val);
        if(curr.right) stk.push(curr.right);
        if(curr.left) stk.push(curr.left);
    }
    return ans;
};

中序

链表#

数组#

字符串#

树#

二叉树前中后序#

链表

数组

字符串

树

二叉树前中后序