Day2：（1）有序数组的平方（2）长度最小的子数（3）Leetcode 59螺旋矩阵II-Toy模板网

这篇具有很好参考价值的文章主要介绍了Day2：（1）有序数组的平方（2）长度最小的子数（3）Leetcode 59螺旋矩阵II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1. Leetcode 977有序数组的平方

（1）解析

Leetcode977
参考文章
参考视频

（2）思路

一开始考虑不采用新建一个新数组，在原数组上实现有序数组平方的排序，实现起来比较繁琐，细节会有些小错，后来采用新建数组的方式：
定义一个新数组resVec，和A数组一样的大小；让index指向resVec数组当前可插入元素的位置；左右指针谁大谁进入新数组，再移动相应指针；循环判断条件是left <= right；

（3）代码

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        vector<int> resVec(nums.size(), 0);
        int index = right;
        while(left <= right)
        {
            if(nums[right]*nums[right] <= nums[left]*nums[left])
            {
                resVec[index--] = nums[left]*nums[left];
                ++left;                
            }
            else
            {
                resVec[index--] = nums[right]*nums[right];
                --right;                
            }
        }
        return resVec;
    }
};

（4）总结

不需要在原数组上实现操作，新建个数组会简单许多。

2. Leetcode 209长度最小的子数组

（1）解析

Leetcode209
参考文章
参考视频

（2）思路

滑动窗口，不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果；slow位置可以采用循环判断来加速推进；nums.size() + 1作为cnt的初始比较对象，同时可以判断是否存在长度最小的子数组的标志；

（3）代码

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

（4）总结

slow的循环加速；nums.size()+1标志位的判断

3. Leetcode 59螺旋矩阵II

（1）解析

Leetcode59
参考文章
参考视频

（2）思路

左闭右开；右 -> 下 -> 左 -> 上四个方向；定义好行列的起始结束位置；二维数组定义vector<vector > vecres(n, vector(n, 0))；循环的次数判定；

（3）代码

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
    int start = 0, end = n - 1;
    int num = 0;
    vector<vector <int>> vecres(n, vector<int>(n, 0));
    int loop = n/2;
    int row, column;
     while(loop--)
     {
         row = start, column = start;
        for(column = start; column < end; ++column)
        {
            vecres[row][column] = ++num;
        }
        for(row = start; row < end; ++row)
        {
            vecres[row][column] = ++num;
        }

        for(column = end; column > start; --column)
        {
            vecres[row][column] = ++num;
        }

        for(row = end; row > start; --row)
        {
            vecres[row][column] = ++num;
        }
        start++;
        end--;
     }
    if(n % 2==1)
        vecres[n/2][n/2] = n * n;
    return vecres;
    }
};