数组的改变和移动、二维数组及滚动数组、数组的旋转——LeetCode

一、数组的改变、移动

1、最小移动次数使数组元素相等（简单）

看题解后

方法一：排序

  每次移动都会使 n-1 个元素加 1，如果知道数组中的最大值 max，最小值 min。经过 max - min 次移动，可以使得 max = min。由于每次移动都会使 n-1 个元素加 1，所以移动后原数组中的次大值就成了最大值，需要再经过 max - min 次移动，使 max = min... 不断执行就可以使得数组中的所有数相同。

  我们可以先对数组进行排序，这样就能很容易确定数组中的，最大值，最小值，次大值... 每次都执行 max - min 次（这里的 max 是指每次移动后的最大值），用 nums[i] - nums[0] 计算 max - min 即可。

• 执行用时：14 ms, 在所有 Java 提交中击败了22.93%的用户
• 内存消耗：38.9 MB, 在所有 Java 提交中击败了77.37%的用户

class Solution {
    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            sum += nums[i] - nums[0];
        }
        return sum;
    }
}

方法二：优化方法一

  由方法一得，我们需要对数组中的数进行 nums[i] - nums[0]，而 nums[0] 是最小值。所以只需要计算出最小值 min，进行 nums[i] -min 即可。这样便能省去数组排序的时间。

• 执行用时：2 ms, 在所有 Java 提交中击败了86.10%的用户
• 内存消耗：38.9 MB, 在所有 Java 提交中击败了73.84%的用户

class Solution {
    public int minMoves(int[] nums) {
        int min = Integer.MAX_VALUE;
        for (int i : nums) {
            min = Math.min(min, i);
        }
        int sum = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            sum += nums[i] - min;
        }
        return sum;
    }
}

方法三：优化方法二

  因为 $a-i+b-i+...+c-i=(a+b+...+c)-i*n$，所以我们可以将方法二中的对数组的两次遍历优化成一次。

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.9 MB, 在所有 Java 提交中击败了78.24%的用户

class Solution {
    public int minMoves(int[] nums) {
        int min = Integer.MAX_VALUE;
        int sum = 0;
        for (int i : nums) {
            // 用 min = Math.min(min, i) 效率低
            if (i < min) {
                min = i;
            }
            sum += i;
        }
        return sum - min * nums.length;
    }
}

方法四：动态规划

  对于升序数组 nums，我们不考虑整个问题，而是将问题分解。假设，直到 i-1 位置的元素都相等，我们只需要考虑第 i 位的元素，那么经过 nums[i]-nums[i-1] 次移动，即可使得数组所有元素相等。由于每次移动都会使 n-1 个元素加 1，所以再进行下次 nums[i]-nums[i-1] 之前，需要为 nums[i] 加上之前所移动的次数（也就是移动所带来的增量）。

• 执行用时：14 ms, 在所有 Java 提交中击败了22.93%的用户
• 内存消耗：39.1 MB, 在所有 Java 提交中击败了47.37%的用户

public class Solution {
    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 1; i < nums.length; i++) {
            // 因为每次移动都会使 n-1 个元素加 1，所以后面的元素都需要加上之前移动的量
            nums[i] += sum;
            // 将 i 之前的所有元素，移动到和 i 相等。
            sum += nums[i] - nums[i - 1];
        }
        return sum;
    }
}

2、非递减数列（简单）

看题解后

方法一：分解子问题

  如果数组 nums 是非递减数列（一个升序的数组），需要满足 nums[i] <= nums[i+1]。遍历数组，如果发现 nums[i] > nums[i+1] 则需要对数组的元素进行改变：

• 当i = 0 时，则将nums[i] 改为任意一个小于等于nums[i+1] 的数即可。
• 当i != 0 时，如果更改nums[i] 值时，可能会影响到 i 之前的数的递增性：
  • 如果nums[i-1] <= nums[i+1]，则将nums[i] 改为nums[i-1]<= nums[i] <=nums[i+1] 即可。
  • 如果nums[i-1] > nums[i+1]，则将nums[i+1] 改为nums[i] 即可。

  此外，还需要一个变量记录当前是不是第二次进行改变。

