刷题「数组与矩阵」相关

把数组中的0移到末尾（简单）

暴力解法就不说了。下面介绍下双指针的思路。

现在的思路就是我们假想又开辟了一个新的数组，但是这个新数组和原数组占用同一片空间。也就是我们让原数组具有「双重人格」。一会表示原数组，一会表示我们假想的新数组。

新数组的内容为原数组中的非零元素。并保持相对顺序。由指针lastNonZeroFoundAt来控制新数组。

两个指针，一个用来遍历原数组，一个lastNonZeroFoundAt用来操作新数组，初始值为0。

程序开始，当我们遍历到一个非零元素就将该元素赋值给nums[lastNonZeroFoundAt]，然后lastNonZeroFoundAt ++。

最后，将新数组的非零元素后面填充0。这里我们并没有将0移动，我们移动的是非零元素。所以将非零元素移到前面以后，后面的就是0。

class Solution {
    public void moveZeroes(int[] nums) {
        int lastNonZeroFoundAt = 0;

        for (int i = 0; i < nums.length; ++ i) {
            if (nums[i] != 0) {
                nums[lastNonZeroFoundAt] = nums[i];
                lastNonZeroFoundAt ++;
            }
        }

        for (int i = lastNonZeroFoundAt; i < nums.length; ++ i) {
            nums[i] = 0;
        }
    }
}

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(1)。

在此基础上在简便一点。我们同时移动非零元素和0。

同样是两个指针。现在一个快一个慢。当快的遇到非零元素时就和慢的交换元素。

class Solution {
    public void moveZeroes(int[] nums) {
        for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.length; ++ cur) {
            if (nums[cur] != 0) {
                int t = nums[lastNonZeroFoundAt];
                nums[lastNonZeroFoundAt] = nums[cur];
                nums[cur] = t;
                lastNonZeroFoundAt ++;
            }
        }
    }
}

复杂度分析：

时间复杂度：O(n)。

空间复杂度：O(1)。

改变矩阵维度（简单）

简单的方法是，通过一个队列来将数组内容全部取出，然后再按照要求填入到新数组中。这个方法我就不写代码了，很容易想到。

除了上述方法，我们还可以通过控制数组下标来解决这个问题。我们引入一个新的变量count。

class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        int m, n;
        m = nums.length;;
        n = nums[0].length;
        if (m * n != r * c || m == 0) {
            return nums;
        }

        int[][] res = new int[r][c];
        int count = 0;
        for (int i = 0; i < m; ++ i) {
            for (int j = 0; j < n; ++ j) {
                res[count / c][count % c] = nums[i][j];
                count ++;
            }
        }
        return res;
    }
}

复杂度分析：

时间复杂度：O(m * n)。

空间复杂度：O(m * n)。

找出数组中最长的连续 1（简单）

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int maxCount = 0, count = 0;

        for (int i = 0; i < nums.length; ++ i) {
            if (nums[i] == 1) {
                count ++;
            } else {
                maxCount = Math.max(count, maxCount);
                count = 0;
            }
        }
        return Math.max(count, maxCount);
    }
}