代码随想录算法训练营第2天

今日任务

977.有序数组的平方，209.长度最小的子数组，59.螺旋矩阵II ，总结。

链接：https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG (opens in a new tab)

977.有序数组的平方

自己想法

相向双指针：

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0, right = nums.length - 1;
        int[] result = new int[nums.length];
        int index = nums.length - 1;
        while (left <= right) {
            if (Math.abs(nums[left]) > Math.abs(nums[right])) {
                result[index] = nums[left] * nums[left];
                index --;
                left ++;
            }
            else {
                result[index] = nums[right] * nums[right];
                index --;
                right --;
            }
        }
        return result;
    }
}

题解想法

略

困难

无

回顾

注意不能写成以下写法，即不能简单地交换left和right，否则[-5,-3,-2,-1] 这种情况会出错。

另外以下代码还有一处冗余，因为把while条件改为<=就不需要再额外判断left和right是否相等了。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left = 0, right = nums.length - 1;
        int[] result = new int[nums.length];
        int index = nums.length - 1;
        while (left < right) {
            if (Math.abs(nums[left]) > Math.abs(nums[right])) {
                result[index] = nums[left] * nums[left];
                index --;
                result[index] = nums[right] * nums[right];
                index --;
            }
            else {
                result[index] = nums[right] * nums[right];
                index --;
                result[index] = nums[left] * nums[left];
                index --;
            }
            left ++;
            right --;
        }
        if (left == right) {
            result[index] = nums[left] * nums[left];
            index --;
        }
        return result;
    }
}

209.长度最小的子数组

自己想法

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int start = 0;
        int min_sub = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum >= target) {
                if (min_sub == 0) {  // 第一次找到
                    min_sub = i - start + 1;
                    start = 0;
                }
                while (sum >= target) {
                    int now_sub = i - start + 1;
                    min_sub = Math.min(now_sub, min_sub);
                    sum -= nums[start];
                    start ++;
                }
            }
        }
        return min_sub;
    }
}

题解想法

无

困难

无

回顾

无

59.螺旋矩阵II

自己想法

class Solution {
    public int[][] generateMatrix(int n) {
        int index = 1;
        int direct = 0; //0, 1, 2, 3
        int loop = 0;
        int[][] ans = new int[n][n];
        while (index < n * n) {
            if (direct == 0) {
                // right
                for (int i = loop; i < n - loop - 1; i++) {
                    ans[loop][i] = index;
                    index ++;
                }
            }
            else if (direct == 1) {
                // down
                for (int i = loop; i < n - loop - 1; i++) {
                    ans[i][n - loop - 1] = index;
                    index ++;
                }
            }
            else if (direct == 2) {
                // left
                for (int i = n - loop - 1; i > loop; i--) {
                    ans[n - loop - 1][i] = index;
                    index ++;
                }
            }
            else if (direct == 3) {
                // up
                for (int i = n - loop - 1; i > loop; i--) {
                    ans[i][loop] = index;
                    index ++;
                }
                loop ++;
            }
            direct = (direct + 1) % 4;
        }
        if (n % 2 == 1) {
            ans[loop][loop] = index;
        }
        else {
            ans[n- loop -1][loop] = index;
        }
        return ans;
    }
}

题解想法

待看

困难

无

回顾

n是奇数偶数时各有注意点：

奇数时，最后是1*1的方格，不能放在循环里，否则会被无限跳过。需要在外面单独处理。因此循环的条件是index < n * n。
偶数时，本来没有问题，但是由于循环条件是index < n * n，因此会少一个数，也需要在外面单独处理。