您现在的位置是：首页 >技术教程 >代码随想录算法训练营第二天 | 977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II，总结网站首页技术教程

代码随想录算法训练营第二天 | 977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II，总结

Jesus_night 2024-09-16 00:01:03
简介代码随想录算法训练营第二天 | 977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II，总结

977.有序数组的平方

977.有序数组的平方

条件：非递减顺序(严格递增顺序)

  • Java代码

    • 双指针
      有序数组的平方-双指针
    class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length];
        // Arrays.sort(nums);       // 题目上只是 非递减顺序 ， 可能是无序的，最好进行排序(虽然不进行排序也能通过)

        int left=0, right=nums.length-1;
        int index=nums.length-1;
        while (left<=right) {
            if (nums[left]*nums[left]>nums[right]*nums[right]) {
                res[index--]=nums[left]*nums[left];
                left++;
            } else {
                res[index--]=nums[right]*nums[right];
                right--;
            }
        }

        return res;
    }
}

    时间复杂度:O(n)
    空间复杂度:O(n)

    • 暴力法(调用排序库)
    class Solution {
    public int[] sortedSquares(int[] nums) {
        for (int i=0; i<nums.length; i++) {
            nums[i] = nums[i]*nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

    时间复杂度:O(n+nlogn)
    空间复杂度:O(1)

    • 完整代码
    package topic1Array;

/*977. 有序数组的平方

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

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/squares-of-a-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

public class topic3_977 {
    public static void main(String[] args) {
        Solution solution = new topic3_977().new Solution();
        int[] nums = {-4,-1,0,3,10};
        PublicAPI.printArray(nums);
        int[] res = solution.sortedSquares(nums);
        PublicAPI.printArray(res);
    }
    // 双指针法
    class Solution {
        public int[] sortedSquares(int[] nums) {
            int[] res = new int[nums.length];
            // Arrays.sort(nums);       // 题目上只是 非递减顺序 ， 可能是无序的，最好进行排序(虽然不进行排序也能通过)

            int left=0, right=nums.length-1;
            int index=nums.length-1;
            while (left<=right) {
                if (nums[left]*nums[left]>nums[right]*nums[right]) {
                    res[index--]=nums[left]*nums[left];
                    left++;
                } else {
                    res[index--]=nums[right]*nums[right];
                    right--;
                }
            }

            return res;
        }
    }
    /*// 暴力法(调用排序库)
    class Solution {
        public int[] sortedSquares(int[] nums) {
            for (int i=0; i<nums.length; i++) {
                nums[i] = nums[i]*nums[i];
            }
            Arrays.sort(nums);
            return nums;
        }
    }*/
}

209. 长度最小的子数组

209.长度最小的子数组

滑动窗口法
长度最小的子数组-滑动窗口法

  • 在本题中实现滑动窗口，主要确定如下三点：
    1. 窗口内是什么？
    2. 如何移动窗口的起始位置？
    3. 如何移动窗口的结束位置？

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

  • Java代码

    • 滑动窗口法(需要维护窗口的长度)
    class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLen = Integer.MAX_VALUE;
        int sum = 0;
        int pre=0, cur=0;
        for (; cur<nums.length; cur++) {
            sum+=nums[cur];
            while (sum>=target) {       // 满足条件就更新最小长度，并维护滑动窗口的总和小于 target
                minLen = minLen < cur-pre+1 ? minLen : cur-pre+1;
                sum-=nums[pre];
                pre++;
            }
        }
        return minLen != Integer.MAX_VALUE ? minLen : 0;
    }
}

    时间复杂度:O(n) 实际是O(2n)
    空间复杂度:O(1)

    • 完整代码
    package topic1Array;

/*209. 长度最小的子数组

    给定一个含有 n 个正整数的数组和一个正整数 target 。

    找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

    来源：力扣（LeetCode）
    链接：https://leetcode.cn/problems/minimum-size-subarray-sum
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    示例 1：

    输入：target = 7, nums = [2,3,1,2,4,3]
    输出：2
    解释：子数组 [4,3] 是该条件下的长度最小的子数组。*/

