Leetcode-数组刷题记录

数组的遍历

485. 最大连续1的个数

public int findMaxConsecutiveOnes(int[] nums) {
        //res存储最长的子数组
        int res = 0;
        //count记录的是每个被0隔断的子数组
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            //如果当前元素是1，更新当前子数组的长度
            if(nums[i] == 1){
                count++;
            }else {
                //遇到0，比较res, count的大小，并将count重置为0
                res = Math.max(res, count);
                count = 0;
            }
        }
        //避免最后一个子数组是最大的情况，例如：1,0,1,1,0,1,1,1,1
        return Math.max(res, count);
    }

495. 提莫攻击

public int findPoisonedDuration(int[] timeSeries, int duration) {
        int res = 0;
        for(int i = 0; i < timeSeries.length; i ++){
            //当前能持续的时间
            int time = timeSeries[i] + duration -1;
            //超过下一次攻击的时间
            if(i != timeSeries.length -1 && time >= timeSeries[i + 1]){
                res += (timeSeries[i + 1] - timeSeries[i]);
            }else{
                res += duration;
            }
        }
        return res;
    }

第三大的数

时间复杂度要求$O(n)$，也就是只能通过一趟遍历完成。

public int thirdMax(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        if(nums.length == 2){
            return nums[0] >= nums[1] ? nums[0] : nums[1];
        }
        long firstMax = Long.MIN_VALUE;
        long secondMax = Long.MIN_VALUE;
        long thirdMax = Long.MIN_VALUE;
    	//判断相等情况是避免相同数字,例如：[2, 2, 3, 1]
        for(int num : nums){
            if(num > firstMax) {
                thirdMax = secondMax;
                secondMax = firstMax;
                firstMax = num;
            }else if(num == firstMax) {
                continue;
            }else if(num > secondMax){
                thirdMax = secondMax;
                secondMax = num;
            }else if(num == secondMax) {
                continue;
            }else if(num > thirdMax){
                thirdMax = num;
            }
        }
        if(thirdMax == Long.MIN_VALUE){
            return (int)firstMax;
        }else{
            return (int) thirdMax;
        }
    }

628. 三个数的最大乘积

偷🐔解法，需要注意考虑负数的情况。

时间复杂度为$O(nlogN)$。

public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
                return Math.max(nums[0] * nums[1] * nums[nums.length - 1], 
                                nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3]);
    }

如果使用一趟遍历的方法，那么需要使用五个变量，分别保存最大的三个数，和最小的两个数。

统计数组中的元素

645. 错误的集合

public int[] findErrorNums(int[] nums) {
        int[] res = new int[2];
        int[] count = new int[nums.length];
        for(int num : nums){
            count[num - 1]++;
        }
        for(int i = 0; i< count.length;i++){
            if(count[i] == 2){
                res[0] = i + 1;
            }else if(count[i] == 0){
                res[1] = i + 1;
            }
        }
        return res;
    }

697. 数组的度

三个HashMap的作用分别如下：

• left：数字第一次出现的索引
• right：数字最后一次出现的索引
• count：数字出现的次数

public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> left = new HashMap(),
            right = new HashMap(), count = new HashMap();

        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            if (left.get(x) == null) left.put(x, i);
            right.put(x, i);
            count.put(x, count.getOrDefault(x, 0) + 1);
        }

        int ans = nums.length;
        int degree = Collections.max(count.values());
        for (int x: count.keySet()) {
            if (count.get(x) == degree) {
                ans = Math.min(ans, right.get(x) - left.get(x) + 1);
            }
        }
        return ans;
    }

448. 找到所有数组中消失的数字

HashMap做记录，再通过一轮遍历找到不存在的数字。

时间复杂度$O(n)$，空间复杂度$O(n)$。

public List<Integer> findDisappearedNumbers(int[] nums) {
        HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], true);
        }
        List<Integer> res = new LinkedList<Integer>();
        for (int i = 1; i <= nums.length; i++) {
            if (!map.containsKey(i)) {
                res.add(i);
            }
        }  
        return res;
    }

如果使用时间复杂度$O(n)$，并不用额外的空间，可以通过添加标记来解决。

一轮遍历添加标记：能标识该数字出现过。

第二轮遍历查找没有做标记的数字。

public List<Integer> findDisappearedNumbers(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int index = (nums[i] - 1) % nums.length;
            nums[index] += nums.length;
        }
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            if(nums[i] <= nums.length){
                res.add(i + 1);
            }
        }
        return res;
    }

442. 数组中重复的数据

与上面一题异曲同工。使用标记法。

public List<Integer> findDuplicates(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int index = (nums[i] - 1) % nums.length;
            nums[index] += nums.length;
        }
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > nums.length * 2){
                res.add(i + 1);
            }
        }
        return res;
    }

41. 缺失的第一个正数

通过索引交换元素。

public int firstMissingPositive(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            while((nums[i] >= 1 && nums[i] <= nums.length) && (nums[i] != nums[nums[i] - 1])){
                int temp = nums[i];
                nums[i] = nums[temp -1];
                nums[temp -1] = temp;
            }
        }
        int res = nums.length + 1;
        for(int i = 0; i < nums.length; i++){
            if (nums[i] != (i + 1)) {
                res = i + 1;
                break;
            }
        }
        return res;
    }

274. H指数

偷🐔了一下，直接sort解决。

