跳到主要内容

22 篇博文 含有标签「矩阵」

查看所有标签

· 阅读需 3 分钟

1、题干​

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

  • 只能从架子的左上角开始拿珠宝
  • 每次可以移动到右侧或下侧的相邻位置
  • 到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

 

示例 1:

输入: frame = [[1,3,1],[1,5,1],[4,2,1]]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝

 

提示：

  • 0 < frame.length <= 200
  • 0 < frame[0].length <= 200

 

2、解法1-动态规划​

循环遍历矩阵，累加礼物价值

状态转移方程：dp[i][j]+=max(dp[i−1][j],dp[i][j−1])dp[i][j] += max(dp[i-1][j], dp[i][j-1])


3、代码​

function maxValue(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            grid[i][j] += Math.max(i > 0 ? grid[i - 1][j] : 0, j > 0 ? grid[i][j - 1] : 0);
        }
    }
    return grid[m - 1][n - 1];
};

4、执行结果​

image.png


5、解法2-记忆化DFS​

DFS遍历矩阵，累加礼物价值

记录每个节点的最大价值作为缓存避免重复计算


6、代码​

function maxValue(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const visited = grid.map(row => row.map(() => 0));
    function dfs(i: number, j: number) {
        if (i < 0 || j < 0 || i >= m || j >= n) return 0;
        if (!visited[i][j]) visited[i][j] = grid[i][j] + Math.max(dfs(i - 1, j), dfs(i, j - 1));
        return visited[i][j];
    }
    return dfs(m - 1, n - 1);
};

7、执行结果​

  • 执行用时: 56 ms
  • 内存消耗: 44.1 MB

· 阅读需 3 分钟

1、题干​

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

 

示例 1:

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

 

提示：

  • 0 < grid.length <= 200
  • 0 < grid[0].length <= 200

2、解法1-动态规划​

循环遍历矩阵，累加礼物价值

状态转移方程：dp[i][j]+=max(dp[i−1][j],dp[i][j−1])dp[i][j] += max(dp[i-1][j], dp[i][j-1])


3、代码​

function maxValue(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            grid[i][j] += Math.max(i > 0 ? grid[i - 1][j] : 0, j > 0 ? grid[i][j - 1] : 0);
        }
    }
    return grid[m - 1][n - 1];
};

4、执行结果​

image.png


5、解法2-记忆化DFS​

DFS遍历矩阵，累加礼物价值

记录每个节点的最大价值作为缓存避免重复计算


6、代码​

function maxValue(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const visited = grid.map(row => row.map(() => 0));
    function dfs(i: number, j: number) {
        if (i < 0 || j < 0 || i >= m || j >= n) return 0;
        if (!visited[i][j]) visited[i][j] = grid[i][j] + Math.max(dfs(i - 1, j), dfs(i, j - 1));
        return visited[i][j];
    }
    return dfs(m - 1, n - 1);
};

7、执行结果​

  • 执行用时: 56 ms
  • 内存消耗: 44.1 MB

· 阅读需 3 分钟

1、题干​

用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。

箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。

  • 将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
  • 将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。

在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。

返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。

 

示例 1：

输入：grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
输出：[1,-1,-1,-1,-1]
解释：示例如图：
b0 球开始放在第 0 列上，最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。
b2 球开始放在第 2 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b3 球开始放在第 3 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b4 球开始放在第 4 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。

示例 2：

输入：grid = [[-1]]
输出：[-1]
解释：球被卡在箱子左侧边上。

示例 3：

输入：grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]
输出：[0,1,2,3,4,-1]

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • grid[i][j] 为 1 或 -1

2、解题思路​

按题意模拟

3、代码​

var findBall = function (grid) {
    const res = [], m = grid.length, n = grid[0].length;

    for (let j = 0; j < n; j++) {
        let k = j;
        for (let i = 0; i < m; i++) {
            if (grid[i][k] === 1 && grid[i][k] === grid[i][k + 1]) k++;
            else if (grid[i][k] === -1 && grid[i][k] === grid[i][k - 1]) k--;
            else res[j] = -1;
        }
        if (res[j] === undefined) res[j] = k;
    }

    return res;
};

