前言

codetop 前一百题，review and review

3. 无重复字符的最长字串

老题新做

利用 includes api 的特性以及循环弹出顶层的特性，将每个元素 push 进来后下一轮比对是否存在，存在则弹出。

1
2
3
4
5
6
7
8
9
10
11
12
var lengthOfLongestSubstring = function (s) {
  let arr = [];
  let max = 0;
  for (const str of s) {
    while (arr.includes(str)) {
      arr.shift();
    }
    arr.push(str);
    if (max < arr.length) max = arr.length;
  }
  return max;
};

88. 合并两个有序数组

思路：从后往前对比插入，大的数字优先插入末尾。但需要注意的是某一方提前结束的情况发生，此时如果一方提前结束了，终止判断直接用后一方直到后一方数字完全用完(j<0)

1
2
3
4
5
6
7
8
var merge = function (nums1, m, nums2, n) {
  let i = m - 1,
    j = n - 1,
    len = m + n - 1;
  while (j >= 0) {
    nums1[len--] = i >= 0 && nums1[i] >= nums2[j] ? nums1[i--] : nums2[j--];
  }
};

165. 比较版本号

思路是分割.并遍历最长的 length（因为要同时比较），相等跳过，不等判断返回结果。

注意 前导 0 的情况可以用~~或者 parseInt 去解决，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var compareVersion = function (version1, version2) {
  let v1arr = version1.split(".");
  let v2arr = version2.split(".");
  let maxLen = Math.max(v1arr.length, v2arr.length);
  for (let i = 0; i < maxLen; i++) {
    let v1 = v1arr[i] || 0;
    let v2 = v2arr[i] || 0;
    if (v1 === v2) continue;
    if (~~v1 < ~~v2) {
      return -1;
    } else if (~~v1 > ~~v2) {
      return 1;
    }
  }
  return 0;
};

415. 字符串相加

思路：从后往前累加到一个数组内，因为是字符串要转数字使用+ 最后从数组还原使用join('')
小技巧，从后往前读可以使用新的 api Array.at(-1) 注意余数和进位数字的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var addStrings = function (num1, num2) {
  let last = -1;
  let maxLen = Math.max(num1.length, num2.length);
  let newAdd = 0;
  let res = [];
  while (maxLen--) {
    let c1 = num1.at(last) ? +num1.at(last) : 0;
    let c2 = num2.at(last) ? +num2.at(last) : 0;
    let count = c1 + c2 + newAdd;
    res.unshift((count % 10) + "");
    newAdd = Math.floor(count / 10);
    last--;
  }
  if (newAdd > 0) {
    res.unshift("1");
  }
  return res.join("");
};

20. 有效的括号

思路：设置匹配规则，遍历的 s 的时候如果元素满足左括号就把规则中的右括号 push 进数组，如果元素是右括号，说明此时弹出的括号要和右括号匹配 否则返回 false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var isValid = function (s) {
  const rule = {
    "(": ")",
    "[": "]",
    "{": "}",
  };
  let arr = [];
  for (const str of s) {
    if (str === "(" || str === "[" || str === "{") {
      arr.push(rule[str]);
    } else {
      if (arr.pop() !== str) {
        return false;
      }
    }
  }
  return !arr.length;
};

1. 两数之和

code

1
2
3
4
5
6
7
8
9
10
var twoSum = function (nums, target) {
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (map.has(nums[i])) {
      let less = map.get(nums[i]);
      return [less, i];
    }
    map.set(target - nums[i], i);
  }
};

46. 全排列

入门回溯，使用 used 记录已经使用过的元素，终止条件是 path 长度等于数组长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var permute = function (nums) {
  const res = [];
  const used = new Array(nums.length).fill(false);
  const dfs = (path) => {
    if (path.length === nums.length) {
      res.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      path.push(nums[i]);
      used[i] = true;
      dfs(path);
      path.pop();
      used[i] = false;
    }
  };
  dfs([]);
  return res;
};

112. 路径总和

dfs 注意第一次进去的是 root 的 val

