案例

有效的数独(中)

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

示例 1：

img

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字（1-9）或者 '.'

解题思路

1. 使用哈希表分别跟踪每一行、每一列以及每个3x3宫内出现的数字。
2. 对于数独板上的每个元素，如果是数字，检查其是否在其所属的行、列或宫内重复出现。
3. 如果发现重复，则说明数独解决方案无效，函数返回 false。
4. 如果整个板遍历完毕，没有发现重复数字，则数独方案有效，函数返回 true。

算法流程：

1. 初始化三个哈希表，用来存储每个行、每个列、每个宫的数字出现情况。
2. 依次遍历数独棋盘上的每个格子，进行以下操作：
   • 如果格子是空的（.），继续检查下一个格子。
   • 如果格子中有数字（1到9），则：
     • 计算它所在的宫的索引号。
     • 检查当前数字是否已经在该行、该列、或该宫中存储过。这一步通过查找哈希表来完成，键的形式分别是行号-数字、列号-数字、宫索引-数字。
3. 如果在步骤2中发现某个数字在同行、同列或同宫中已存在，立刻返回 false。
4. 如果所有格子都检查完毕，没有发现问题，返回 true。

通过上述逻辑，代码有效地遍历了所有格子，且有效避免了重复计算和不必要的检查，保证了算法的效率。这个算法的时间复杂度为 O(n^2)，其中 n 是数独每一行或列的长度，在此案例中为常数9，所以实际是 O(1)（固定大小的棋盘）。

// 定义函数isValidSudoku来判断一个9x9的数独板是否有效
var isValidSudoku = function (board) {
    // 初始化三个哈希表来记录行、列以及3x3子格子中的数字是否出现过
    let rows = {};
    let columns = {};
    let boxes = {};

    // 两层循环遍历数独的每个格子
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            // 提取当前坐标格子中的数字
            let num = board[i][j];

            // 如果当前格子有数字（不是'.'），则检查该数字是否在其所在的行、列或3x3子格子中重复
            if (num != '.') {
                // 计算3x3子格子的索引
                let boxIndex = parseInt(i / 3) * 3 + parseInt(j / 3);
                
                // 构建在哈希表中检查的键
                // 对于行来说，使用行号-数字作为键
                // 对于列来说，使用列号-数字作为键
                // 对于3x3子格子来说，使用盒子索引-数字作为键
                // 检查数字是否已经在所属行、列或3x3子格子中出现过
                if (rows[i + '-' + num] || columns[j + '-' + num] || boxes[boxIndex + '-' + num]) {
                    // 如果任何检查为真，则立即返回false，因为数独无效
                    return false;
                }

                // 在哈希表中记录当前数字已在对应的行、列和3x3子格子中出现过
                rows[i + '-' + num] = true;
                columns[j + '-' + num] = true;
                boxes[boxIndex + '-' + num] = true;
            }
        }
    }
    // 如果所有的格子都检查完毕且没有发现重复，说明数独有效，返回true
    return true;
};

螺旋矩阵(中)

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

示例 1：

img

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

示例 2：

img

输入：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]

解题思路

根据题目示例 matrix = [[1,2,3],[4,5,6],[7,8,9]] 的对应输出 [1,2,3,6,9,8,7,4,5] 可以发现，顺时针打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环。

因此，考虑设定矩阵的 “左、上、右、下” 四个边界，模拟以上矩阵遍历顺序。

image-20240118102553791

算法步骤：

1. 空值处理： 当 matrix 为空时，直接返回空列表 [] 即可。
2. 初始化： 矩阵 左、右、上、下 四个边界 l , r , t , b ，用于打印的结果列表 res 。
3. 循环打印： “从左向右、从上向下、从右向左、从下向上” 四个方向循环打印。
   1. 根据边界打印，即将元素按顺序添加至列表 res 尾部。
   2. 边界向内收缩 1 （代表已被打印）。
   3. 判断边界是否相遇（是否打印完毕），若打印完毕则跳出。
4. 返回值： 返回 res 即可。

image-20240118102416298

/*
  函数：spiralOrder
  参数：matrix - 二维数组，表示一个矩阵
  返回值：以螺旋顺序遍历矩阵的结果数组
*/

