代码随想录算法训练营第二天|LeetCode977， 209， 59

LeetCode 977 有序数组的平方

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

//使用stl的排序，毫无算法思想
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());
        return nums;
    }
};

视频讲解链接：https://www.bilibili.com/video/BV1QB4y1D7ep

文章讲解链接：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

根据视频和文章讲解做出如下总结：

1.采用相向双指针，i从0下标开始从左向右遍历，j从nums.size()-1下标开始从右向左遍历。因为平方后，数组元素的最大值在两边，最小值在中间。


2.新建数组，接收更新后的元素值。

//双指针
vector<int> sortedSquares(vector<int>& nums) {
        //建一个新的数组
        vector<int> result(nums.size(), 0);
        int k = nums.size()-1;
        int i, j;
				//相向双指针所指的元素进行比较
  			//当 i > j 时终止for循环
        for(i = 0, j = nums.size()-1; i <= j; ){
            if(nums[i] * nums[i] > nums[j] * nums[j]){
                result[k--] = nums[i] * nums[i];
                ++i;
            }
            else{
                result[k--] = nums[j] * nums[j];
                --j;
            }
        }
        return result;
    }

LeetCode 209 长度最小的子数组

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

//如果使用暴力双重循环，会超出时间限制
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        vector<int> result;
      	//i指向起始位置
        for(int i = 0; i < nums.size(); i++){
            int sum = 0;
          	//j指向终止位置
            for(int j = i; j < nums.size(); j++){
                sum += nums[j];
                if(sum >= target){
                    	result.push_back(j-i+1);
				
                }
            } 
        }
        if(result.empty()) return 0;
        sort(result.begin(), result.end());
        return result[0];
    }
};

视频讲解链接：https://www.bilibili.com/video/BV1tZ4y1q7XE

文章讲解链接：https://programmercarl.com/0209.长度最小的子数组.html

根据视频和文章讲解做出如下总结：

1.数组操作中，使用滑动窗口方法，不断地调节子序列的起始位置和终止位置，从而得出想要的结果。在暴力解法中，是一个for循环为滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环完成了一个不断搜索区间的过程。

2.思考如果只用一个for循环，是该表示滑动窗口的起始位置还是终止位置？如果该for循环表示滑动窗口的起始位置，如何遍历剩下的终止位置？最后又变成暴力双重for循环。因此，只用一个for循环，那么这个循环的索引一定是表示滑动窗口的终止位置。

3.以题目中的示例来举例，target = 7，数组 [2, 3, 1, 2, 4, 3]，图解查找过程





class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        //采用滑动窗口，只使用一个for循环
        //j代表滑动窗口的终止位置，i代表滑动窗口的起始位置
        int j, i = 0;
        int sum = 0; //滑动窗口的数值之和
        int result = INT32_MAX; //用来进行比较
        for(j = 0; j < nums.size(); j++){
            sum += nums[j];
            while(sum >= target){
                int sublen = j - i + 1;
                result = min(result, sublen);
                sum -= nums[i]; //不用让sum每次从头计算了
                ++i; 
            }
        }
        if(result == INT32_MAX) return 0;
        return result;
        
    }

};

LeetCode 59 螺旋矩阵II

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/

视频讲解链接：https://www.bilibili.com/video/BV1SL4y1N7mV/

文章讲解链接：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html

根据视频和文章讲解做出如下总结：

1.在这篇文章数组：每次遇到二分法，都是一看就会，一写就废 (opens new window)中讲解了二分法，提到如果要写出正确的二分法一定要坚持循环不变量原则。此处不变量可以理解为对每一条边的处理规则，采取左闭右开的方式。

2.模拟顺时针画矩阵的过程：填充上行从左到右；填充右列从上到下；填充下行从右到左；填充左列从下到上



class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        //定义一个二维数组存放矩阵
        vector<vector<int>> res(n, vector<int>(n, 0));
        //定义循环的起始位置startx，starty
        int startx = 0, starty = 0;
        //定义要转的圈数
        int loop = n/2;
        //采取左闭右开的方式遍历每条边，定义遍历每个圈的起始偏移量
        int offset = 1;
        //记录每个二维数组元素赋的值
        int count = 1;

        //最初是从第一行从左到右遍历每一列
        while(loop--){
            int i = startx, j = starty;
            for(; j < n - offset; j++){
                res[startx][j] = count++;
            }
            //从最右列自上而下遍历每一行
            for(; i < n - offset; i++){
                res[i][j] = count++; //此时j跳出for循环，已经 = n - offset
            }
            //从最下行从右到左遍历每一列
            for(; j > starty; j--){
                res[i][j] = count++; //此时i跳出for循环，已经 = n - offset
            }
            //从最左列自下而上遍历每一行
            for(; i > startx; i--){
                res[i][j] = count++; //此时j已跳出for循环，已经 = starty
            }
            //更新offset
            ++offset;
            //更新startx, starty
            ++startx;
            ++starty;
        }

        //判断n是奇数还是偶数，以确认最后一圈是否只用填入一个值
        if(n % 2) res[n/2][n/2] = n * n;
        return res;
        
       

    }
};