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

977.有序数组的平方

题目描述

题目链接：力扣977.有序数组的平方

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

思路

已知数组按非递减顺序排列，若全为非负数，则直接按顺序平方即可；若全为非整数，则按倒序平方即可。可既有正数又有负数的情况下不能如此考虑。

结合全部同号的情况，可将数组按正负号分为两组，则两组分别按顺序排列。易联想到将两个有序数列结合成一个有序数列的情况。

因此思路如下：首先找到数组中间正负分界点，也即绝对值最小的元素，也即平方最小的元素，左边是全是负数，右边全是正数，从中间向两边的平方均为非递减顺序。使用两个指针left right, 每次判断两个指针指向元素的绝对值大小，将小的元素的平方插入新数组尾部，并向外移动一步，循环遍历即可。

注意：需要注意当一边越界后的处理

代码实现

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans;
        int min_i = -1, cur = 10005;
        for(int i = 0; i < n; i++){
            if(abs(nums[i] < cur)){
                min_i = i;
                cur = abs(nums[i]);
            }
        }

        int left, right;
        if(nums[min_i] < 0) left = min_i;
        else left = min_i - 1;
        right = left + 1;
        
        for(int i = 0; i < n; i++){
            if(left < 0 || (right < n && nums[right] <= -nums[left])){
                ans.push_back(nums[right] * nums[right]);
                right++;
            }
            else if(right >= n || (left >= 0 && -nums[left] < nums[right])){
                ans.push_back(nums[left] * nums[left]);
                left--;
            }
        }


        return ans;
    }
};

209. 长度最小的子数组

题目描述

题目链接：力扣209.长度最小的子数组

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

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组$[num{s}_l,num{s}_{l+1},...,num{s}_{r-1},num{s}_r]$，并返回其长度。如果不存在符合条件的子数组，返回 0 。

思路

假如数组中含有总和等于target的子数组，起始终止下标设为l r。已知数组中均为正整数，那么[l, r-1], [l+1, r]的和必定小于target，[l-1, r], [l, r+1]的和必定大于target。

由此引出滑动窗口的思想：设定一个宽度不固定的窗口，起始位置为l，终止位置为r，窗口内元素和为s。若s < target, r += 1; 若s >= target, 更新窗口宽度，l += 1。

这时候有同学要问了，为什么s < target 的时候, 是 r += 1， 而不是 l -= 1呢，这样也可以让窗口内元素和变大呀。

因为我们的窗口是从左边往右移动，若当前左边界是 l 的话，那么说明左边界是 l-1 的情况已经经历过了，l - 1代表的窗口长度已经记录，不需要再返回了。s >= target 的情况同理，是 l += 1 而不是 r -= 1。

代码实现

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        
        int l = 0, r = 0, s = 0;
        int min_length = 100001;
        while(r < n){
            s += nums[r];
            while(s >= target){
                min_length = min(min_length, r - l + 1);
                s -=nums[l++];
            }
            r++;
        }
        if(min_length == 100001) return 0;
        return min_length;
    }
};

59.螺旋矩阵II

题目

题目链接: 力扣59.螺旋矩阵II

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

思路

假如让你用手在纸上画出这个矩阵，你会怎么画？

按照人类的思想，应该是先确定矩阵的长宽，然后沿着边界一圈一圈将数字填进去即可。

这道题目其实按照人类的思想模拟即可，长宽已经确定是$n\times n$，再设计好边界的更新规则，一一填入即可。下面我们讨论下边界的更新。

正方形共有上下左右四个边界，一圈为一个循环。初始状态上边界 $up=0$， 下边界$down=n$，左边界$left=0$，右边界 $right=n$，若你要使用左闭右闭的区间规则，将$n$改为$n-1$即可。沿顺时针转即，先沿上边界向右填一行，随后up += 1, 再沿右边界向下填一列，随后 right -= 1，再沿下边界向左填一行，随后 down += 1，最后沿左边界向上填一行，随后 left += 1。直到矩阵填满。

代码实现

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n);
        for(int i=0; i<n; i++){
            matrix[i].resize(n);
        }

        int up = 0, left = 0, right = n, down = n;
        int num = 1;
        while(num <= n*n){
            for(int i = left; i < right; i++){
                matrix[up][i] = num;
                num++;
            }
            up++;
            for(int i = up; i < down; i++){
                matrix[i][right-1] = num;
                num++;
            }
            right--;
            for(int i = right - 1; i >= left; i--){
                matrix[down-1][i] = num;
                num++;
            }
            down--;
            for(int i = down - 1; i >= up; i--){
                matrix[i][left] = num;
                num ++;
            }
            left++;
        }
        return matrix;
    }
};