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

第一题：

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

思路：

先将数组求完平方和后进行排序，很简单，主要是排序算法的考察。

这里采用快排

快排的思路：

取这个数组的中间值，然后以此为基准，判断这个基准的左边的元素是否小于基准值，右边的元素是否大于基准值，如果两边都为否，也就是说左边的值大于基准值，右边的值小于基准值，则交换两者的位置。然后一直迭代下去，对左边的元素进行以上操作同时对右边的元素也进行以上操作，最后便是排完序的结果。

代码如下：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){
            nums[i] = nums[i] * nums[i];
        }
        //sort(nums.begin(), nums.end());
        quicksort(nums, 0, nums.size() - 1);
        return nums;
    }
private:
    void quicksort(vector<int> &nums, int l, int r){
        if(l >= r) return;
        int mid = l + (r - l) / 2;
        int pivot = nums[mid];
        int i = l - 1, j = r + 1;
        while(i < j){
            do i++; while(nums[i] < pivot);
            do j--; while(nums[j] > pivot);
            if(i < j) swap(nums[i], nums[j]);
        }
        quicksort(nums, l, j);
        quicksort(nums, j + 1, r);      
    }
};

第二题链接：209. 长度最小的子数组 - 力扣（LeetCode）

思路：

双指针：使用快慢指针，首先定义一个慢指针为0，定义快指针一直遍历整个数组。

然后定义一个总和记录此时相加元素的总和sum。

此时维护一个范围让这个区间的元素的总和一直大于target，慢指针指向这个区间的最左边，快指针指向区间的最右边。

如何维护，首先先快指针遍历加到sum中，当sum的值大于等于target的时候，此时得到区间的长度进行比较最后得到最小值，同时更行左边界，也就是让慢指针右移直到区间内的元素总和小于target。

代码如下：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int res = INT_MAX;
        int sum = 0, slow = 0;
        for(int fast = 0; fast < nums.size(); fast++){
            sum += nums[fast];
            while(sum >= target){
                res = min(res, fast - slow + 1);
                sum -= nums[slow];
                slow++;
            }
        }
        return res == INT_MAX ? 0 : res;
    }
};

第三题链接：59. 螺旋矩阵 II - 力扣（LeetCode）

思路：

模拟把元素放进指定位置的过程。定义上下左右四个边界。当第一行的元素放入后，上边界++，当最后一列的元素放入后，右边界--，当最后一行的元素放入后，下边界--，当第一列元素放入后，左边界++；直到放完为止。

代码如下：

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