1
2
3
4
5
6
7
8
9
10
11
12
13
var hasPathSum = function (root, targetSum) {
  if (!root) return false;
  let res = false;
  const dfs = (n, sum) => {
    if (!n.left && !n.right && sum === targetSum) {
      res = true;
    }
    if (n.left) dfs(n.left, sum + n.left.val);
    if (n.right) dfs(n.right, sum + n.right.val);
  };
  dfs(root, root.val);
  return res;
};

二叉树的层序遍历

时刻牢记：层序遍历有两层循环，外层退出条件是队列为空，因为队列为空了，意味着已经走到最后一步结束了。内层循环是为了让孩子进队列并弹出队头元素，弹出有两个目的，一是清空当前队列，二是保留当前队头元素；让孩子进队列是为了下一次层序。

容易犯错的点：退出当前循环的条件是队列为空,且因为弹出会影响数组长度，所以要保存数组长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var levelOrder = function (root) {
  if (!root) return [];
  const res = [];
  const queue = [root];
  while (queue.length) {
    const len = queue.length;
    const temp = [];
    for (let i = 0; i < len; i++) {
      const n = queue.shift();
      temp.push(n.val);
      if (n.left) queue.push(n.left);
      if (n.right) queue.push(n.right);
    }
    res.push(temp);
  }
  return res;
};

70. 爬楼梯

斐波那契:思路，把每个问题分割成子问题，去逐步处理子问题。

1
2
3
4
5
6
7
8
9
const fun = (n) => {
  const fn = [];
  fn[1] = 1;
  fn[2] = 2;
  for (let i = 3; i <= n; i++) {
    fn[i] = fn[i - 1] + fn[i - 2];
  }
  return fn[n];
};

53. 最大子数组和

思路：比较每次的和和当前项的关系，大的替换。因为我们每次只需要保留两数之间的最大值，然后有个流程上面的最大值，用于比较每次的最大值，找到最大的最大值返回

1
2
3
4
5
6
7
8
9
const fn = (nums) => {
  let sum = nums[0];
  let max = nums[0];
  for (let i = 1; i < nums.length; i++) {
    sum = Math.max(nums[i], sum + nums[i]);
    max = Math.max(sum, max);
  }
  return max;
};

15. 三数之和

三指针，注意满足条件就剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const fn = (nums) => {
  nums = nums.sort((a, b) => a - b);
  let res = [];
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) continue;
    let mid = i + 1;
    let last = nums.length - 1;
    while (mid < last) {
      let sum = nums[i] + nums[mid] + nums[last];
      if (sum === 0) {
        res.push([nums[i], nums[mid], nums[last]]);
        mid++;
        while (nums[mid] === nums[mid - 1]) {
          mid++;
        }
      } else if (sum < 0) {
        mid++;
      } else {
        last--;
      }
    }
  }
  return res;
};

206.反转链表

反转链表的流程其实就是

稍微理解一下这个图就可以了。并且注意最后 cur 已经走完，但是 pre 构建完了。

1
2
3
4
5
6
7
8
const fn = (head){
  let cur = head;
  let pre = null;
  while(cur){
    [cur.next,pre,cur] = [pre,cur,cur.next]
  }
  return pre;
}

141.环形链表

快指针每次都比慢指针多走一步，如果有环，必定会重合

1
2
3
4
5
6
7
8
9
10
11
12
const fn = (head) => {
  let slow = head;
  let fast = head;
  while (slow && fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (slow === fast) {
      return true;
    }
  }
  return false;
};

121. 买卖股票的最佳时机

基本思路是，使用后一次和前一次做差加初始的值进行判断，如果持续收益大于 0 说明本次是正收益，保留，否则置为 0.最后比较得到 max

注意 因为是比较前后，最后一位要省去

1
2
3
4
5
6
7
8
9
const fn = (prices) => {
  let last = 0;
  let max = 0;
  for (let i = 0; i < prices.length - 1; i++) {
    last = Math.max(0, last + prices[i + 1] - prices[i]);
    max = Math.max(max, last);
  }
  return max;
};

215. 数组中的第 K 个最大元素

1
const fn = (nums, k) => {};

5. 最长回文子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const fn = (s) => {
  let len = s.length;
  let dp = new Array(len);
  let res = s[0];
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(len).fill(false);
  }
  for (let i = len - 1; i >= 0; i--) {
    for (let j = i; j < len; j++) {
      if (s.charAt(i) !== s.charAt(j)) continue;
      dp[i][j] = j - i <= 2 || dp[i + 1][j - 1];
      if (dp[i][j] && j - i + 1 > res.length) {
        res = s.slice(i, j + 1);
      }
    }
  }
  return res;
};