• 执行用时：1 ms, 在所有 Java 提交中击败了99.77%的用户
• 内存消耗：39.8 MB, 在所有 Java 提交中击败了78.95%的用户

class Solution {
    public boolean checkPossibility(int[] nums) {
        // 记录是不是第一次进行改变
        boolean is = false;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (is) {
                    return false;
                }
                // 判断是不是第一个元素
                if (i != 0) {
                    // 如果 nums[i-1] > nums[i+1]，则将 nums[i+1] 改为 nums[i] 即可。
                    if (nums[i - 1] > nums[i + 1]) {
                        nums[i + 1] = nums[i];
                    } else {
                        // 如果 nums[i-1] <= nums[i+1]，则将 nums[i] 改为 nums[i-1]<= nums[i] <=nums[i+1] 即可。
                        nums[i] = nums[i + 1];
                    }
                } else {
                    // 当 i = 0 时，则将 nums[i] 改为任意一个小于等于 nums[i+1] 的数即可。
                    nums[i] = nums[i + 1];
                }
                is = true;
            }
        }
        return true;
    }
}

方法二：优化

  因为最多只能改变一个元素，所以 if (nums[i] > nums[i + 1]) 中的语句块最多执行一次，所以修改不修改 nums[i] 的值对今后的判断都不影响。

class Solution {
    public boolean checkPossibility(int[] nums) {
        // 记录是不是第一次进行改变
        boolean is = false;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                if (is) {
                    return false;
                }
                // 判断是不是第一个元素
                if (i != 0) {
                    // 如果 nums[i-1] > nums[i+1]，则将 nums[i+1] 改为 nums[i] 即可。
                    if (nums[i - 1] > nums[i + 1]) {
                        nums[i + 1] = nums[i];
                    } 
                } 
                is = true;
            }
        }
        return true;
    }
}

3、移动零（简单）

自己的想法

方法一：双指针

  使用两个指针，指针 zero 指向数组中的 0，指针 pointer 用来遍历数组。如果 nums[pointer] = 0，则不做处理，pointer 指针向后移动；如果为非 0，则和 zero 指向的数进行交换，两个指针都向后移动。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.8 MB, 在所有 Java 提交中击败了62.56%的用户

class Solution {
    public void moveZeroes(int[] nums) {
        // 零的指针
        int zero = 0;
        // 遍历数组的指针
        int pointer = 0;
        // 临时变量
        int tmp = 0;
        while (pointer < nums.length) {
            if (nums[pointer] == 0) {
                pointer++;
            } else {
                tmp = nums[pointer];
                nums[pointer++] = nums[zero];
                nums[zero++] = tmp;
            }
        }
    }
}

二、二维数组及滚动数组

1、杨辉三角（简单）

自己的想法（看题解后进行了优化）

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：36.4 MB, 在所有 Java 提交中击败了33.94%的用户

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> lists = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                // 如果为开头和结尾则添加 1
                if (j == 0 || j == i) {
                    list.add(1);
                } else {
                    // 将上一行的 j-1 + j 等于当前行的 j
                    list.add(lists.get(i - 1).get(j - 1) + lists.get(i - 1).get(j));
                }
            }
            lists.add(list);
        }
        return lists;
    }
}

2、杨辉三角 II（简单）

看题解后

  建议先写会 118 题再来写这个题，因为这个题是它的进阶。这个题最坑的地方就是：{1} 是第零行，{1,1} 是第一行（刚刚从 118 题过来踩了坑）。

  题目要求使用 O(k) 的空间复杂度，所以我们只能创建一个集合。我们知道第 i 行的第 j 个数的值，是 i-1 行的中 j-1 和 j 值的和。由于我们只有一个集合，所以需要不断的覆盖，所以第 j 个数的值等于前一个值加上当前值的和。因为集合中的值是不断覆盖，所以我们获取到的前一个值并不是我们想要的（因为上次循环把覆盖了）。有两种解决办法：