function spiralOrder(matrix) {
    if (!matrix.length) return []; // 如果矩阵为空，直接返回空数组
    let l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, res = []; // 初始化边界指针和结果数组
    while (true) {
        // 从左到右遍历上边界
        for (let i = l; i <= r; i++) res.push(matrix[t][i]);
        t += 1; // 上边界下移一行
        if (t > b) break; // 如果上边界超过下边界，则结束循环

        // 从上到下遍历右边界
        for (let i = t; i <= b; i++) res.push(matrix[i][r]);
        r -= 1; // 右边界左移一列
        if (l > r) break; // 如果左边界超过右边界，则结束循环

        // 从右到左遍历下边界
        for (let i = r; i >= l; i--) res.push(matrix[b][i]);
        b -= 1; // 下边界上移一行
        if (t > b) break; // 如果上边界超过下边界，则结束循环

        // 从下到上遍历左边界
        for (let i = b; i >= t; i--) res.push(matrix[i][l]);
        l += 1; // 左边界右移一列
        if (l > r) break; // 如果左边界超过右边界，则结束循环
    }
    return res; // 返回螺旋遍历结果数组
}

旋转图像(中)

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在** 原地** 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

img

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

示例 2：

img

输入：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].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

解题思路

方法一：辅助矩阵

如下图所示，矩阵顺时针旋转 90º 后，可找到以下规律：

「第 i 行」元素旋转到「第 n−1−i 列」元素；
「第 j 列」元素旋转到「第 j 行」元素；
因此，对于矩阵任意第 i 行、第 j 列元素 matrix[i][j]，矩阵旋转 90º 后「元素位置旋转公式」为：

image-20240119102020382

方法二：原地修改

image-20240119103233716

image-20240119103321532

image-20240119104714647

image-20240119104739491

方法三：用翻转代替旋转

image-20240119105448126

image-20240119105507295

辅助矩阵

var rotate = function (matrix) {
    const len = matrix.length;
    // 深拷贝
    const ans = JSON.parse(JSON.stringify(matrix));
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            matrix[j][len - 1 - i] = ans[i][j]
        }
    }
    return ans;
};

原地修改

// 定义一个函数，用于将一个n×n的矩阵顺时针旋转90度，不使用额外的空间
var rotate = function(matrix) {
    // 获取矩阵的长度
    const n = matrix.length;
    // 遍历矩阵的每一层，从外层到内层
    for (let i = 0; i < Math.floor(n / 2); ++i) {
        // 遍历该层的前n-1-i*2个元素，从左上角开始
        for (let j = 0; j < Math.floor((n + 1) / 2); ++j) {
            // 保存当前元素到一个临时变量
            const temp = matrix[i][j];
            // 将当前元素与它顺时针旋转后的位置的元素交换，共四次交换
            matrix[i][j] = matrix[n - j - 1][i];
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
            matrix[j][n - i - 1] = temp;
        }
    }
};

用翻转代替旋转

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]];
        }
    }
};

矩阵置零(中)

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

image-20240122092500525

image-20240122092520733

解题思路

使用标记数组

我们可以用两个标记数组分别记录每一行和每一列是否有零出现。

具体地，我们首先遍历该数组一次，如果某个元素为 0，那么就记录该元素所在的行和列。最后我们再次遍历该数组，用标记数组更新原数组即可。

使用一个标记变量

利用矩阵的第一行和第一列来记录哪些行和列需要置为0，但是在这之前，我们需要先判断第一行和第一列本身是否有0元素，因为如果有的话，它们也需要被置为0。我们用两个布尔变量来存储这个信息，然后根据这两个变量来决定最后是否将第一行和第一列都置为0。

具体的步骤如下：

• 初始化两个布尔变量，分别表示第一行和第一列是否有0元素。
• 遍历第一行和第一列，如果有0元素，就将对应的布尔变量置为true。
• 遍历除了第一行和第一列之外的元素，如果有0元素，就将对应的第一行和第一列的元素置为0。
• 根据第一行和第一列的元素，将需要置为0的行和列的元素置为0。
• 根据之前的两个布尔变量，将第一行和第一列的元素置为0（如果需要的话）。

这样做的空间复杂度是O(1)，因为我们只用了常数个额外的变量。时间复杂度仍然是O(mn)，其中m和n分别是矩阵的行数和列数。

标记数组

var setZeroes = function (matrix) {
    const rowLen = matrix.length;
    const colLen = matrix[0].length;
    let zeroRows = new Set();
    let zeroCols = new Set();

    // 遍历矩阵，找到值为0的元素的行和列
    for (let row = 0; row < rowLen; row++) {
        for (let col = 0; col < colLen; col++) {
            if (matrix[row][col] === 0) {
                zeroRows.add(row);
                zeroCols.add(col);
            }
        }
    }

    // 将对应行和列的元素置为0
    zeroRows.forEach((row) => {
        for (let col = 0; col < colLen; col++) {
            matrix[row][col] = 0;
        }
    });

    zeroCols.forEach((col) => {
        for (let row = 0; row < rowLen; row++) {
            matrix[row][col] = 0;
        }
    });
};

使用一个标记变量