4、执行结果​

image.png

· 阅读需 3 分钟

1、题干​

给你一个 m * n 的矩阵，矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。

幸运数 是指矩阵中满足同时下列两个条件的元素：

  • 在同一行的所有元素中最小
  • 在同一列的所有元素中最大

 

示例 1：

输入：matrix = [[3,7,8],[9,11,13],[15,16,17]]
输出：[15]
解释：15 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。

示例 2：

输入：matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
输出：[12]
解释：12 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。

示例 3：

输入：matrix = [[7,8],[1,2]]
输出：[7]
解释：7是唯一的幸运数字，因为它是行中的最小值，列中的最大值。

 

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= n, m <= 50
  • 1 <= matrix[i][j] <= 10^5
  • 矩阵中的所有元素都是不同的

最近JS的运行环境是不是调整了，执行结果的内存消耗普遍比年前高了一大截，明明空间复杂度是 O(1)O(1) 结果一提交发现击败7%，这到底是为什么啊喂？

wecom-temp-7e880fd1f913b7acf9e1efa1143efdd8.gif


2、解题思路​

双层遍历，外层按行号 i 逐行遍历，内层先遍历找出第 i 行最小列号 minCol；再遍历第 minCol 列所有元素，检查 matrix[i][minCol] 是否该列最大值，若是则加入结果数组 res


3、代码​

var luckyNumbers = function (matrix) {
    const res = [];
    for (let i = 0; i < matrix.length; i++) {
        const minCol = matrix[i].reduce((a, c, j) => c < matrix[i][a] ? j : a, 0);
        for (let r = 0; r < matrix.length; r++) {
            if (matrix[r][minCol] > matrix[i][minCol]) break;
            if (r === matrix.length - 1) res.push(matrix[i][minCol]);
        }
    }
    return res;
};

4、复杂度​

  • 时间复杂度：O(n2)O(n^2)
  • 空间复杂度：O(1)O(1)

5、执行结果​

image.png

· 阅读需 7 分钟

1、题干​

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：一个机器人每次只能向下或者向右移动一步。

 

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

 

注意：本题与主站 64 题相同： https://leetcode-cn.com/problems/minimum-path-sum/

2、解法1-暴力DFS​

看完题目之后没多想误认为是走迷宫的题，于是写了一版暴力 DFS ，结果超时了。代码逻辑是从左上角到右下角进行深度遍历，并且累计路径和代入下一步计算。


超时的原因在于 ：通常走迷宫的题不会重复经过某个节点，因此时间复杂度是 O(mn)O(mn)，以 m,n<=200m,n <= 200 来算不会超时； 但这个题目的暴力 DFS 可以看做是遍历一棵高度为 n+m−1n+m-1 的二叉树，时间复杂度接近指数级的 2n+m−12^{n+m-1}，超时也不足为奇。


从网格左上角到右下角的最短路径长度为 n+m−1n+m-1，因此把它当成树的话高度为 n+m−1n+m-1


暴力DFS超时代码

var minPathSum = function (grid) {
    const m = grid.length, n = grid[0].length
    let min = Infinity;

    function dfs(i, j, sum) {
        if (i >= m || j >= n) return;
        sum += grid[i][j]

        if (i === m - 1 && j === n - 1) min = Math.min(min, sum);

        dfs(i + 1, j, sum);
        dfs(i, j + 1, sum);
    }

    dfs(0, 0, 0);
    return min;
};

3、暴力DFS-优化​

通常暴力 DFS 可以通过剪枝、记忆化等方式进行优化，这里采用了剪枝优化，优化后AC了但耗时 3208 ms 依然很高。


