代码随想录day02-Toy模板网

这篇具有很好参考价值的文章主要介绍了代码随想录day02。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

977.有序数组的平方

● 力扣题目链接
● 给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

思路

● 暴力排序，时间复杂度O(n + nlogn)
● 使用双指针，时间复杂度O(n)

代码

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length]; // 返回的数组，这个题目没法原地修改
        int l = 0; int r = nums.length -1;
        for (int i = res.length - 1; i >= 0; i--) { // 遍历返回的数组，每个元素都要放到适合的位置
            if (nums[l] * nums[l] > nums[r] * nums[r]) {
                res[i] = nums[l] * nums[l]; // 左边大
                l++; // 左指针右移
            } else {
                res[i] = nums[r] * nums[r]; // 右边大
                r--; // 右指针左移
            }
        }
        return res;
    }
}
// 思路一样，换成while循环
class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length];
        int l = 0; int r = nums.length - 1;
        int index = nums.length - 1;
        while (l <= r) {
            if (nums[l] * nums[l] > nums[r] * nums[r]) {
                res[index--] = nums[l] * nums[l];
                l++;
            } else {
                res[index--] = nums[r] * nums[r];
                r--;
            }
        }
        return res;
    }
}

209.长度最小的子数组

● 力扣题目链接
● 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
思路
● 可以暴力解法，外层循环遍历数组，内层不断往后看，更新长度的最小值
● 也可以使用滑动窗口
○ 外层循环遍历数组，不断移动快指针，加到sum
○ 一旦发现超过target，就开始移动慢指针，更新res，减去元素
○ 最后看res是否更新过

代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int s = 0; int sum = 0; int res = Integer.MAX_VALUE;
        for (int f = 0; f < nums.length; f++) { // 外层循环遍历数组
            sum += nums[f];
            while (sum >= target) { // 一旦超过target
                res = Math.min(res, f - s + 1); // 更新res
                sum -= nums[s++]; // 移动慢指针，减去元素
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res; // 看res是否更新过
    }
}

59.螺旋矩阵II

● 力扣题目链接
● 给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

思路

● 设置四个边界，不断循环处理

代码

class Solution {
    public int[][] generateMatrix(int n) {
        int l = 0, r = n - 1, b = 0, t = n - 1, num = 0, tar = n * n;
        int[][] res = new int[n][n];
        while (num < tar) {
            for (int i = l; i <= r; i++) {
                res[b][i] = ++num;
            }
            b++;
            for (int i = b; i <= t; i++) {
                res[i][r] = ++num;
            }
            r--;
            for (int i = r; i >= l; i--) {
                res[t][i] = ++num;
            }
            t--;
            for (int i = t; i >= b; i--) {
                res[i][l] = ++num;
            }
            l++;
        }
        return res;
    }
}

54.螺旋矩阵

● 给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

思路

● 和上一题类似，但是需要注意给集合中加元素不要重复

代码

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int l = 0, m = matrix.length - 1, b = 0, n = matrix[0].length - 1;
        int r = n, t = m, num = 1;
        List<Integer> res = new ArrayList();
        while (num <= (m + 1) * (n + 1)) {
            for (int i = l; i <= r && num <= (m + 1) * (n + 1); i++) { // 这步判断尽量写上
                res.add(matrix[b][i]);
                num++;
            }
            b++;
            for (int i = b; i <= t && num <= (m + 1) * (n + 1); i++) {
                res.add(matrix[i][r]);
                num++;
            }
            r--;
            for (int i = r; i >= l && num <= (m + 1) * (n + 1); i--) {
                res.add(matrix[t][i]);
                num++;
            }
            t--;
            for (int i = t; i >= b && num <= (m + 1) * (n + 1); i--) {
                res.add(matrix[i][l]);
                num++;
            }
            l++;
        }
        return res;
    }
}

剑指 Offer 29.顺时针打印矩阵

● 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

思路

● 与之前思路类似文章来源地址https://www.toymoban.com/news/detail-639851.html

代码

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return new int[0];
        int m = matrix.length;
        int n = matrix[0].length;
        int[] res = new int[m * n];
        int index = 0, l = 0, r = n - 1, b = 0, t = m - 1;
        while (index <= res.length - 1) {
            for (int i = l; i <= r && index <= res.length - 1; i++) {
                res[index++] = matrix[b][i];
            }
            b++;
            for (int i = b; i <= t && index <= res.length - 1; i++) {
                res[index++] = matrix[i][r];
            }
            r--;
            for (int i = r; i >= l && index <= res.length - 1; i--) {
                res[index++] = matrix[t][i];
            }
            t--;
            for (int i = t; i >= b && index <= res.length - 1; i--) {
                res[index++] = matrix[i][l];
            }
            l++;
        }
        return res;
    }
}