okkjoo-leetcodeHot-byJs带你用 JS 刷高频面试算法题~ 每周一更新~ 合集仓库：okkjoo-leetcodeHot-byJs
如果你已经按题型分类系统地刷了一遍算法面试题的各个题型，想感受一下面试题的”随机性”的话，欢迎一起~

这是第三周的刷题记录与题解分享

上题

200. 岛屿数量|中等|DFS

题目描述

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

解题思路

也就是求连续的“1”块的数量

DFS：

  1. vis 记录该点是否访问过
  2. 每个点递归到上下左右
  3. 递归后记录为访问过
  4. 找完一块 cnt++
  5. 找下一个没访问的
  6. 重复

实际上，访问过的直接将其变为 0 就可以达到一样的效果，还可以省去空间~

  1. /**
  2.  * @param {character[][]} grid
  3.  * @return {number}
  4.  */
  5. var numIslands = function (grid) {
  6.     let cnt = 0;
  7.     const rows = grid.length,
  8.         cols = grid[0]?.length;
  9.     if (rows === 0) return 0;
  10.     for (let i = 0; i < rows; i++) {
  11.         for (let j = 0; j < cols; j++) {
  12.             if (grid[i][j] === "1") {
  13.                 dfs(grid, i, j);
  14.                 cnt++;
  15.             }
  16.         }
  17.     }
  18.     return cnt;
  19. };
  20. const dfs = (grid, i, j) => {
  21.     const rows = grid.length,
  22.         cols = grid[0].length;
  23.     if (i < 0 || j < 0 || i > rows - 1 || j > cols - 1 || grid[i][j] == "0")
  24.         return;
  25.     grid[i][j] = "0";
  26.     const d = [
  27.         [1, 0],
  28.         [0, 1],
  29.         [-1, 0],
  30.         [0, -1],
  31.     ];
  32.     for (let k = 0; k < 4; k++) dfs(grid, i + d[k][0], j + d[k][1]);
  33. };

704. 二分查找|简单|二分

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

解题思路

题目就告诉你了，要 logn 的二分查找~

粗略的二分步骤：

  1. [left, right]
  2. 左右指针，取左右指针中值
  3. 取到的值
    1. 大于 target 就将右指针位移到中值位置 (-1)
    2. 小于就将左指针移到中值位置 (+1)
  4. 直到找到 or 遍历完

代码

  1. /*
  2.  * @lc app=leetcode.cn id=704 lang=javascript
  3.  *
  4.  * [704] 二分查找
  5.  */
  7. // @lc code=start
  8. /**
  9.  * @param {number[]} nums
  10.  * @param {number} target
  11.  * @return {number}
  12.  */
  13. var search = function (nums, target) {
  14.     let left = 0,
  15.         right = nums.length - 1;
  16.     while (left <= right) {
  17.         const mid = Math.floor(right - left) + left / 2;
  18.         const v = nums[mid];
  19.         if (v == target) return mid;
  20.         else if (v > target) right = mid - 1;
  21.         else if (v < target) left = mid + 1;
  22.     }
  23.     return -1;
  24. };
  25. // @lc code=end

21. 合并两个有序链表|简单|递归|链表

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

解题思路

比较两个链表头部的值，谁的小都先放进去，返回一个有序的链表

其实这里真的挺妙的，看起来没有排序的代码，实际上藏在递归之中，每次归都是返回的 其实就是 排序好的了

时间复杂度O(n),空间复杂度O(n)，n 为两个链表长度的合

  1. /**
  2.  * Definition for singly-linked list.
  3.  * function ListNode(val, next) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.next = (next===undefined ? null : next)
  6.  * }
  7.  */
  8. /**
  9.  * @param {ListNode} list1
  10.  * @param {ListNode} list2
  11.  * @return {ListNode}
  12.  */
  13. var mergeTwoLists = function (list1, list2) {
  14.     if (list1 === null) return list2;
  15.     if (list2 === null) return list1;
  16.     if (list1.val < list2.val) {
  17.         list1.next = mergeTwoLists(list1.next, list2);
  18.         return list1;
  19.     } else {
  20.         list2.next = mergeTwoLists(list1, list2.next);
  21.         return list2;
  22.     }
  23. };

300. 最长递增子序列|中等|dp|二分查找

题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

解题思路

  • dp[i]: 包括i 的之前最长递增子序列
  • 状态转移：dp[i] = max(dp[i], dp[j] + 1) (前提：nums[i] > nums[j])
    • j 从 0 到 i -1 各个位置的最长递增子序列长度 最大值 + 1
  • dp[i] 的初始值都为1

每一次都要看看 res 要不要更新

代码

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number}
  4.  */
  5. var lengthOfLIS = function (nums) {
  6.     let dp = Array(nums.length).fill(1);
  7.     let res = 1;
  8.     for (let i = 1; i < nums.length; i++) {
  9.         for (let j = 0; j < i; j++) {
  10.             nums[i] > nums[j] && (dp[i] = Math.max(dp[i], dp[j] + 1));
  11.         }
  12.         res = Math.max(res, dp[i]);
  13.     }
  14.     return res;
  15. };

