典型算法题汇总

链表

合并两个有序链表

类似拉拉链，维护一个指针，与当前链表的头指针不断比较

var mergeTwoLists = function (list1, list2) {
  //虚拟链表头
  const dummy = { next: null };
  let p = dummy;
  while (list1 && list2) {
    if (list1.val > list2.val) {
      p.next = list2;
      list2 = list2.next;
    } else {
      p.next = list1;
      list1 = list1.next;
    }
    p = p.next;
  }
  // 多余列表，默认增序的，直接接上
  if (list1) {
    p.next = list1;
  }
  if (list2) {
    p.next = list2;
  }
  return dummy.next;
};

合并 k 个有序链表

用最小堆优先队列，js 没有这种东西，得自己写一个（java 自带了一个，羡慕 😂）

二叉最大/小堆优先队列，通过数组的下标来与二叉树节点建立来联系设队列为queue=[]，二叉树根节点从下标 1开始（从 0 的话相乘就还是 0 了），左子树对应下标则为 1*2=2，右子树 1*2+1=3，左子树的左子树 1*2*2=4 …以此类推，对于每一个节点，设其下标为i，则可知道它的父节点下为Math.floor(i/2)，左子点下标i*2，右子节点i*2+1

var mergeKLists = function (lists) {
  // 过滤空链表，测试用例十分操蛋
  lists = lists.filter((l) => !!l);
  if (!lists.length) return null;

  // Class实现二叉最小堆优先队列
  class MinPQ {
    constructor(array = []) {
      this.array = [undefined, ...array];
    }
    // 上浮操作
    swim(idx) {
      while (
        idx > 1 &&
        this.array[this.parent(idx)].val > this.array[idx].val
      ) {
        this.exch(this.parent(idx), idx);
        idx = this.parent(idx);
      }
    }
    // 下沉
    sink(idx) {
      const size = this.array.length;
      while (this.left(idx) < size) {
        // 先假设左边节点较小
        let less = this.left(idx);
        // 如果右边节点存在，比一下大小
        if (
          this.right(idx) < size &&
          this.array[this.right(idx)].val < this.array[this.left(idx)].val
        )
          less = this.right(idx);
        // 结点 idx 比俩孩子都小，就不必下沉了
        if (this.array[idx].val <= this.array[less].val) break;
        // 否则，不符合最小堆的结构，下沉 idx 结点
        this.exch(idx, less);
        idx = less;
      }
    }
    // pop出最小值，同时更新队列
    popMin() {
      if (this.array.length === 2) {
        return this.array.pop();
      }
      const min = this.array[1];
      this.array[1] = this.array.pop();
      this.sink(1);
      return min;
    }
    // 插入节点
    insert(node) {
      this.array.push(node);
      this.swim(this.array.length - 1);
    }
    // 交换节点
    exch(idx1, idx2) {
      const idx2Val = this.array[idx2];
      this.array[idx2] = this.array[idx1];
      this.array[idx1] = idx2Val;
    }
    // 下标查询
    parent(idx) {
      return Math.floor(idx / 2);
    }
    left(idx) {
      return idx * 2;
    }
    right(idx) {
      return idx * 2 + 1;
    }
  }

  // 各列表头节点入队
  const pq = new MinPQ(lists.sort((a, b) => a.val - b.val));

  const dummy = { next: null };
  let p = dummy;

  // 依次从优先队列取出最小的，放到结果链表里
  while (pq.array.length > 1) {
    const min = pq.popMin();
    p.next = min;
    p = p.next;
    // 如果取出的节点还有后续，则入队
    if (min?.next) {
      pq.insert(min.next);
    }
  }

  return dummy.next;
};

删除链表的倒数第 N 个结点

快慢指针，快的比慢的先走 N 步

var removeNthFromEnd = function (head, n) {
  const dummy = { next: head };
  let point = dummy;
  let lastNPoint = dummy;

  while (n >= 0) {
    n--;
    point = point.next;
  }

  while (point) {
    lastNPoint = lastNPoint.next;
    point = point.next;
  }

  lastNPoint.next = lastNPoint.next.next;

  return dummy.next;
};

链表的中间节点

快慢指针，快的每走两步，慢的走一步，快指针到终点时，满指针刚好在中点

var middleNode = function (head) {
  let fast = head;
  let slow = head;

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

  return slow;
};

判断链表是否有环

快慢指针（快两倍），当快指针没有下一个节点时，没有环，两指针相遇时，有环

var hasCycle = function (head) {
  let fast = head;
  let slow = head;
  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (slow === fast) {
      return true;
    }
  }
  return false;
};