1. 创建一个中间变量记录前一个值（不推荐）；
2. 逆序构造每一行（代码如下）。

• 执行用时：1 ms, 在所有 Java 提交中击败了79.12%的用户
• 内存消耗：36.2 MB, 在所有 Java 提交中击败了70.72%的用户

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        for (int i = 0; i < rowIndex; i++) {
            for (int j = i; j >= 1; j--) {
                list.set(j, list.get(j - 1) + list.get(j));
            }
            list.add(1);
        }
        return list;
    }
}

3、图片平滑器（简单）

看题解后

  刚开始连题都没读懂，看来了会儿题解才理解题意。题意：对于矩阵中的每一个单元格，向周围八个方向扩展一格，构成一个 3*3 的二维矩阵（如果周围的单元格不足八个，则尽可能多的利用它们）。然后统计各个单元格中的值，除以单个格的个数，就是当前单元格的值。

方法一：暴力破解

  创建一个同样大的二维矩阵来存储重新构建的值。遍历矩阵中的每个单元格，并统计当前单元格周围的值，除以单个格的个数，将结果赋给新的二维矩阵中的指定位置。

• 执行用时：9 ms, 在所有 Java 提交中击败了62.59%的用户
• 内存消耗：39.4 MB, 在所有 Java 提交中击败了79.12%的用户

class Solution {
    public int[][] imageSmoother(int[][] M) {
        int n = M.length;
        int m = M[0].length;
        int[][] result = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 记录当前有几个数（除数）
                int count = 0;
                // 构造遍历周围的八个单元格
                for (int ii = i - 1; ii <= i + 1; ii++) {
                    for (int jj = j - 1; jj <= j + 1; jj++) {
                        // 判断下标是否越界
                        if (ii >= 0 && ii < n && jj >= 0 && jj < m) {
                            result[i][j] += M[ii][jj];
                            count++;
                        }
                    }
                }
                result[i][j] /= count;
            }
        }
        return result;
    }
}

方法二：暴力破解（优化）

• 执行用时：4 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：39.4 MB, 在所有 Java 提交中击败了79.55%的用户

class Solution {
    public int[][] imageSmoother(int[][] M) {
        int n = M.length, m = M[0].length;
        int[][] result = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result[i][j] = arg(j, i, M);
            }
        }
        return result;
    }

    private int arg(int x, int y, int[][] M) {
        int maxX = M[0].length - 1;
        int maxY = M.length - 1;
        // 该窗口的元素个数（包含自己）
        int count = 1;
        // 计算窗口所有元素之和，先加上自己
        int sum = M[y][x];
        // 加上左上角的邻居
        if (y > 0 && x > 0) {
            sum += M[y - 1][x - 1];
            count++;
        }
        // 加上上面的邻居
        if (y > 0) {
            sum += M[y - 1][x];
            count++;
        }
        // 加上右上角的邻居
        if (y > 0 && x < maxX) {
            sum += M[y - 1][x + 1];
            count++;
        }
        // 加上右边的邻居
        if (x < maxX) {
            sum += M[y][x + 1];
            count++;
        }
        // 加上右下角的邻居
        if (y < maxY && x < maxX) {
            sum += M[y + 1][x + 1];
            count++;
        }
        // 加上下面的邻居
        if (y < maxY) {
            sum += M[y + 1][x];
            count++;
        }
        // 加上左下角的邻居
        if (y < maxY && x > 0) {
            sum += M[y + 1][x - 1];
            count++;
        }
        // 加上左边的邻居
        if (x > 0) {
            sum += M[y][x - 1];
            count++;
        }
        // 计算窗口的均值
        return sum / count;
    }
}