这里的问题在于：

  • 上述DFS代码属于暴力遍历所有情况并在终点时计算最小值，没有求局部最优解的倾向
  • 剪枝优化不稳定：这里剪枝的方式是记录节点前序路径和，当再次访问该节点时判断当前情况的前序路径和是否更小，以决定是否继续遍历以及是否更新该前序路径和，这种剪枝方式存在不稳定性，因为记录的前序路径和不是最小，后续遍历可能会有更小的前序路径和出现，所以这种剪枝没办法排除掉最小值以外的所有情况

4、代码​

var minPathSum = function (grid) {
    const m = grid.length, n = grid[0].length
    let min = Infinity, minPreSum = new Map();

    function dfs(i, j, sum) {
        const key = i + '-' + j;
        if (i >= m || j >= n || sum >= (minPreSum.get(key) || Infinity)) return;
        minPreSum.set(key, sum);

        sum += grid[i][j]

        if (i === m - 1 && j === n - 1) min = Math.min(min, sum);

        dfs(i + 1, j, sum);
        dfs(i, j + 1, sum);
    }

    dfs(0, 0, 0);
    return min;
};

5、执行结果​

  • 执行用时: 3208 ms
  • 内存消耗: 53 MB

6、解法2-记忆化DFS​

这个解法思路接近于动态规划， dfs 函数的意图是求局部最优解最终得到全局最优解，其中 dfs(i, j) 代表从终点 (m, n) 到点 (i, j) 的最小路径和，然后通过哈希表记录点 (i, j) 的最小路径和，后续再次遍历到该节点直接返回最小路径和，无需多余遍历与计算。


7、代码​

var minPathSum = function (grid) {
    const m = grid.length, n = grid[0].length
    const minSum = new Map();

    function dfs(i, j) {
        if (i >= m || j >= n) return Infinity;
        if (i === m - 1 && j === n - 1) return grid[i][j];

        const key = i + '-' + j;
        if (minSum.has(key)) return minSum.get(key);

        const min = Math.min(dfs(i + 1, j), dfs(i, j + 1)) + grid[i][j];
        return minSum.set(key, min), min;
    }

    return dfs(0, 0);
};

8、执行结果​

  • 执行用时: 76 ms
  • 内存消耗: 49.2 MB

9、解法3-动态规划​

解法2采用的是逆序累加和求解，这里为了方便理解采用顺序累加和进行求解。从题意可以看出对于任意节点 (i, j)，其最小路径和取决于上方节点 (i-1, j) 和左方节点 (i, j-1)，其值为左上两个节点中最小路径和的较小值加上自身的值。

  • dp 数组含义：dp 数组是一个 (m+1)*(n+1) 的数组，其中 dp[i][j] 表示从起点 (0, 0) 到点 (i, j) 的最小路径和，其中第一行和第一列只是为了方便计算，没有实际含义
  • 状态转移方程是：
    • i === 1 && j === 1 时：dp[i][j] = grid[i - 1][j - 1]
    • 其他情况：dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]
  • dp[i][j] 对应的节点是 grid[i - 1][j - 1]，因此遍历 dp 数组时 i 和 j 都从下标 1 开始

10、代码​

var minPathSum = function (grid) {
    const m = grid.length, n = grid[0].length
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(Infinity));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (i === 1 && j === 1) dp[i][j] = grid[i - 1][j - 1];
            else dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        }
    }

    return dp[m][n];
};

11、执行结果​

  • 执行用时: 76 ms
  • 内存消耗: 44 MB

12、最后​

题解区有更优秀的动态规划解法，有降维 DP（一维）、有把原始数组 grid 作为 DP 数组等，主要降低了空间复杂度，很值得学习。

· 阅读需 7 分钟

1、题干​

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：一个机器人每次只能向下或者向右移动一步。

 

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

 

注意：本题与主站 64 题相同： https://leetcode-cn.com/problems/minimum-path-sum/

2、解法1-暴力DFS​

看完题目之后没多想误认为是走迷宫的题，于是写了一版暴力 DFS ，结果超时了。代码逻辑是从左上角到右下角进行深度遍历，并且累计路径和代入下一步计算。