判断环形列表的起点

快慢指针，两指针相遇时将任一指针放回起点，然后已相同速度前进，再次相遇的节点则为环起点

var detectCycle = function (head) {
  if (!head?.next) return null;

  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast === slow) {
      break;
    }
  }

  if (!fast?.next) return null;

  fast = head;

  while (fast !== slow) {
    fast = fast.next;
    slow = slow.next;
  }

  return fast;
};

两个链表是否相交

双指针遍历两个链表（同速度），假设两个链表相交长度为 z，不相交的长度为 x 和 y，两个指针同时走，如果两个指针都在走完自己的时候走另一条，那么两指针必定在相交点相遇，应为此时两指针走的距离相等x+z+y=y+z+x

var getIntersectionNode = function (headA, headB) {
  let pA = headA;
  let pB = headB;
  while (pA !== pB) {
    if (pA === null) {
      pA = headB;
    } else {
      pA = pA.next;
    }
    if (pB === null) {
      pB = headA;
    } else {
      pB = pB.next;
    }
  }
  return pA;
};

反转单链表

普通做法，做一个新链表，不断的包上父节点

var reverseList = function (head) {
  let res = null;
  let p = head;
  while (p) {
    res = {
      val: p.val,
      next: res,
    };
    p = p.next;
  }
  return res;
};

递归实现，dp 问题返回的是反转后的头节点，在父问题中这个头节点则需要作为最后一个节点

var reverseList = function (head) {
  if (!head?.next) {
    return head;
  }
  const last = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return last;
};

反转列表的一部分

将链表先砍成三段，反转中间那段，再重新拼接

var reverseBetween = function (head, left, right) {
  //反转整条
  const reverse = (head) => {
    if (!head?.next) {
      return head;
    }
    const last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
  };
  // 截取之前的
  let prepend = { next: head };
  while (left > 1) {
    prepend = prepend.next;
    left--;
    right--;
  }
  // 截取需要反转的那段
  let needReverse = prepend.next;
  let p = needReverse;
  while (right > 1) {
    p = p.next;
    right--;
  }
  let append = p.next;
  // 临时砍掉
  p.next = null;
  // 反转
  const reversedHead = reverse(needReverse);
  // 拼接
  prepend.next.next = append;
  prepend.next = reversedHead;
  return prepend.val ? head : prepend.next;
};

K 个一组反转链表

更上面类似，分段反转，注意拼接问题

判断回文链表

类似二叉树后续遍历，对链表进行遍历，前后续分别维护一个指针，达到两端对比的效果

var isPalindrome = function (head) {
  // 倒序对比
  let left = head;
  let right;
  let res = true;
  const deep = (node) => {
    // 前序遍历，从有段开始
    if (!node.next) {
      right = node;
      return;
    }
    deep(node.next);
    // 后续遍历，从左端开始
    res = res && left.val === right.val;
    left = left.next;
    right = node;
  };

  deep(head);
  return res;
};

也可以东通过快慢指针找到中间节点，然后反转后半段链表，再依次进行比较

// TODO

数组

删除有序数组中的重复项

注意题目中是需要原地操作数组的，使用快慢指针即可，慢指针维护不重复项，快指针正常遍历

var removeDuplicates = function (nums) {
  let slow = 0;
  let fast = 1;
  const length = nums.length;
  while (fast < length) {
    // 当快指针与慢指针不同时，慢指针挪一步，将快指针的值赋给它
    if (nums[slow] !== nums[fast]) {
      slow++;
      nums[slow] = nums[fast];
    }
    fast++;
  }
  nums.length = slow + 1;
};

删除排序链表中的重复元素

和上面这个一样的道理，编程了操作节点而已

var deleteDuplicates = function (head) {
  if (!head || !head.next) return head;
  let slow = head;
  let fast = head.next;
  while (fast) {
    if (fast.val !== slow.val) {
      slow.next = fast;
      slow = slow.next;
    }
    fast = fast.next;
  }
  slow.next = null;
  return head;
};

移除元素

也是需要原地操作数组，使用快慢指针，慢指针维护当前不需要删除的元素，快指针正常遍历，遇到不需要删除的，将值赋给慢指针，随后慢指针挪一步，遇到需要删除的则跳过

var removeElement = function (nums, val) {
  let slow = 0;
  let fast = 0;
  while (fast < nums.length) {
    if (nums[fast] !== val) {
      nums[slow] = nums[fast];
      slow++;
    }
    fast++;
  }
  return slow;
};

移动零