public class topic4_209 {
    public static void main(String[] args) {
        Solution solution = new topic4_209().new Solution();
        int[] nums = {2,3,1,2,4,3};
        int target = 7;
        PublicAPI.printArray(nums);
        int minLen = solution.minSubArrayLen(target, nums);
        System.out.println(minLen);
    }
    class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            int minLen = Integer.MAX_VALUE;
            int sum = 0;
            int pre=0, cur=0;
            for (; cur<nums.length; cur++) {
                sum+=nums[cur];
                while (sum>=target) {       // 满足条件就更新最小长度，并维护滑动窗口的总和小于 target
                    minLen = minLen < cur-pre+1 ? minLen : cur-pre+1;
                    sum-=nums[pre];
                    pre++;
                }
            }
            return minLen != Integer.MAX_VALUE ? minLen : 0;
        }
    }
}

59.螺旋矩阵II

59.螺旋矩阵II

注意：
坚持循环不变量原则(推荐使用 左闭右开 的规则做模拟)
用循环的圈数作为判断条件，在每一圈内实现填充规则

  • 模拟顺时针画矩阵的过程:

    1. 填充上行从左到右
    2. 填充右列从上到下
    3. 填充下行从右到左
    4. 填充左列从下到上
      螺旋矩阵模拟

  • Java代码

    • 规则模拟
    class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int loop=0, start=0;    // 实际注意两个问题，画的圈数以及当前圈的起始点
        int i=0, j=0;           // i作为行，j作为列
        int count=1;            // 计数量，1 ~ n^2
        while (loop++ < n/2) {  // 用要画的圈数做为判断条件
            for (i=start, j=start; j<n-loop; j++) {
                matrix[i][j]=count++;
            }
            for (; i<n-loop; i++) {
                matrix[i][j]=count++;
            }
            for (; j>=loop; j--) {
                matrix[i][j]=count++;
            }
            for (; i>=loop; i--) {
                matrix[i][j]=count++;
            }
            start++;
        }
        if (n%2==1) {           // 还要注意n为奇数时，中间的点也要填充
            matrix[start][start]=count;
        }
        return matrix;
    }
}
    • 完整代码
    package topic1Array;

/*59. 螺旋矩阵 II

    给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

    示例 1：


    输入：n = 3
    输出：[[1,2,3],[8,9,4],[7,6,5]]

    链接：https://leetcode.cn/problems/spiral-matrix-ii/*/
public class topic5_59 {
    public static void main(String[] args) {
        Solution solution = new topic5_59().new Solution();
        int n = 4;
        int[][] matrix = solution.generateMatrix(n);
        PublicAPI.printArray(matrix);
    }
    class Solution {
        public int[][] generateMatrix(int n) {
            int[][] matrix = new int[n][n];
            int loop=0, start=0;
            int i=0, j=0;
            int count=1;
            while (loop++ < n/2) {
                for (i=start, j=start; j<n-loop; j++) {
                    matrix[i][j]=count++;
                }
                for (; i<n-loop; i++) {
                    matrix[i][j]=count++;
                }
                for (; j>=loop; j--) {
                    matrix[i][j]=count++;
                }
                for (; i>=loop; i--) {
                    matrix[i][j]=count++;
                }
                start++;
            }
            if (n%2==1) {
                matrix[start][start]=count;
            }
            return matrix;
        }
    }
}

数组总结

数组的经典题目

  1. 二分法
    704.二分查找
  • 可以使用暴力解法，通过这道题目，如果追求更优的算法，建议试一试用二分法，来解决这道题目
    • 暴力解法时间复杂度：O(n)
    • 二分法时间复杂度：O(logn)

在这道题目中我们讲到了循环不变量原则，只有在循环中坚持对区间的定义，才能清楚的把握循环中的各种细节。

  1. 双指针法
    快慢指针：27.移除元素
    977.有序数组的平方

双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

  • 暴力解法时间复杂度：O(n^2)
  • 双指针时间复杂度：O(n)

数组中的元素为什么不能删除，主要是因为：

  • 数组在内存中是连续的地址空间，不能释放单一元素，如果要释放，就是全释放（程序运行结束，回收内存栈空间）

双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组和链表操作的面试题，都使用双指针法。

  1. 滑动窗口
    209.长度最小的子数组
  • 暴力解法时间复杂度：O(n^2)
  • 滑动窗口时间复杂度：O(n)

本题中，主要要理解滑动窗口如何移动 窗口起始位置，达到动态更新窗口大小的，从而得出长度最小的符合条件的长度。

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。

  1. 模拟行为

在这道题目中，我们再一次介绍到了循环不变量原则，其实这也是写程序中的重要原则。

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