超时的原因在于 ：通常走迷宫的题不会重复经过某个节点，因此时间复杂度是 O(mn)O(mn)，以 m,n<=200m,n <= 200 来算不会超时； 但这个题目的暴力 DFS 可以看做是遍历一棵高度为 n+m−1n+m-1 的二叉树，时间复杂度接近指数级的 2n+m−12^{n+m-1}，超时也不足为奇。


从网格左上角到右下角的最短路径长度为 n+m−1n+m-1，因此把它当成树的话高度为 n+m−1n+m-1


暴力DFS超时代码

var minPathSum = function (grid) {
    const m = grid.length, n = grid[0].length
    let min = Infinity;

    function dfs(i, j, sum) {
        if (i >= m || j >= n) return;
        sum += grid[i][j]

        if (i === m - 1 && j === n - 1) min = Math.min(min, sum);

        dfs(i + 1, j, sum);
        dfs(i, j + 1, sum);
    }

    dfs(0, 0, 0);
    return min;
};

3、暴力DFS-优化​

通常暴力 DFS 可以通过剪枝、记忆化等方式进行优化，这里采用了剪枝优化，优化后AC了但耗时 3208 ms 依然很高。


这里的问题在于：

  • 上述DFS代码属于暴力遍历所有情况并在终点时计算最小值，没有求局部最优解的倾向
  • 剪枝优化不稳定：这里剪枝的方式是记录节点前序路径和，当再次访问该节点时判断当前情况的前序路径和是否更小，以决定是否继续遍历以及是否更新该前序路径和，这种剪枝方式存在不稳定性，因为记录的前序路径和不是最小，后续遍历可能会有更小的前序路径和出现，所以这种剪枝没办法排除掉最小值以外的所有情况

4、代码​

var minPathSum = function (grid) {
    const m = grid.length, n = grid[0].length
    let min = Infinity, minPreSum = new Map();

    function dfs(i, j, sum) {
        const key = i + '-' + j;
        if (i >= m || j >= n || sum >= (minPreSum.get(key) || Infinity)) return;
        minPreSum.set(key, sum);

        sum += grid[i][j]

        if (i === m - 1 && j === n - 1) min = Math.min(min, sum);

        dfs(i + 1, j, sum);
        dfs(i, j + 1, sum);
    }

    dfs(0, 0, 0);
    return min;
};

5、执行结果​

  • 执行用时: 3208 ms
  • 内存消耗: 53 MB

6、解法2-记忆化DFS​

这个解法思路接近于动态规划， dfs 函数的意图是求局部最优解最终得到全局最优解，其中 dfs(i, j) 代表从终点 (m, n) 到点 (i, j) 的最小路径和，然后通过哈希表记录点 (i, j) 的最小路径和，后续再次遍历到该节点直接返回最小路径和，无需多余遍历与计算。


7、代码​

var minPathSum = function (grid) {
    const m = grid.length, n = grid[0].length
    const minSum = new Map();

    function dfs(i, j) {
        if (i >= m || j >= n) return Infinity;
        if (i === m - 1 && j === n - 1) return grid[i][j];

        const key = i + '-' + j;
        if (minSum.has(key)) return minSum.get(key);

        const min = Math.min(dfs(i + 1, j), dfs(i, j + 1)) + grid[i][j];
        return minSum.set(key, min), min;
    }

    return dfs(0, 0);
};

8、执行结果​

  • 执行用时: 76 ms
  • 内存消耗: 49.2 MB

9、解法3-动态规划​