需要原地操作，使用快慢指针，慢指针维护非零值，快指针正常遍历，遇到了非零的值则与慢指针交换，然后慢指针挪一步

var moveZeroes = function (nums) {
  let slow = 0;
  let fast = 0;
  const length = nums.length;
  while (fast < length) {
    if (nums[fast] !== 0) {
      const slowVal = nums[slow];
      nums[slow] = nums[fast];
      nums[fast] = slowVal;
      slow++;
    }
    fast++;
  }
};

两数之和 II

因为数组是递增的，可以使用左右指针不断调整

var twoSum = function (numbers, target) {
  let left = 0;
  let right = numbers.length - 1;
  while (left < right) {
    if (numbers[left] + numbers[right] === target) {
      return [left + 1, right + 1];
    } else if (numbers[left] + numbers[right] > target) {
      right--;
    } else {
      left++;
    }
  }
};

反转字符串

左右指针向中间靠拢，交换两端值

var reverseString = function (s) {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    const rightV = s[right];
    s[right] = s[left];
    s[left] = rightV;
    left++;
    right--;
  }
  return s;
};

最长回文子串

通过从中心向两端扩散的双指针判断是否回文，需要注意的是回文字串的中心可能是一个字符，也可能是两个字符

var longestPalindrome = function (s) {
  // 找以某一点为中心的最长回文字串
  const findPalidrom = (s, l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      l--;
      r++;
    }
    return s.slice(l + 1, r);
  };
  let res = "";
  for (let i = 0; i < s.length; i++) {
    const s1 = findPalidrom(s, i, i);
    const s2 = findPalidrom(s, i, i + 1);
    if (s1.length > res.length) res = s1;
    if (s2.length > res.length) res = s2;
  }
  return res;
};

区域和检索 - 数组不可变

使用前缀和绩效，维护每个点的前缀和，区间的和只需要求起点和终点的前缀和差值即可

var NumArray = function (nums) {
  const sums = [0];

  for (const i of nums) {
    const last = sums.slice(-1)[0];
    sums.push(last + i);
  }

  this.sums = sums;
};

NumArray.prototype.sumRange = function (left, right) {
  return this.sums[right + 1] - this.sums[left];
};

二维区域和检索 - 矩阵不可变

也是使用前缀和技巧，不同的是，矩阵中的区域差值计算

var NumMatrix = function (matrix) {
  const colNum = matrix[0].length;
  const rowNum = matrix.length;
  if (rowNum === 0 || colNum === 0) return;
  const preSum = [new Array(colNum + 1).fill(0)];
  for (let i = 1; i <= rowNum; i++) {
    if (!preSum[i]) preSum[i] = [0];
    for (let j = 1; j <= colNum; j++) {
      // 计算每个矩阵 [0, 0, i, j] 的元素和
      preSum[i][j] =
        preSum[i - 1][j] +
        preSum[i][j - 1] +
        matrix[i - 1][j - 1] -
        preSum[i - 1][j - 1];
    }
  }
  this.sums = preSum;
};

// 相当于计算面积
// ┍ ┬ ┐
// │a│b│
// ┝ ┾ ┤
// │c│d│
// ┕ ┶ ┘
// 由r1*c1=a,r1*c2=a+b,r2*c1=a+c,r2*c2=a+b+c+d
// 得d=r2c2-r1c2-r2c1+r1c1
NumMatrix.prototype.sumRegion = function (r1, c1, r2, c2) {
  return (
    this.sums[r2 + 1][c2 + 1] -
    this.sums[r1][c2 + 1] -
    this.sums[r2 + 1][c1] +
    this.sums[r1][c1]
  );
};

二叉树

动态规划

动态规划基本条件：符合最优子结构，问题相互独立基本步骤：确定base case->确定状态->确定选择->明确dp函数/数组的定义状态指的是原问题和子问题会变化的量，选择指的是能使状态发生变化的行为

斐波那契数

正常的递归会有很多字问题重复求解，可以用备忘录优化，但最优解法使用 dp 状态转移

var fib = function (n) {
  if (n < 2) return n;
  // 维护两个状态就够了，不需要用状态数组，节省空间
  let dp_1 = 0,
    dp_2 = 1;
  for (let i = 2; i <= n; i++) {
    const newDp = dp_1 + dp_2;
    dp_1 = dp_2;
    dp_2 = newDp;
  }
  return dp_2;
};

零钱兑换

var coinChange = function(coins, amount) {
    // 备忘录，cache[amount]记录该金额下的最少零钱数
    const cache = []
}

链表

数组

二叉树

动态规划

待续…