322. 零钱兑换|中等|动态规划|dp|贪心

题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

解题思路

直接贪心是错误的！

要求最少硬币个数，贪心地想自然就是先拿面值大的硬币，也就是让 amount - cnt 尽量快地变小

cnt 就是当前拿了的全部硬币的值

但是纯贪心的不一定对的，比如[1,6,10]，amount = 12，你从最大开始，就会是一个10，两个1，总共三个硬币。而实际上直接两个6就能达到目标~

暴力枚举

如果是暴力枚举，计算所有组合… 那时间复杂度想当之高~ 这是不值得考虑的

dp

暴力枚举之所以复杂度高，就是因为大部分的情况会重复出现多次，那么我们将重复出现的子问题记录下来即可了。

用 dp 数组将其存储下来，也有叫记忆化递归的，没差

  • 定义：dp[i][j]就是拿前j个硬币来组成金额 i 的最少个数
  • 状态转移：
    • dp[i][j]=min(dp[i][j-1], dp[i - coins[j-1]][j] + 1)
      • 选了也要和之前不选j 就能组成i 的情况比较一下，选j的话就是 ，金额为i-coins[j-1]（也就是还没有选第j个硬币)时 + 1(选j)

时间复杂度O(coins.length*amonut)，空间同上

同时可以发现，dp[i][j]只与dp[i][j - 1]和 dp[i - coins[j]][j] + 1)有关，可以将其优化为一维。

  • dp[i]表示 金额为 i 的时候，需要的最少硬币数
  • 初始化 dp[0]=0
  • 状态转移：
    • 不拿第j个 dp[i]
    • 拿第j个 dp[i - coins[j]] + 1

其实就是完全背包问题

代码

  1. /**
  2.  * @param {number[]} coins
  3.  * @param {number} amount
  4.  * @return {number}
  5.  */
  6. var coinChange = function (coins, amount) {
  7.     if (amount === 0) return 0;
  8.     const dp = Array(amount + 1).fill(Number.MAX_VALUE);
  9.     dp[0] = 0;
  10.     for (let i = 1; i < dp.length; i++) {
  11.         for (let j = 0; j < coins.length; j++) {
  12.             if (i - coins[j] >= 0) {
  13.                 dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
  14.             }
  15.         }
  16.     }
  17.     return dp[dp.length - 1] === Number.MAX_VALUE ? -1 : dp[dp.length - 1];
  18. };

22. 括号生成|中等|回溯|剪枝

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

解题思路

关键词：

  • 所有的
  • 可能的
  • 有效的
  • 组合

一眼回溯

回溯必备的优化手段：剪枝，那么这里应该怎么剪枝？

怎么剪枝

要求括号组合，那么左右两个括号的数量必然相等

  1. 前面出现的左括号小于出现的右括号，比如这样 (())))，绝对是错误的，已经没机会了
  2. 什么情况是有效的：左括号数= 右括号数 = n

代码

  1. /**
  2.  * @param {number} n
  3.  * @return {string[]}
  4.  */
  5. var generateParenthesis = function (n) {
  6.     const res = [];
  7.     //l r s：左右括号个数、当前构造出的字符串
  8.     const dfs = (l, r, s) => {
  9.         if (l == n && r == n) return res.push(s);
  10.         if (l < r) return;
  11.         if (l < n) dfs(l + 1, r, s + "(");
  12.         if (r < l) dfs(l, r + 1, s + ")");
  13.     };
  14.     dfs(0, 0, "");
  15.     return res;
  16. };

54. 螺旋矩阵|矩阵|模拟|数组

题目描述

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

解题思路

就是一圈一圈往里面走，那么就要有四个变量 ：

  • top
  • botton
  • left
  • right

来告诉遍历指针能走到哪里

每走完一圈，left++、top++、right—、bottom—

时间复杂度O(mn)，空间复杂度O(1)

代码

  1. /**
  2.  * @param {number[][]} matrix
  3.  * @return {number[]}
  4.  */
  5. var spiralOrder = function (matrix) {
  6.     if (!matrix.length || !matrix[0].length) return [];
  7.     const rows = matrix.length,
  8.         cols = matrix[0].length;
  9.     const order = [];
  10.     let left = 0,
  11.         right = cols - 1,
  12.         top = 0,
  13.         bottom = rows - 1;
  14.     while (left <= right && top <= bottom) {
  15.         // →
  16.         for (let col = left; col <= right; col++) {
  17.             order.push(matrix[top][col]);
  18.         }
  19.         //↓
  20.         for (let row = top + 1; row <= bottom; row++) {
  21.             order.push(matrix[row][right]);
  22.         }
  23.         if (left < right && top < bottom) {
  24.             //←
  25.             for (let col = right - 1; col > left; col--) {
  26.                 order.push(matrix[bottom][col]);
  27.             }
  28.             //↑
  29.             for (let row = bottom; row > top; row--) {
  30.                 order.push(matrix[row][left]);
  31.             }
  32.         }
  33.         [left, right, top, bottom] = [left + 1, right - 1, top + 1, bottom - 1];
  34.     }
  35.     return order;
  36. };