4、范围求和 II（简单）

自己的想法

方法一：统计最小的 a 和 b，相乘就是矩阵中含有最大整数的元素个数。需要注意是，如果矩阵 ops 长度为 0，则最大整数的元素个数是 m*n（最大元素是 0）。

• 执行用时：1 ms, 在所有 Java 提交中击败了74.11%的用户
• 内存消耗：38.7 MB, 在所有 Java 提交中击败了47.23%的用户

public class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        for (int[] op : ops) {
            m = Math.min(m, op[0]);
            n = Math.min(n, op[1]);
        }
        return m * n;
    }
}

方法二：自己用 if 语句判断比 Math.min 效率高

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.2 MB, 在所有 Java 提交中击败了91.78%的用户

public class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        for (int[] op : ops) {
            if (m > op[0]){
                m = op[0];
            }
            if (n > op[1]){
                n = op[1];
            }
        }
        return m * n;
    }
}

5、甲板上的战舰（中等）

自己的想法

方法一：DFS

  遍历矩阵，每找到一个 X（战舰）进行计数，并将其相邻的 X 改为 . 。

• 执行用时：1 ms, 在所有 Java 提交中击败了99.82%的用户
• 内存消耗：37.8 MB, 在所有 Java 提交中击败了94.18%的用户

class Solution {
    public int countBattleships(char[][] board) {
        int count = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'X') {
                    count++;
                    board[i][j] = '.';
                    int a = i + 1;
                    int b = j;
                    // 遍历行
                    while (a < board.length && board[a][b] == 'X') {
                        board[a++][b] = '.';
                    }
                    a = i;
                    b = j + 1;
                    // 遍历列
                    while (b < board[0].length && board[a][b] == 'X') {
                        board[a][b++] = '.';
                    }
                }
            }
        }
        return count;
    }
}

看题解后

方法二：寻找战舰头

  由于战舰只能水平或者垂直放置，所以战舰头的左边和上边一定不是 X。

• 执行用时：1 ms, 在所有 Java 提交中击败了99.82%的用户
• 内存消耗：38 MB, 在所有 Java 提交中击败了84.00%的用户

class Solution {
    public int countBattleships(char[][] board) {
        int count = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 判断是否是战舰头，要防止越界
                if (board[i][j] == 'X' && (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')) {
                    count++;
                }
            }
        }
        return count;
    }
}

6、乐团站位（简单）

方法一：等差数列

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：35.1 MB, 在所有 Java 提交中击败了100.00%的用户

class Solution {

    public int orchestraLayout(int num, int xPos, int yPos) {
        long numLong = num;
        // 第几环，如果当前行大于 num 的一半，
        long ring = ring(numLong, xPos, yPos);
        // 环的开头Value
        long start = 0;
        // 求出环的开头下标
        if (ring > 0) {
            start = (4 * ring) % 9 * (numLong - ring) % 9;
        }
        start++;
        // 计算对角坐标
        long diagonally = numLong - ring - 1;
        // 根据上三角和下三角做不同的判断
        long result;
        // 判断当前下标在上三角还是下三角
        if (xPos == ring || yPos == diagonally) {
            result = (start + xPos + yPos - ring * 2) % 9;
        } else {
            result = (start + diagonally * 2 - ring * 2 + (diagonally * 2 - xPos - yPos)) % 9;
        }
        if (result == 0) {
            return 9;
        }
        return (int) result;
    }

    // 求当前下标在第几环
    int ring(long num, long xPos, long yPos) {
        // xPos + 1 > (num + 1) / 2 判断下标是上半区还是下半区
        xPos = xPos + 1 > (num + 1) / 2 ? num - 1 - xPos : xPos;
        yPos = yPos + 1 > (num + 1) / 2 ? num - 1 - yPos : yPos;
        return (int) Math.min(xPos, yPos);
    }
}

三、数组的旋转

1、旋转数组（中等）

自己的想法

