标签： 矩阵

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

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

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

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

 

示例 1：

输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

示例 2：

输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]

 

提示：

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

 

进阶：

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

数组复制 & 简化易懂版的原地修改
题意很好理解，直接上来就是淦代码

顺便自己写了个页面http://next.cheungq.com/ 里面有个生命游戏的演示

数组复制的方法代码

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[][] ans = new int[m][n];
        int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1},{1,-1},{1,1},{-1,1},{-1,-1}};

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                int cnt = 0;
                for (int i = 0; i < dir.length; i++) {
                    int x = row+dir[i][0];
                    int y = col+dir[i][1];
                    if (x<0||y<0||x>=m||y>=n){
                        continue;
                    }
                    cnt += board[x][y];
                }

                if (board[row][col] == 1){
                    //如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
                    ans[row][col] = (cnt == 2 || cnt == 3)?1:0;
                    //如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
                    //如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
                }else{
                    //如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
                    ans[row][col] = cnt==3?1:0;
                }
            }
        }

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                board[row][col] = ans[row][col];
            }
        }
    }
}

原地修改

而原地修改大佬们用的方法略高端，用二进制位的状态来标记。我这有个简化版的原理一样。
思路如下，也许可以帮到你更加容易的来理解这个过程

1. 因为周围最多只有8个格子，所以周围最多活细胞数量只有8个，这个数字小于10，那么我们可以活用这个关系
2. 讲当前格子状态进一位，变成10或者00，第一位表示当前格子的状态
3. 后面一位的0我们更新为周围8个格子的活细胞数量，
4. 比如更新后当前格子的值为14，第一位1表示当前格子是活细胞，周围8个格子中有4个活细胞
5. 又比如更新后当前格子的值为5,第一位的10位数上没有，即为0，那么表明当前格子为死细胞，周围有5个活细胞
6. 一遍更新完了之后，我们就可以根据更新后的结果值来重新换算下当前格子的下一步状态值是死细胞还是活细胞了
7. 又，因为是从左往右，从上往下的更新的，所以，在计算周围8个格子中活细胞数量的时候需要注意一下以下情况
   • 当前行的上一行对应的3个格子中的结果是已经计算过之后的结果，所以判断细胞死活情况需要判断的是10位数的值
   • 当前格子当前行左边一个格子也是已经计算过的结果，所以也需要根据10位数的值来判断死活情况

原地修改代码

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1},{1,-1},{1,1},{-1,1},{-1,-1}};
        int cnt = 0;
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                cnt = 0;
                for (int i = 0; i < dir.length; i++) {
                    int x = row+dir[i][0];
                    int y = col+dir[i][1];
                    if (x<0||y<0||x>=m||y>=n){
                        continue;
                    }
                    if (dir[i][0]<0 || (dir[i][0]==0 && dir[i][1]<0)){
                        cnt += board[x][y]/10;
                    }else{
                        cnt += board[x][y];
                    }
                }
                board[row][col] = board[row][col]*10 + cnt;
            }
        }

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                cnt = board[row][col] % 10;
                int status = board[row][col]/10;
                if (status==1){
                    board[row][col] = (cnt == 2 || cnt == 3)?1:0;
                }else{
                    board[row][col] =  cnt==3?1:0;
                }
            }
        }
    }
}

给你一座由 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

class Solution {
    public int maxIncreaseKeepingSkyline(int[][] grid) {
        int[] rowMin = new int[grid.length];
        int[] colMin = new int[grid[0].length];
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[row].length; col++) {
                int height = grid[row][col];
                rowMin[row] = Math.max(rowMin[row],height);
                colMin[col] = Math.max(colMin[col],height);
            }
        }
        int ans = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[row].length; col++) {
                ans += Math.min(rowMin[row],colMin[col]) - grid[row][col];
            }
        }
        return ans;
    }
}