912. 排序数组

手撕快速排序

1
2
3
4
const quickSort = (nums) => {
  let left = [];
  let right = [];
};

129. 根到叶子节点数字之和

code dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const fn = (root) => {
  let res = 0;
  const dfs = (n, sum) => {
    if (!n) return;
    if (!n.left && !n.right) {
      res += +[...sum].join("");
    }
    if (n.left) {
      sum.push(n.left.val);
      dfs(n.left, sum);
      sum.pop();
    }
    if (n.right) {
      sum.push(n.right.val);
      dfs(n.right, sum);
      sum.pop();
    }
  };
  dfs(root, [root.val]);
  return res;
};

200. 岛屿数量

思路：
dfs 判断是否处于二位平面，且是否为 1，满足条件沉没陆地，判断下个格子并 dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const fn = (grid) => {
  if (!grid) return 0;
  let xLen = grid[0].length;
  let yLen = grid.length;
  let count = 0;
  const d = [
    [1, 0],
    [0, 1],
    [-1, 0],
    [0, -1],
  ];
  const inArea = (x, y) => {
    return x >= 0 && x < yLen && y >= 0 && y <= xLen;
  };
  const dfs = (i, j, grid) => {
    grid[i][j] = "0";
    for (let k = 0; k < 4; k++) {
      let x = i + d[k][0];
      let y = j + d[k][1];
      inArea(x, y) && grid[x][y] === "1" && dfs(x, y, grid);
    }
    return;
  };
  for (let i = 0; i < yLen; i++) {
    for (let j = 0; j < xLen; j++) {
      if (grid[i][j] === "1") {
        count++;
        dfs(i, j, grid);
      }
    }
  }
  return count;
};

704. 二分查找

300. 最长上升子序列

21. 合并两个有序链表

22. 括号生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const fn = (n) => {
  const res = [];
  // 技巧 变量都要带进递归
  const dfs = (l, r, path) => {
    if (path.length === 2 * n) {
      res.push([...path].join(""));
    }
    if (l > 0) {
      path.push("(");
      dfs(l - 1, r, path);
      path.pop();
    }
    // 注意是左括号的数量小于右括号才能让右括号进栈
    if (l < r) {
      path.push(")");
      dfs(l, r - 1, path);
      path.pop();
    }
  };
  dfs(n, n, []);
  return res;
};

104. 二叉树的最大深度

注意条件!n 和 !n.right&&!n.left的不同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var maxDepth = function (root) {
  if (!root) return 0;
  let max = 1;
  const dfs = (n, depth) => {
    if (!n) {
      return;
    }
    if (!n.left && !n.right) {
      max = Math.max(depth, max);
    }
    if (n.left) dfs(n.left, depth + 1);
    if (n.right) dfs(n.right, depth + 1);
  };
  dfs(root, 1);
  return max;
};

322. 零钱兑换

分解问题再合并问题
求 1 就是求 0 的次数和求 1 的次数的最小值比较
求 2 其实就是求 1 的次数和求 2 的次数的最小值比较
因此推到出状态转移方程为：
dp[i] = Math.min(dp[i],dp[i-coin]+1)

