算法训练营Day 2

977.有序数组的平方language
题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep

考察点：双指针

class Solution {
public:
    std::vector<int> sortedSquares(std::vector<int> &nums) {
        int left = 0;
        int right = nums.size() - 1;
        vector<int> res(nums.size(), 0);
	# 这里不能用auto, nums.size() 是unsigned long, --到最后都不会小于0，会死循环
        for (int k = nums.size() - 1; k >= 0; k--) {
            if (nums[left] * nums[left] < nums[right] * nums[right]) {
                res[k] = nums[right] * nums[right];
                right--;
            } else {
                res[k] = nums[left] * nums[left];
                left++;
            }
        }
        return res;
    }
};

209.长度最小的子数组
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE

考察点：双指针，滑动窗口

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0;
        int right = 0;
        int sum = nums[0];
        int min_len = nums.size()+1;

        while(left<=right){
            if(sum>=target){
                if(right-left+1<min_len){
                    min_len = right-left+1;
                }
                sum -= nums[left];
                left++;
            }else{
                if(right<nums.size()-1){
                    right ++;
                    sum += nums[right];
                }else{
                    break;
                }
            }
        }
        if(min_len>nums.size()){
            min_len =0;
        }
        return min_len;
    }
};

59.螺旋矩阵II
题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/

考察点：边界值处理

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int start_x = 0;
        int start_y = 0;
        int offset = 1;
        int loop_cout = n/2;
        int num = 0;
        vector<vector<int>> res(n, vector<int>(n, 0));
        
        while(offset <= loop_cout){
            int i=start_x;
            int j=start_y;
            for(;i<n-offset;i++){
                res[start_y][i]=++num;
            }
            for(;j<n-offset;j++){
                res[j][i]=++num;
            }
            for(;i>start_y;i--){
                res[j][i]=++num;
            }
            for(;j>start_x;j--){
                res[j][start_x]=++num;
            }
            start_x++;
            start_y++;
            offset++;
        }

        if(n%2==1){
            int mid = n/2;
            res[mid][mid] = n*n;
        }

       return res; 
    }
};