方法一：使用额外空间

  创建新的数组存储移动后的值，然后重新拷贝到原数组中。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.8 MB, 在所有 Java 提交中击败了93.40%的用户

class Solution {
    public void rotate(int[] nums, int k) {
        int[] array = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            // 防止下标越界
            array[(i + k) % nums.length] = nums[i];
        }
        System.arraycopy(array, 0, nums, 0, nums.length);
    }
}

看题解后

方法二：环状替换

  如果我们不使用额外数组，又要将当前元素（start）一次移动到指定位置。那么我们需要保存被覆盖的值。再计算这个被覆盖的值应该存放的位置，依次执行相同的操作，直到回到元素 start 即可。

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：39.1 MB, 在所有 Java 提交中击败了66.06%的用户

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        // 统计移动数的个数
        int count = 0;
        // 所有数都移动过则结束循环
        for (int start = 0; count < nums.length; start++) {
            int pointer = start;
            // 保存当前元素的值
            int value = nums[pointer];
            do {
                // 计算下一次移动的下标
                pointer = (pointer + k) % nums.length;
                // 向后移动，并保存覆盖的值
                int tmp = nums[pointer];
                nums[pointer] = value;
                value = tmp;
                count++;
                // 如果相等表示回到了起点
            } while (pointer != start);
        }
    }
}

方法三：数组反转

  对原数组进行三次反转即可，例如：

1. 原始数组：1 2 3 4 5 6 7
2. 反转所有数字后：7 6 5 4 3 2 1
3. 反转前 k 个数字后：5 6 7 4 3 2 1
4. 反转后 n-k 个数字后：5 6 7 1 2 3 4 --> 结果

• 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：39.1 MB, 在所有 Java 提交中击败了64.39%的用户

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reversal(0, nums.length - 1, nums);
        reversal(0, k - 1, nums);
        reversal(k, nums.length - 1, nums);
    }

    public void reversal(int left, int right, int[] nums) {
        int tmp;
        while (left < right) {
            tmp = nums[right];
            nums[right--] = nums[left];
            nums[left++] = tmp;
        }
    }
}

2、旋转函数（中等）

自己的想法

方法一：暴力破解（超时）

class Solution {
    public int maxRotateFunction(int[] A) {
        if (A.length == 0) {
            return 0;
        }
        // 统计最大值
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < A.length; i++) {
            // 统计每次的和
            int sum = 0;
            // 从第二个开始加
            int count = 1;
            // 计算下一个的下标
            int ii = (i + 1) % A.length;
            while (ii != i) {
                sum += count++ * A[ii++];
                ii %= A.length;
            }
            max = Math.max(max, sum);
        }
        return max;
    }
}

看题解后

方法二：错位相减

F(k) = 0 * A[0] + 1 * A[1] + ... + (n-1) * A[n-1]；

F(k+1) = 0 * A[n-1] + 1 * A[0] + 2 * A[1] + ... + (n-1) * A[n-2]；

F(k+1) - F(k) = -(n-1) * A[n-1] + 1 * A[0] + 1 * A[1] + ... + 1 * A[n-2]；

F(k+1) = F(k) - n * A[n-1] + 所有数的和;

F(k+i) = F(k+i-1) - n * A[n-i] + 所有数的和。

• 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗：38.7 MB, 在所有 Java 提交中击败了74.78%的用户

class Solution {
    public int maxRotateFunction(int[] A) {
        int n = A.length;
        int max = 0;
        int count = 0;
        // 统计数组所有数的和
        int sum = 0;
        // 计算 F(1) 的值
        for (int i : A) {
            max += count++ * i;
            sum += i;
        }
        // 记录上一个计算结果
        int tmp = max;
        for (int i = 1; i < n; i++) {
            // 利用等差数列求解
            tmp = tmp + sum - n * A[n - i];
            if (max < tmp) {
                max = tmp;
            }
        }
        return max;
    }
}