用 javascript 分类刷 leetcode24. 其他类型题 (图文视频讲解)

作者：js2030code

2023-01-03
浙江
本文字数：7842 字
阅读完需：约 26 分钟

73. 矩阵置零（ medium）

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]输出：[[1,0,1],[0,0,0],[1,0,1]]示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
提示：
m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231 <= matrix[i][j] <= 231 - 1
进阶：
一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。你能想出一个仅使用常量空间的解决方案吗？

思路:用两个变量标记第一行和第一列是否有 0，接着循环一遍矩阵，如果遇见 0，将和这个网格相同的第一行和第一列的元素标记成 0，在循环矩阵，如果当前网格对应的第一行和第一列是 0，则将这个单元格置为 0。最后如果第一列有 0 ，则将这第一列全部置为 0,如果第一行有 0 ，则将这第一行全部置为 0
复杂度：时间复杂度O(mn)，m、n 为矩阵的行和列。空间复杂度O(1)

js:

var setZeroes = function(matrix) {    const m = matrix.length, n = matrix[0].length;    let flagCol0 = false, flagRow0 = false;//表示第一行和第一列有没有0    for (let i = 0; i < m; i++) {//寻找第一列是否存在0        if (matrix[i][0] === 0) {            flagCol0 = true;        }    }    for (let j = 0; j < n; j++) {        if (matrix[0][j] === 0) {            flagRow0 = true;        }    }    for (let i = 1; i < m; i++) {//循环矩阵，如果遇见0，将和这个网格相同的第一行和第一列的元素标记成0        for (let j = 1; j < n; j++) {            if (matrix[i][j] === 0) {                matrix[i][0] = matrix[0][j] = 0;            }        }    }    for (let i = 1; i < m; i++) {//循环矩阵，如果当前网格对应的第一行和第一列是0，则将这个单元格置为0        for (let j = 1; j < n; j++) {            if (matrix[i][0] === 0 || matrix[0][j] === 0) {                matrix[i][j] = 0;            }        }    }    if (flagCol0) {//如果第一列有0 ，则将这第一列全部置为0        for (let i = 0; i < m; i++) {            matrix[i][0] = 0;        }    }    if (flagRow0) {//如果第一行有0 ，则将这第一行全部置为0        for (let j = 0; j < n; j++) {            matrix[0][j] = 0;        }    }};

复制代码

133. 克隆图（medium）

给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。
图中的每个节点都包含它的值 val（int）和其邻居的列表（list[Node]）。
class Node { public int val; public Listneighbors;}
测试用例格式：
简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。
邻接列表是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
给定节点将始终是图中的第一个节点（值为 1）。你必须将给定节点的拷贝作为对克隆图的引用返回。

示例 1：

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]输出：[[2,4],[1,3],[2,4],[1,3]]解释：图中有 4 个节点。节点 1 的值是 1，它有两个邻居：节点 2 和 4 。节点 2 的值是 2，它有两个邻居：节点 1 和 3 。节点 3 的值是 3，它有两个邻居：节点 2 和 4 。节点 4 的值是 4，它有两个邻居：节点 1 和 3 。示例 2：

输入：adjList = [[]]输出：[[]]解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。示例 3：
输入：adjList = []输出：[]解释：这个图是空的，它不含任何节点。示例 4：

输入：adjList = [[2],[1]]输出：[[2],[1]]
提示：
节点数不超过 100 。每个节点值 Node.val 都是唯一的，1 <= Node.val <= 100。无向图是一个简单图，这意味着图中没有重复的边，也没有自环。由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。图是连通图，你可以从给定节点访问到所有节点。

方法 1:dfs

思路：深度优先遍历，递归新建每个节点和相邻节点的关系
复杂度：时间复杂度O(n)，n 表示节点的数量。空间复杂度O(n)，递归的深度

js：