解法2采用的是逆序累加和求解，这里为了方便理解采用顺序累加和进行求解。从题意可以看出对于任意节点 (i, j)，其最小路径和取决于上方节点 (i-1, j) 和左方节点 (i, j-1)，其值为左上两个节点中最小路径和的较小值加上自身的值。

  • dp 数组含义：dp 数组是一个 (m+1)*(n+1) 的数组，其中 dp[i][j] 表示从起点 (0, 0) 到点 (i, j) 的最小路径和，其中第一行和第一列只是为了方便计算，没有实际含义
  • 状态转移方程是：
    • i === 1 && j === 1 时：dp[i][j] = grid[i - 1][j - 1]
    • 其他情况：dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]
  • dp[i][j] 对应的节点是 grid[i - 1][j - 1]，因此遍历 dp 数组时 i 和 j 都从下标 1 开始

10、代码​

var minPathSum = function (grid) {
    const m = grid.length, n = grid[0].length
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(Infinity));

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (i === 1 && j === 1) dp[i][j] = grid[i - 1][j - 1];
            else dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
        }
    }

    return dp[m][n];
};

11、执行结果​

  • 执行用时: 76 ms
  • 内存消耗: 44 MB

12、最后​

题解区有更优秀的动态规划解法，有降维 DP（一维）、有把原始数组 grid 作为 DP 数组等，主要降低了空间复杂度，很值得学习。

· 阅读需 3 分钟

1、题干​

给你一个下标从 0 开始的一维整数数组 original 和两个整数 m 和  n 。你需要使用 original 中 所有 元素创建一个 m 行 n 列的二维数组。

original 中下标从 0 到 n - 1 （都 包含 ）的元素构成二维数组的第一行，下标从 n 到 2 * n - 1 （都 包含 ）的元素构成二维数组的第二行，依此类推。

请你根据上述过程返回一个 m x n 的二维数组。如果无法构成这样的二维数组，请你返回一个空的二维数组。

 

示例 1：

输入：original = [1,2,3,4], m = 2, n = 2
输出：[[1,2],[3,4]]
解释：
构造出的二维数组应该包含 2 行 2 列。
original 中第一个 n=2 的部分为 [1,2] ，构成二维数组的第一行。
original 中第二个 n=2 的部分为 [3,4] ，构成二维数组的第二行。

示例 2：

输入：original = [1,2,3], m = 1, n = 3
输出：[[1,2,3]]
解释：
构造出的二维数组应该包含 1 行 3 列。
将 original 中所有三个元素放入第一行中，构成要求的二维数组。

示例 3：

输入：original = [1,2], m = 1, n = 1
输出：[]
解释：
original 中有 2 个元素。
无法将 2 个元素放入到一个 1x1 的二维数组中，所以返回一个空的二维数组。

示例 4：

输入：original = [3], m = 1, n = 2
输出：[]
解释：
original 中只有 1 个元素。
无法将 1 个元素放满一个 1x2 的二维数组，所以返回一个空的二维数组。

 

提示：

  • 1 <= original.length <= 5 * 104
  • 1 <= original[i] <= 105
  • 1 <= m, n <= 4 * 104

2、解题思路​

考察数组基本操作

3、代码​

var construct2DArray = function (original, m, n) {
    return original.length !== m * n ? [] : new Array(m).fill(0).map((v, i) => {
        return original.slice(n * i, n * i + n);
    });
};

4、执行结果​

1.png

· 阅读需 3 分钟

1、题干​

给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ，返回在甲板 board 上放置的 战舰 的数量。

战舰 只能水平或者垂直放置在 board 上。换句话说，战舰只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状建造，其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰）。

 

示例 1：

输入：board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
输出：2

示例 2：

输入：board = [["."]]
输出：0

 

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] 是 '.' 或 'X'

 

进阶：你可以实现一次扫描算法，并只使用 O(1) 额外空间，并且不修改 board 的值来解决这个问题吗？

执行结果​

1.png

解法1-寻找船头​

由于战舰只能水平或者垂直放置在board上，那就意味着船头位置的左边和上边必然是空位。因此只要双循环遍历整个board矩阵，遇到船头则战舰数量加一。

同理可以寻找船尾，船尾的右边和下边必然是空位。

代码​

一行强迫症写法

var countBattleships = function (board) {
    return board.reduce((acc, cur, i) => acc + cur.filter((c, j) => c === 'X' && board[i][j - 1] !== 'X' && (!i || board[i - 1][j] !== 'X')).length, 0);
};