// 函数名: setZeroes
// 参数: matrix - 二维矩阵，表示一个矩阵的布尔值
var setZeroes = function(matrix) {
    // 获取矩阵的行数和列数
    const m = matrix.length, n = matrix[0].length;

    // 用于标记第一列是否有零
    let flagCol0 = false;

    // 第一次遍历矩阵，将零元素对应的行首和列首置为零
    for (let i = 0; i < m; i++) {
        if (matrix[i][0] === 0) {
            flagCol0 = true;
        }
        for (let j = 1; j < n; j++) {
            if (matrix[i][j] === 0) {
                matrix[i][0] = matrix[0][j] = 0;
            }
        }
    }

    // 第二次遍历矩阵，根据行首和列首的标记，将对应元素置为零
    for (let i = m - 1; i >= 0; i--) {
        for (let j = 1; j < n; j++) {
            if (matrix[i][0] === 0 || matrix[0][j] === 0) {
                matrix[i][j] = 0;
            }
        }
        // 如果第一列有零，将该行首元素置为零
        if (flagCol0) {
            matrix[i][0] = 0;
        }
    }
};

生命游戏(中)

根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

提示：

• m == board.length
• n == board[i].length
• 1 <= m, n <= 25
• board[i][j] 为 0 或 1

进阶：

• 你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
• 本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

解题思路

1. 方法一：复制原数组进行模拟

   这个问题看起来很简单，但有一个陷阱，如果你直接根据规则更新原始数组，那么就做不到题目中说的 同步 更新。假设你直接将更新后的细胞状态填入原始数组，那么当前轮次其他细胞状态的更新就会引用到当前轮已更新细胞的状态，但实际上每一轮更新需要依赖上一轮细胞的状态，是不能用这一轮的细胞状态来更新的。

   如上图所示，已更新细胞的状态会影响到周围其他还未更新细胞状态的计算。一个最简单的解决方法就是复制一份原始数组，复制的那一份永远不修改，只作为更新规则的引用。这样原始数组的细胞值就不会被污染了。

2. 方法二：使用额外的状态

   方法一中 O(mn)O(mn)O(mn) 的空间复杂度在数组很大的时候内存消耗是非常昂贵的。题目中每个细胞只有两种状态 live(1) 或 dead(0)，但我们可以拓展一些复合状态使其包含之前的状态。举个例子，如果细胞之前的状态是 0，但是在更新之后变成了 1，我们就可以给它定义一个复合状态 2。这样我们看到 2，既能知道目前这个细胞是活的，还能知道它之前是死的。

   算法

   遍历 board 中的细胞。

   根据数组的细胞状态计算新一轮的细胞状态，这里会用到能同时代表过去状态和现在状态的复合状态。

   具体的计算规则如下所示：

   • 规则 1：如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡。这时候，将细胞值改为 -1，代表这个细胞过去是活的现在死了；
   • 规则 2：如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活。这时候不改变细胞的值，仍为 1；
   • 规则 3：如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡。这时候，将细胞的值改为 -1，代表这个细胞过去是活的现在死了。可以看到，因为规则 1 和规则 3 下细胞的起始终止状态是一致的，因此它们的复合状态也一致；
   • 规则 4：如果死细胞周围正好有三个活细胞，则该位置死细胞复活。这时候，将细胞的值改为 2，代表这个细胞过去是死的现在活了。*

   根据新的规则更新数组；

   现在复合状态隐含了过去细胞的状态，所以我们可以在不复制数组的情况下完成原地更新；

   对于最终的输出，需要将 board 转成 0，1 的形式。因此这时候需要再遍历一次数组，将复合状态为 2 的细胞的值改为 1，复合状态为 -1 的细胞的值改为 0。

3. 方法三：位运算

• 使用两位二进制数来表示每个细胞的状态，第一位表示下一个状态，第二位表示当前状态。例如，00表示死细胞不变，01表示活细胞变死，10表示死细胞变活，11表示活细胞不变。
• 遍历二维数组中的每个细胞，计算它周围的活细胞数量，然后根据游戏规则更新它的第一位。如果当前细胞是活的，且周围有2或3个活细胞，那么它的第一位为1，否则为0。如果当前细胞是死的，且周围有3个活细胞，那么它的第一位为1，否则为0。
• 再次遍历二维数组中的每个细胞，将它的状态右移一位，即取出它的第一位，作为它的新状态。

这样，我们就可以用原地算法解决生命游戏的问题，不需要额外的空间。

复制原数组进行模拟