1
2
3
4
5
6
7
8
9
10
11
const fn = (coins, amount) => {
  const dp = new Array(amount + 1).fill(Infinity); //考虑0
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (coin > i) continue; //如果当前硬币值大于当前所求额度则不能组合 跳过
      dp[i] = Math.min(dp[i], dp[i - coin] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
};

54. 螺旋矩阵

走四个方向为一次 dfs，如果中间没有 length 就直接返回。

走右边相当于 i 为 0 的情况，就直接把整个数组开头 shift 然后解构过来

走下面相当于 i 大于 0 且小于数组长度的情况，就一直获取前面每个子数组里面 pop 的内容，(因为第一个被 shift 了 长度-1)

走左边相当于 i 为最后一个的时候，直接把数组最后的元素 pop 然后反转

注意这个过程中，如果只走了一圈 比如
左右下 xxx 左上 xxx 右的情况 出现了很多空子数组，但整个数组还是有长度的

就会 push 很多 undefined 进去，要阻止他，就得使用if (arr[i] && !arr[i].length) return; //防止只走一圈就结束的情况

接着我们要完成往上的操作，往上的操作相当于倒着读取数组，然后把子数组的最前面一项拿出来

注意这个过程也需要判断子数组是否为空

最后没结束就继续递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const fn = (matrix) => {
  const res = [];
  const dfs = (arr) => {
    let len = arr.length; //保存length
    for (let i = 0; i < len; i++) {
      if (!arr.length) return;
      if (arr[i] && !arr[i].length) return; //防止只走一圈就结束的情况
      if (i === 0) {
        res.push(...arr.shift());
      } else if (i === len - 1) {
        res.push(...arr.pop().reverse());
      } else {
        res.push(arr[i - 1].pop());
      }
    }
    for (let i = arr.length - 1; i >= 0; i--) {
      if (!arr[i].length) return;
      res.push(arr[i].shift());
    }
    if (!arr.length) return;
    dfs(arr);
  };
  dfs(matrix);
  return res;
};

94. 二叉树的中序遍历

code

1
2
3
4
5
6
7
8
9
10
11
12
var inorderTraversal = function (root) {
  if (!root) return [];
  const res = [];
  const dfs = (n) => {
    if (!n) return;
    dfs(n.left);
    res.push(n.val);
    dfs(n.right);
  };
  dfs(root);
  return res;
};

146. LRU 缓存机制

剑指 Offer 22. 链表中倒数第 k 个节点

注意使用 dummy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var getKthFromEnd = function (head, k) {
  let dummy = new ListNode();
  dummy.next = head;
  let slow = dummy;
  let fast = dummy;
  while (k--) {
    fast = fast.next;
  }
  while (fast.next) {
    slow = slow.next;
    fast = fast.next;
  }
  return slow.next;
};

42. 接雨水

剑指 Offer 10- I. 斐波那契数列

code

1
2
3
4
5
6
7
const fn = (n) => {
  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
  }
  return dp[n];
};

695. 岛屿的最大面积

在求岛屿数量的基础上增加个 count 和 max 即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
var maxAreaOfIsland = function (grid) {
  let max = 0;
  let count = 0;
  const xLen = grid[0].length;
  const yLen = grid.length;
  const d = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];
  const inArea = (x, y) => {
    return x >= 0 && x < yLen && y >= 0 && y < xLen;
  };
  const dfs = (i, j, grid) => {
    grid[i][j] = 0;
    count++;
    for (let k = 0; k < 4; k++) {
      const x = i + d[k][0];
      const y = j + d[k][1];
      inArea(x, y) && grid[x][y] && dfs(x, y, grid);
    }
    return;
  };
  for (let i = 0; i < yLen; i++) {
    for (let j = 0; j < xLen; j++) {
      if (grid[i][j] === 1) {
        dfs(i, j, grid);
        max = Math.max(max, count);
        count = 0;
      }
    }
  }
  return max;
};

103. 二叉树的锯齿型层序遍历

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var zigzagLevelOrder = function (root) {
  if (!root) return [];
  const q = [root];
  const res = [];
  let isTran = false;
  while (q.length) {
    const temp = [];
    const len = q.length;
    for (let i = 0; i < len; i++) {
      const n = q.shift();
      temp.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    if (!isTran) {
      res.push(temp);
    } else {
      res.push(temp.reverse());
    }
    isTran = !isTran;
  }
  return res;
};

209. 长度最小的子数组

因为是正整数数组，所以每次都是递增的
使用滑动窗口
当右指针移动扩大窗口的时候，判断是否满足 target，如果满足则右指针减左指针得到窗口长度和当前的最小长度比较。然后左指针移动，缩小窗口。

1
2
3
4
5
6
7
8
9
10
11
12
const fn = (target, nums) => {
  let l = (r = sum = 0);
  let res = Infinity;
  while (r < nums.length) {
    sum += nums[r++]; //扩大窗口
    while (sum >= target) {
      res = Math.min(res, r - l); //r-l代表满足条件的窗口长度
      sum -= nums[l++];
    }
  }
  return res === Infinity ? 0 : res;
};