常规写法

var countBattleships = function (board) {
    let res = 0;

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (board[i][j] == 'X' && board[i][j - 1] !== 'X' && (!i || board[i - 1][j] !== 'X')) res++;
        }
    }

    return res;
};

解法2-DFS​

双循环遍历整个board矩阵，遇到战舰则战舰数量加一，然后深度遍历战舰所占位置，把遍历过的战舰位置修改成空位避免重复遍历。

代码​

var countBattleships = function (board) {
    let res = 0;
    function dfs(i, j) {
        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] !== 'X') return;

        board[i][j] = '.';
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }

    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            if (board[i][j] === 'X') dfs(i, j), res++;
        }
    }

    return res;
};

· 阅读需 2 分钟

1、题干​

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

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

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

 

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0' 或 '1'

解题思路​

  • 遍历矩阵grid，以grid[i][j]为起点往上下左右4个方向进行深度遍历
  • 深度遍历过程中需要注意2点
    • 遍历过的节点修改为0，即grid[i][j] = '0'，以免重复遍历
    • grid[i][j]必须在矩阵中且grid[i][j] === '1'才累加岛屿数量

代码​

var numIslands = function (grid) {
    const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    function dfs(i, j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] === '0') return false;
        grid[i][j] = '0';
        for (const [di, dj] of dirs) dfs(i + di, j + dj);
        return true;
    }

    let count = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (dfs(i, j)) count++;
        }
    }

    return count;
};

· 阅读需 4 分钟

1、题干​

给你一座由 n x n 个街区组成的城市，每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 grid ，其中 grid[r][c] 表示坐落于 r 行 c 列的建筑物的 高度 。

城市的 天际线 是从远处观察城市时，所有建筑物形成的外部轮廓。从东、南、西、北四个主要方向观测到的 天际线 可能不同。

我们被允许为 任意数量的建筑物 的高度增加 任意增量（不同建筑物的增量可能不同） 。 高度为 0 的建筑物的高度也可以增加。然而，增加的建筑物高度 不能影响 从任何主要方向观察城市得到的 天际线 。

在 不改变 从任何主要方向观测到的城市 天际线 的前提下，返回建筑物可以增加的 最大高度增量总和 。

 

示例 1：

输入：grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出：35
解释：建筑物的高度如上图中心所示。
用红色绘制从不同方向观看得到的天际线。
在不影响天际线的情况下，增加建筑物的高度：
gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

示例 2：

输入：grid = [[0,0,0],[0,0,0],[0,0,0]]
输出：0
解释：增加任何建筑物的高度都会导致天际线的变化。

 

提示：

  • n == grid.length
  • n == grid[r].length
  • 2 <= n <= 50
  • 0 <= grid[r][c] <= 100

解题思路​

题目比较简单，两次遍历先取行列最大值再累加最大差值即可。详细步骤如下：

  • 先计算各行最大值maxInRows和各列最大值maxInCols
  • 再遍历矩阵grid中每个元素，元素增大的上限是该行最大值maxInRows[i]和该列最大值maxInCols[j]中较小的那个
  • 求局部最优解：计算出每个建筑物可以增加的最大高度(Math.min(maxInRows[i], maxInCols[j]) - grid[i][j])
  • 累加可得全局最优解：建筑物高度可以增加的最大总和

时间复杂度：O(n2)O(n^2)

代码​

var maxIncreaseKeepingSkyline = function (grid) {
    const maxInRows = new Array(grid.length).fill(0);
    const maxInCols = new Array(grid[0].length).fill(0);

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            maxInRows[i] = Math.max(maxInRows[i], grid[i][j]);
            maxInCols[j] = Math.max(maxInCols[j], grid[i][j]);
        }
    }

    let res = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            res += (Math.min(maxInRows[i], maxInCols[j]) - grid[i][j]);
        }
    }

    return res;
};