// 定义一个函数，参数是一个二维数组，表示一个由死细胞（0）和活细胞（1）组成的网格
function gameOfLife(board) {
    // 定义一个数组，表示细胞周围的八个方向
    const neighbors = [[1, 0], [1, -1], [0, -1], [-1, -1], [-1, 0], [-1, 1], [0, 1], [1, 1]];
    // 获取网格的行数和列数
    const rows = board.length;
    const cols = board[0].length;

    // 创建一个和原数组一样大小的副本，用于存储原始的细胞状态
    const copy_board = board.map(row => row.slice());

    // 遍历每个细胞
    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {

            // 初始化一个变量，记录当前细胞周围的活细胞数量
            let live_neighbors = 0;
            // 遍历细胞周围的八个方向
            for (let neighbor of neighbors) {
                // 计算相邻位置的行号和列号
                const r = row + neighbor[0];
                const c = col + neighbor[1];

                // 判断相邻位置是否在网格范围内，且是否为活细胞
                if (r < rows && r >= 0 && c < cols && c >= 0 && copy_board[r][c] === 1) {
                    // 如果是，活细胞数量加一
                    live_neighbors += 1;
                }
            }

            // 根据活细胞数量，判断当前细胞在下一代应该是死亡还是存活，并更新原数组中对应的位置
            // 如果当前细胞是活的，且周围有少于两个或超过三个活细胞，就会死亡
            if (copy_board[row][col] === 1 && (live_neighbors < 2 || live_neighbors > 3)) {
                board[row][col] = 0;
            }
            // 如果当前细胞是死的，且周围有正好三个活细胞，就会复活
            if (copy_board[row][col] === 0 && live_neighbors === 3) {
                board[row][col] = 1;
            }
        }
    }
    // 返回原数组，即为更新后的网格状态
    return board;
}

复合状态

function gameOfLife(board) {
  // 定义八个方向的偏移量
  const neighbors = [
    [1, 0],
    [1, -1],
    [0, -1],
    [-1, -1],
    [-1, 0],
    [-1, 1],
    [0, 1],
    [1, 1],
  ];

  // 获取 board 的行数和列数
  const rows = board.length;
  const cols = board[0].length;

  // 遍历 board 中的每个细胞
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      // 初始化活邻居的个数为 0
      let liveNeighbors = 0;

      // 遍历八个方向的邻居
      for (let neighbor of neighbors) {
        // 计算邻居的坐标
        let r = row + neighbor[0];
        let c = col + neighbor[1];

        // 判断邻居是否在 board 范围内，以及是否为活细胞
        if (
          r < rows &&
          r >= 0 &&
          c < cols &&
          c >= 0 &&
          Math.abs(board[r][c]) === 1
        ) {
          // 如果是活细胞，增加活邻居的个数
          liveNeighbors += 1;
        }
      }

      // 根据规则更新细胞的状态，用 -1 表示从活变死，用 2 表示从死变活
      if (board[row][col] === 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
        board[row][col] = -1;
      }
      if (board[row][col] === 0 && liveNeighbors === 3) {
        board[row][col] = 2;
      }
    }
  }

  // 遍历 board 中的每个细胞，把 -1 和 2 分别变成 0 和 1
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (board[row][col] > 0) {
        board[row][col] = 1;
      } else {
        board[row][col] = 0;
      }
    }
  }
}

位运算

function gameOfLife(board) {
    // 定义相邻元素的坐标偏移
    const dx = [-1, 0, 1, -1, 1, -1, 0, 1];
    const dy = [-1, -1, -1, 0, 0, 1, 1, 1];

    // 遍历二维数组中的每个元素
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            let sum = 0; // 用于计算当前元素周围存活细胞的数量

            // 遍历当前元素周围的8个相邻元素
            for (let k = 0; k < 8; k++) {
                let nx = i + dx[k]; // 计算相邻元素的横坐标
                let ny = j + dy[k]; // 计算相邻元素的纵坐标

                // 检查相邻元素坐标是否在有效范围内
                if (nx >= 0 && nx < board.length && ny >= 0 && ny < board[0].length) {
                    // 如果相邻元素是存活的，增加存活细胞数量
                    sum += board[nx][ny] & 1;
                }
            }

            // 根据游戏规则更新当前元素状态
            if ((board[i][j] & 1) === 1) {
                // 当前元素为存活状态
                if (sum >= 2 && sum <= 3) {
                    // 存活细胞周围有2或3个存活细胞，当前细胞继续存活
                    board[i][j] |= 2;
                }
            } else {
                // 当前元素为死亡状态
                if (sum === 3) {
                    // 死亡细胞周围有3个存活细胞，当前细胞变为存活状态
                    board[i][j] |= 2;
                }
            }
        }
    }
    // 更新细胞状态
    for (let i = 0; i < board.length; i++) {
        for (let j = 0; j < board[0].length; j++) {
            board[i][j] >>= 1; // 右移一位，更新细胞状态
        }
    }
}