var cloneGraph = function(node) {    if(!node) return;    const visited = new Map();//存放遍历过的节点    const dfs = (n) => {        const nCopy = new Node(n.val);//拷贝节点        visited.set(n, nCopy);//节点值和新建节点以键值对存入visited        (n.neighbors || []).forEach(ne => {            if(!visited.has(ne)) {                dfs(ne);//递归遍历相邻节点            }            nCopy.neighbors.push(visited.get(ne));//复制相邻节点        })    }    dfs(node);//深度优先遍历    return visited.get(node);//返回visited中的新创建的节点};

复制代码

方法 1:bfs

思路：广度优先遍历每个节点，复制节点和节点间的关系
复杂度：时间复杂度O(n)，n 表示节点的数量。空间复杂度O(n)，队列的空间

js：

var cloneGraph = function(node) {    if(!node) return;    const visited = new Map();    visited.set(node, new Node(node.val));//节点值和新建节点以键值对存入visited    const q = [node];    while(q.length) {        const n = q.shift()//出队        (n.neighbors || []).forEach(ne => {//循环相邻节点            if(!visited.has(ne)) {//没有访问过就加入队列                q.push(ne);                visited.set(ne, new Node(ne.val));            }            visited.get(n).neighbors.push(visited.get(ne));//复制相邻节点        })    }    return visited.get(node);};

复制代码

54. 螺旋矩阵（medium）

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

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5]示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100

思路：模拟旋转的顺序
复杂度：时间复杂度O(mn)，空间复杂度O(1)

js：

var spiralOrder = function (matrix) {    if (matrix.length == 0) return []    const res = []    let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1    while (top <= bottom && left <= right) {//循环条件        for (let i = left; i <= right; i++) res.push(matrix[top][i])//循环完上面一行 top++        top++        for (let i = top; i <= bottom; i++) res.push(matrix[i][right])//循环右边一行 right--        right--        if (top > bottom || left > right) break        for (let i = right; i >= left; i--) res.push(matrix[bottom][i])        bottom--        for (let i = bottom; i >= top; i--) res.push(matrix[i][left])        left++    }    return res};

复制代码

48. 旋转图像（medium）

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[[7,4,1],[8,5,2],[9,6,3]]示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
提示：
n == matrix.length == matrix[i].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000

思路：先沿水平中轴线翻转，然后在沿主对角线翻转.
复杂度：时间复杂度O(n^2)，空间复杂度O(1)

js：

var rotate = function(matrix) {    const n = matrix.length;    //水平中轴线翻转    for (let i = 0; i < Math.floor(n / 2); i++) {        for (let j = 0; j < n; j++) {            [matrix[i][j], matrix[n - i - 1][j]] = [matrix[n - i - 1][j], matrix[i][j]];        }    }    //主对角线翻转    for (let i = 0; i < n; i++) {        for (let j = 0; j < i; j++) {            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];        }    }};

复制代码

836. 矩形重叠（easy）

矩形以列表 [x1, y1, x2, y2] 的形式表示，其中 (x1, y1) 为左下角的坐标，(x2, y2) 是右上角的坐标。矩形的上下边平行于 x 轴，左右边平行于 y 轴。
如果相交的面积为正，则称两矩形重叠。需要明确的是，只在角或边接触的两个矩形不构成重叠。
给出两个矩形 rec1 和 rec2 。如果它们重叠，返回 true；否则，返回 false 。

示例 1：
输入：rec1 = [0,0,2,2], rec2 = [1,1,3,3]输出：true 示例 2：
输入：rec1 = [0,0,1,1], rec2 = [1,0,2,1]输出：false 示例 3：
输入：rec1 = [0,0,1,1], rec2 = [2,2,3,3]输出：false
提示：
rect1.length == 4rect2.length == 4-109 <= rec1[i], rec2[i] <= 109rec1 和 rec2 表示一个面积不为零的有效矩形

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

js：

var isRectangleOverlap = function(rec1, rec2) {    const [x1, y1, x2, y2] = rec1;    const [x3, y3, x4, y4] = rec2;    return !(x1 >= x4 || x3 >= x2 || y3 >= y2 || y1 >= y4);};

复制代码

89. 格雷编码（medium）

n 位格雷码序列是一个由 2n 个整数组成的序列，其中：每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）第一个整数是 0 一个整数在序列中出现不超过一次每对相邻整数的二进制表示恰好一位不同，且第一个和最后一个整数的二进制表示恰好一位不同给你一个整数 n ，返回任一有效的 n 位格雷码序列。

示例 1：
输入：n = 2 输出：[0,1,3,2]解释：[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
00 和 01 有一位不同
01 和 11 有一位不同
11 和 10 有一位不同
10 和 00 有一位不同[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
00 和 10 有一位不同
10 和 11 有一位不同
11 和 01 有一位不同
01 和 00 有一位不同示例 2：
输入：n = 1 输出：[0,1]
提示：
1 <= n <= 16

思路：变量 pre 初始为 1，不断左移，ans 存放结果，每次循环之前数，在前面加上 pre
复杂度：时间复杂度O(n^2)。空间复杂度O(1)

js：

var grayCode = function(n) {    let ans = [0];    let pre = 1;    for(let i = 0;i<n;i++){        for(let j = ans.length - 1;j>=0;j--){            ans.push(pre + ans[j]);        }        pre <<= 1;    }    return ans;};

复制代码

66. 加一（easy)

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：
输入：digits = [1,2,3]输出：[1,2,4]解释：输入数组表示数字 123。示例 2：
输入：digits = [4,3,2,1]输出：[4,3,2,2]解释：输入数组表示数字 4321。示例 3：
输入：digits = [0]输出：[1]
提示：
1 <= digits.length <= 1000 <= digits[i] <= 9

思路：如果digits[i] %= 10不为 0，则直接返回 digits，循环过程中没有 reutrn 掉说明一直进位到最大位置。
复杂度：时间复杂度O(n)，空间复杂度O(1)

js：

//例子：12，19， 99var plusOne = function(digits) {    const len = digits.length;    for(let i = len - 1; i >= 0; i--) {        digits[i]++;        digits[i] %= 10;//求余10，覆盖当前位置        if(digits[i]!=0)//没有进位就直接返回这个数            return digits;    }    digits = [...Array(len + 1)].map(_=>0);//循环没有return掉 处理一直进位到最大位置      //[1,0,0]    digits[0] = 1;    return digits;};

复制代码

65. 有效数字（hard）

有效数字（按顺序）可以分成以下几个部分：
一个小数或者整数（可选）一个 'e' 或 'E' ，后面跟着一个整数小数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（'+' 或 '-'）下述格式之一：至少一位数字，后面跟着一个点 '.'至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字一个点 '.' ，后面跟着至少一位数字整数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（'+' 或 '-'）至少一位数字部分有效数字列举如下：["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]
部分无效数字列举如下：["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]
给你一个字符串 s ，如果 s 是一个有效数字，请返回 true 。

示例 1：
输入：s = "0"输出：true 示例 2：
输入：s = "e"输出：false 示例 3：
输入：s = "."输出：false
提示：
1 <= s.length <= 20s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。

图是网络结构的抽象模型，是一组由边连接的节点

图可以辨识任何二元关系比如路、航班

图的表示方法

邻接矩阵
邻接表

思路:有限状态机，遍历字符串，不断转换状态，看最后的状态是是否是有效状态
复杂度：时间复杂度O(n)，n 是字符串的长度，遍历 n 次，每次状态转移是O(1)。空间复杂度O(1)

js：

//1.2   2e10//--6   2evar isNumber = function (s) {    const graph = {        0: { 'black': 0, 'sign': 1, '.': 2, 'digit': 6 },        1: { 'digit': 6, '.': 2 },        2: { 'digit': 3 },        3: { 'digit': 3, 'e': 4, "E": 4 },        4: { 'digit': 5, 'sign': 7 },        5: { 'digit': 5 },        6: { 'digit': 6, '.': 3, 'e': 4, "E": 4 },        7: { 'digit': 5 }    };
    let state = 0;//初始状态
    for (let c of s.trim()) {//循环字符串        if (c >= '0' && c <= '9') {            c = 'digit';        } else if (c === ' ') {            c = 'blank';        } else if (c === '+' || c === '-') {            c = 'sign'        }
        state = graph[state][c];//返回下一个状态
        if (state === undefined) {//状态转移之后不在临接表中 返回false            return false;        }
    }
    if (state == 3 || state == 5 || state == 6) {//状态是3、5、6中的一个说明是有效数字        return true;    }
    return false;};

复制代码

417. 太平洋大西洋水流问题（ medium）

有一个 m × n 的矩形岛屿，与太平洋和大西洋相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格高于海平面的高度。
岛上雨水较多，如果相邻单元格的高度小于或等于当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回网格坐标 result 的 2D 列表，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动既可流向太平洋也可流向大西洋。

示例 1：

输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]示例 2：
输入: heights = [[2,1],[1,2]]输出: [[0,0],[0,1],[1,0],[1,1]]
提示：
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 105

思路：准备两个表示是否能流向某个海岸线的矩阵，沿着海岸线‘’逆流而上‘’，最后统计两个大洋都能流向的坐标
复杂度：时间复杂度O(m*n),m、n 分别是坐标矩阵的长宽。空间复杂度O(m * n)

太平洋 ~   ~   ~   ~   ~        ~  1   2   2   3  (5) *       ~  3   2   3  (4) (4) *       ~  2   4  (5)  3   1  *       ~ (6) (7)  1   4   5  *       ~ (5)  1   1   2   4  *          *   *   *   *   * 大西洋

复制代码

js：

var pacificAtlantic = function(matrix) {    if(!matrix || !matrix[0]) { return []; }    const m = matrix.length;    const n = matrix[0].length;      //从太平洋或大西洋逆流而上是否能到达某个坐标的数组 ture表示能流向某一个大洋    const flow1 = Array.from({ length: m }, () => new Array(n).fill(false));    const flow2 = Array.from({ length: m }, () => new Array(n).fill(false));
    const dfs = (r, c, flow) => {        flow[r][c] = true;        [[r-1, c], [r+1, c], [r, c-1], [r, c+1]].forEach(([nr, nc]) => {            if(                //防止越界                nr >= 0 && nr < m &&                nc >= 0 && nc < n &&                //只有未标记的坐标才能继续递归 防止死循环                !flow[nr][nc] &&                //确保是逆流而上                matrix[nr][nc] >= matrix[r][c]            ) {                dfs(nr, nc, flow)            }        })    }    //逆流而上    for(let r = 0; r<m; r+=1) {        dfs(r, 0, flow1);        dfs(r, n-1, flow2)    }    for(let c = 0; c <n; c += 1) {        dfs(0, c, flow1);        dfs(m-1, c, flow2)    }    //统计两个大洋都能流向的坐标    const res = []    for(let r = 0; r < m; r += 1) {        for(let c = 0; c < n; c += 1) {            if(flow1[r][c] && flow2[r][c]) {                res.push([r, c])            }        }    }    return res;};

复制代码

41. 缺失的第一个正数（hard）

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0]输出：3 示例 2：
输入：nums = [3,4,-1,1]输出：2 示例 3：
输入：nums = [7,8,9,11,12]输出：1
提示：
1 <= nums.length <= 5 * 105-231 <= nums[i] <= 231 - 1

思路:循环 nums，当前元素在(0,nums.lenght]之间，并且nums[nums[i]-1] != nums[i]，则交换位置，然后循环交换位置之后的数组，判断第一个缺失的正数
复杂度：时间复杂度O(n)，空间复杂度O(1)

js：

var firstMissingPositive = function(nums) {    for(let i = 0; i < nums.length; i++){          //循环nums，当前元素在(0,nums.lenght]之间，并且nums[nums[i]-1] != nums[i]，则交换位置        while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i]-1] != nums[i] ){            const temp = nums[nums[i]-1];            nums[nums[i]-1] = nums[i];            nums[i] = temp;        }    }    for(let i = 0; i < nums.length; i++){//循环交换位置之后的数组，判断第一个缺失的正数        if(nums[i] != i+1){            return i+1;        }    }        // [1,2,3]    return nums.length + 1;
};

复制代码

视频讲解：传送门

发布于: 刚刚阅读数: 5

js2030code

关注

还未添加个人签名 2022-09-14 加入

还未添加个人简介

发布

暂无评论

创作场景

用 javascript 分类刷 leetcode24. 其他类型题 (图文视频讲解)

73. 矩阵置零（ medium）

133. 克隆图 （medium）

方法 1:dfs

方法 1:bfs

54. 螺旋矩阵 （medium）

48. 旋转图像 （medium）

836. 矩形重叠 （easy）

89. 格雷编码 （medium）

66. 加一 （easy)

65. 有效数字 （hard）

417. 太平洋大西洋水流问题（ medium）

41. 缺失的第一个正数 （hard）

js2030code

评论

133. 克隆图（medium）

54. 螺旋矩阵（medium）

48. 旋转图像（medium）

836. 矩形重叠（easy）

89. 格雷编码（medium）

66. 加一（easy)

65. 有效数字（hard）

41. 缺失的第一个正数（hard）