public int hIndex(int[] citations) {
        int len = citations.length;
        Arrays.sort(citations);
        for(int i = 0; i < len; i++){
            int count = len - i;
            if(citations[i] >= count){
                return count;
            }
        }
        return 0;
    }

数组的改变、移动

453. 最小操作次数使数组元素相等

每次操作会使$n-1$个元素增加1 == > 每次操作让一个元素减去1

因此需要计算的次数就是：数组中所有元素（除去最小值）与最小值之间的差值。

（Python的API用的舒服）

def minMoves(self, nums):
        sum = 0
        minnum = min(nums)
        for i in nums:
            sum += i - minnum
        return sum

665. 非递减数列

拐点不能出现两次，修复会有两种情况：

• nums[i - 2] > nums[i]：将nums[i]改为nums[i - 1]
• nums[i - 2] <= nums[i]：将nums[i - 1]改为nums[i]

public boolean checkPossibility(int[] nums) {
        int count = 0;
        for(int i = 1 ; i< nums.length; i++){
            if(nums[i - 1] > nums[i]){
                count++;
                if(count >= 2) return false;
                if(i - 2 >= 0 && nums[i - 2] > nums[i]){
                    nums[i] = nums[i - 1];
                }else{
                    nums[i - 1] = nums[i];
                }
            }
        }
        return true;
}

283. 移动零

通过index存储有效位。

public void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[index++] = nums[i];
            }
        }
        while (index < nums.length) {
            nums[index++] = 0;
        }
    }

二维数组及滚动数组

118. 杨辉三角

public List<List<Integer>> generate(int numRows) {
       List<List<Integer>> ans = new ArrayList<List<Integer>>();
        for(int i = 0; i < numRows; i++){
            List<Integer> list = new ArrayList<>();
            list.add(1);
            for(int j = 1; j < i; j++){
                List<Integer> front = ans.get(i - 1);
                list.add(front.get(j) + front.get(j -1));
            }
            if(i > 0){
                list.add(1);
            }
            ans.add(list);
        }
        return ans;
    }

119. 杨辉三角Ⅱ

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

598. 范围求和Ⅱ

public int maxCount(int m, int n, int[][] ops) {
        int minX = m , minY = n;
        for(int i = 0; i < ops.length; i++){
            minX = Math.min(minX, ops[i][0]);
            minY = Math.min(minY, ops[i][1]);
        }
        return minX * minY;
    }

419. 甲板上的战舰

暴力判断：如果当前点是X，判断其左边和上边是否有X，没有则不连通，增加计数。

public int countBattleships(char[][] board) {
        int count = 0;
        for(int i = 0; i <board.length; i++){
            for(int j = 0; j < board[i].length; j++){
                if(board[i][j] == 'X'){
                    if(i > 0 && board[i - 1][j] == 'X' || j > 0 && board[i][j - 1] == 'X') continue;
                    count++;
                }
            }
        }
        return count;
    }

189. 数组的旋转

三轮reverse。

public void rotate(int[] nums, int k) {
        //如果数组长度小于旋转次数，那么执行k次和执行k % length次结果一样
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }

396. 旋转函数

可通过数学归纳法得到$F[k]= F[k-1] + sum - n*A[n-k]$

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];
            max = Math.max(tmp, max);
        }
        return max;
    }

特定顺序遍历二维数组

54. 螺旋矩阵

抓住两个index的变化趋势，按照规律变化就行。

public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        int up = 0, down = m - 1, left = 0, right = n -1;
        while(true){
            for(int i = left; i <= right; i++) res.add(matrix[up][i]);
            if(++up > down) break;
            for(int i = up; i <= down; i++) res.add(matrix[i][right]);
            if (--right < left) break;
            for(int i = right; i >= left; i--) res.add(matrix[down][i]);
            if (--down < up) break;
            for(int i = down; i >= up; i--) res.add(matrix[i][left]);
            if(++left > right) break;
        }
        return res;
    }

59. 螺旋矩阵Ⅱ

和上题一样。

public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int up = 0, down = n - 1, left = 0, right = n -1;
        int num = 1;
        while(true){
            for(int i = left; i <= right; i++) matrix[up][i] = num++;
            if(++up > down) break;
            for(int i = up; i <= down; i++) matrix[i][right] = num++;
            if (--right < left) break;
            for(int i = right; i >= left; i--) matrix[down][i] = num++;
            if (--down < up) break;
            for(int i = down; i >= up; i--) matrix[i][left] = num++;
            if(++left > right) break;
        }
        return matrix;
    }

498. 对角线遍历

二维数组变换

566. 重塑矩阵

笨方法，放入队列中，然后逐个按序取出。

public int[][] matrixReshape(int[][] nums, int r, int c) {
        int[][] res = new int[r][c];
        if (nums.length == 0 || r * c != nums.length * nums[0].length)
            return nums;
        int count = 0;
        Queue <Integer> queue = new LinkedList < > ();
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[0].length; j++) {
                queue.add(nums[i][j]);
            }
        }
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                res[i][j] = queue.remove();
            }
        }
        return res;
    }

原地算法：

• $count$用于保存当前到第几个元素
• $count / c$用于计算当前是第几行，$count % c$用于计算当前是第几个。

public int[][] matrixReshape(int[][] nums, int r, int c) {
        int[][] res = new int[r][c];
        if (nums.length == 0 || r * c != nums.length * nums[0].length)
            return nums;
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[0].length; j++) {
                res[count / c][count % c] = nums[i][j];
                count++;
            }
        }
        return res;
    }