标签： 模拟

根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 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;
                }
            }
        }
    }
}

给你一个待查数组 queries ，数组中的元素为 1 到 m 之间的正整数。 请你根据以下规则处理所有待查项 queries[i]（从 i=0 到 i=queries.length-1）：

• 一开始，排列 P=[1,2,3,...,m]。
• 对于当前的 i ，请你找出待查项 queries[i] 在排列 P 中的位置（下标从 0 开始），然后将其从原位置移动到排列 P 的起始位置（即下标为 0 处）。注意， queries[i] 在 P 中的位置就是 queries[i] 的查询结果。

请你以数组形式返回待查数组  queries 的查询结果。

 

示例 1：

输入：queries = [3,1,2,1], m = 5
输出：[2,1,2,1] 
解释：待查数组 queries 处理如下：
对于 i=0: queries[i]=3, P=[1,2,3,4,5], 3 在 P 中的位置是 2，接着我们把 3 移动到 P 的起始位置，得到 P=[3,1,2,4,5] 。
对于 i=1: queries[i]=1, P=[3,1,2,4,5], 1 在 P 中的位置是 1，接着我们把 1 移动到 P 的起始位置，得到 P=[1,3,2,4,5] 。 
对于 i=2: queries[i]=2, P=[1,3,2,4,5], 2 在 P 中的位置是 2，接着我们把 2 移动到 P 的起始位置，得到 P=[2,1,3,4,5] 。
对于 i=3: queries[i]=1, P=[2,1,3,4,5], 1 在 P 中的位置是 1，接着我们把 1 移动到 P 的起始位置，得到 P=[1,2,3,4,5] 。 
因此，返回的结果数组为 [2,1,2,1] 。  

示例 2：

输入：queries = [4,1,2,2], m = 4
输出：[3,1,2,0]

示例 3：

输入：queries = [7,5,5,8,3], m = 8
输出：[6,5,0,7,5]

 

提示：

• 1 <= m <= 10^3
• 1 <= queries.length <= m
• 1 <= queries[i] <= m

class Solution {
    public int[] processQueries(int[] queries, int m) {
        int l = queries.length + m;
        FenwickTree fenwickTree = new FenwickTree(l);
        int[] numPos = new int[m+1];
        for (int i = queries.length + 1; i <= l; i++) {
            fenwickTree.add(i,1);
            numPos[i - queries.length] = i;
        }

        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int num = queries[i];
            res[i] = fenwickTree.query(numPos[num]) - 1;
            fenwickTree.add(numPos[num],-1);
            numPos[num] = queries.length - i;
            fenwickTree.add(numPos[num],1);
        }
        return res;
    }

    class FenwickTree{
        int[] arr;

        public FenwickTree(int n){
            arr = new int[n+1];
        }

        public int lowBit(int i){
            return i & (-i);
        }

        public void add(int idx , int num){
            while (idx < arr.length){
                arr[idx] += num;
                idx += lowBit(idx);
            }
        }

        public int query(int idx){
            int sum = 0;
            while (idx > 0){
                sum += arr[idx];
                idx -= lowBit(idx);
            }
            return sum;
        }

    }
}