day2-数组part02| 977.有序数组的平方、 209.长度最小的子数组、 59.螺旋矩阵II

977. 有序数组的平方

思路

• 数组平方后的最大值只可能在数组两端，不可能在中间
• 设置双指针，比较两个指针所指值的大小，记录较大值，接着向中间移动这个指针
• 结束条件：左右指针相背

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
    int k = nums.size() - 1;
        vector<int> result(nums.size(), 0);
        int i=0,j=nums.size()-1;
        while (i<=j) { // 注意这里要i <= j，因为最后要处理两个元素
            if (nums[i] * nums[i] < nums[j] * nums[j])  {
                result[k] = nums[j] * nums[j];
                k--;
                j--;
            }
            else {
                result[k] = nums[i] * nums[i];
                k--;
                i++;
            }
        }
        return result;
    
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

209.长度最小的子数组

暴力一直不过，明天再补一下

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result=INT32_MAX; //初始化子数组的最小长度为无穷大
        int sum=0;
        int length=0;
        for(int i=0;i<nums.size();i++){
            sum=0;
            for(int j=i;j<nums.size();j++){
                sum += nums[j];
                if(sum >= target){
                    length=j-i+1;
                    result=result<length?result:length;
                    break;
                }
            }
        }
        return result == INT32_MAX ? 0 : result;//如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

滑动窗口

不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

思路

子数组的和小于目标值，移动j指针直到找到大于等于目标值的子数组
找到后，j指针不动，移动i指针，如果移动后的子数组和小于目标值，继续移动j指针，直到和大于等于目标值
重复这个2步骤，直到遍历结束

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result=INT32_MAX;
        int sum=0;
        int i=0;
        int length=0;
        for(int j=0;j<nums.size();j++){
            sum +=nums[j];
            //满足大于等于目标值后，移动i
            while(sum>=target){
                length=j-i+1;
                result=min(result,length);
                sum=sum-nums[i];
                i++;
            }
        }
        return result==INT32_MAX?0:result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

59. 螺旋矩阵 II

本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。

注意：循环不变量

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
       vector<vector<int>> res(n,vector<int>(n,0));
       int startx=0,starty=0;
       int mid=n/2;
       int count=1;
       int offset=1;
       int i,j;
       int loop=n/2;
       while(loop--){
           i=startx;
           j=starty;
           //第一行
           for(j=starty;j<n-offset;j++){
               res[startx][j]=count++;
           }
           //第n-1列
           for(i=startx;i<n-offset;i++){
               res[i][n-offset]=count++;
           }
           for(j=n-offset;j>starty;j--){
               res[n-offset][j]=count++;
           }
           for(i=n-offset;i>startx;i--){
               res[i][starty]=count++;
           }
        startx++;
        starty++;
        offset++;
       } 
       if(n%2){
           res[mid][mid]=count;
       }
       return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

心得

手写一下，把每个值带到带到代码里就明白了