原地算法(数组向)

一.原地算法简单介绍

1.案例引入

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

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

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

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

        那么，按照题目要求，数组是同时更新的，肯定不能先按照规则更新其中一个，然后将新更新的值带入再进行更新。 

2.原地算法

        在上述案例中，如果使用深拷贝，问题将很容易解决，但一是耗费空间较大，二是如果在面试中，这种类型的题目肯定是想让你使用原地算法。

        原地算法，即不占用额外空间（少量占用），在不改变原本数据附带的信息的条件下，为数据附上新的信息。要注意，不是不改变原本的值，是不改变原本的值所附带的信息。

        而有些题目的要求原地算法是一种要求，而不是像回溯或者动态规划这种问题的具体解法。

3.相关技巧

        那么，在生命游戏的案例中，1代表活细胞，0代表死亡细胞，那么，为数据附上新的信息，用2代表活细胞。但是，2同时代表此细胞是过去死亡，现在活着，即2承载了两个信息，一是此细胞活着，二是此细胞之间死亡，由于生存定律的第四条，它活了。那么用-1来代表此细胞是死亡的，但是，它过去是活的。 那么，现在细胞共有4种状态：

        -1（死亡，之前活），0（死亡），1（活的），2（活的，之前死）。

        总之就是在不改变数据原本附带的信息的状况下，为数据附加上新的信息，也可以理解为复合状态。当然，既然是原地，意味着有时候要根据题目要求进行状态回溯，根据新状态推出最后的结果。本质上相较于深拷贝是用时间换空间。

二.leetcode实战

1.leetcode73 矩阵置零

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

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

此题若使用O(MN)空间复杂度，那肯定不是出题者想要考察的目的，要在O(M+N)的基础上思考O（1）的解决方案。

O(M+N) 

class Solution {
    public void setZeroes(int[][] matrix) {
        Set row_zero = new HashSet<>();
        Set col_zero = new HashSet<>();
        int row = matrix.length;
        int col = matrix[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 0) {
                    row_zero.add(i);
                    col_zero.add(j);
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (row_zero.contains(i) || col_zero.contains(j)) matrix[i][j] = 0;
            }
        }  
    }
}

用HashSet保留出现的0的行与列，O(M+N) 

O(1) 

class Solution {
    public void setZeroes(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        boolean row0_flag = false;
        boolean col0_flag = false;
        for(int j = 0; j < col; j++){
            if(matrix[0][j] == 0){
                row0_flag = true;
                break;
            }
        }
        for(int i = 0; i < row; i++){
            if(matrix[i][0] == 0){
                col0_flag = true;
                break;
            }
        }
        for(int i = 1; i < row; i++){
            for(int j = 1; j < col; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for(int i = 1; i < row; i++){
            for(int j = 1; j < col; j++){
                if(matrix[i][0] == 0 || matrix[0][j] == 0){
                    matrix[i][j] = 0;
                } 
            }
        }
        if(row0_flag){
            for(int j = 0; j < col; j++){
                matrix[0][j] = 0;
            }
        }
        if(col0_flag){
            for(int i = 0; i < row; i++){
                matrix[i][0] = 0;
            }
        }
    }
}

本题小结：（1）用首行首列保存信息

                  （2）首行首列单独判断

2.leetcode223 生命游戏

参考案例引入

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

class Solution {
    public void gameOfLife(int[][] board) {
        int[] neighbors = {0,-1,1};
        int rows = board.length;
        int cols = board[0].length;
        int[][] copyBoard = new int[rows][cols];
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                copyBoard[i][j] = board[i][j];
            }
        }
        for(int row = 0; row < rows; row++){
            for(int col = 0; col < cols; col++){
                int live = 0;
                for(int i = 0; i < 3; i++){
                    for(int j = 0; j < 3; j++){
                        if(!(i == 0 && j == 0)){
                            int r = row+neighbors[i];
                            int c = col+neighbors[j];
                            if((r < rows && r >= 0) && (c < cols && c >=0) && (copyBoard[r][c]==1)){
                            live++;
                        }
                        }
 
                    }
                }
            if((copyBoard[row][col] == 1) && (live < 2 || live > 3)){
                board[row][col] = 0;
            }
            if(copyBoard[row][col] == 0 && live == 3){
                board[row][col] = 1;
            }
            }
        }
    }
}

        思路很简单，直接完全深拷贝原数组，查看时看复制的数组，而改动的时候直接改原数组。

原地算法【2】

class Solution {
    public void gameOfLife(int[][] board) {
        int[] neighbors = {0, 1, -1};
 
        int rows = board.length;
        int cols = board[0].length;
 
        // 遍历面板每一个格子里的细胞
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
 
                // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                int liveNeighbors = 0;
 
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
 
                        if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
                            // 相邻位置的坐标
                            int r = (row + neighbors[i]);
                            int c = (col + neighbors[j]);
 
                            // 查看相邻的细胞是否是活细胞
                            if ((r < rows && r >= 0) && (c < cols && c >= 0) && (Math.abs(board[r][c]) == 1)) {
                                liveNeighbors += 1;
                            }
                        }
                    }
                }
 
                // 规则 1 或规则 3 
                if ((board[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    // -1 代表这个细胞过去是活的现在死了
                    board[row][col] = -1;
                }
                // 规则 4
                if (board[row][col] == 0 && liveNeighbors == 3) {
                    // 2 代表这个细胞过去是死的现在活了
                    board[row][col] = 2;
                }
            }
        }
 
        // 遍历 board 得到一次更新后的状态
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (board[row][col] > 0) {
                    board[row][col] = 1;
                } else {
                    board[row][col] = 0;
                }
            }
        }
    }
}

本题小结（1） 方向的遍历技巧-生成方向数组，本题因为是8方向遍历，生成一个int[] neighbors = {0, 1, -1}即可，并且注意过滤掉（0,0）点，因为是以此点进行顾虑。

              （2） 用-1（死亡，之前活）表示很巧妙，这样，绝对值即可表示之前活的状态

              （3）最后不要忘记状态回溯

3.leetcode189 轮转数组

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

        输入: nums = [1,2,3,4,5,6,7], k = 3
        输出: [5,6,7,1,2,3,4]
        解释:
        向右轮转 1 步: [7,1,2,3,4,5,6]
        向右轮转 2 步: [6,7,1,2,3,4,5]
        向右轮转 3 步: [5,6,7,1,2,3,4]

两倍数组法：

class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k = k % len;
        int[] new_arr = new int[len*2];
        for(int i = 0; i < len; i++){
            new_arr[i] = nums[i];
        }
        for(int i = len; i < len*2; i++){
            new_arr[i] = nums[i-len];
        }
        for(int i = 0; i < len; i++){
            nums[i] = new_arr[i+len-k];
        }
    }
}

官方环状拷贝【4】

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }
}

两次反转法【5】​​​​​​​

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}

 

参考来源【1】leetcode289 生命游戏

              【2】leetcode289 生命游戏leetcode官方解题

              【3】leetcode73 矩阵置零  powcai O(1)空间

              【4】leetcode189 官方题解 

              【5】leetcode 御三五 【数组翻转】旋转数组