Leetcode977 有序数组的平方 Square of a Sorted Array

暴力解法

  • 刚看到题想到的是暴力解法, 时间复杂度是O(nlogn)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {  
    public:  
        vector<int> sortedSquares(vector<int>& nums) {  
            for (int i = 0; i < nums.size(); i++) {  
                nums[i] *= nums[i];  
            }  
            sort(nums.begin(),nums.end());  
            return nums;  
        }  
    };

双指针法

  • 因为数组有负数, 所以负数的平方很可能比正数的平方大. 所以我们只要比对快慢指针的平方对比谁大就放进result的数组里.
  • 时间复杂度O(n)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {  
    public:  
        vector<int> sortedSquares(vector<int>& nums) {  
            int len = nums.size() - 1;  
            vector<int> result(nums.size(), 0);  
            int i = 0, j = nums.size() - 1;  
            while (i <= j ){  
                if ( (nums[i] * nums[i]) > (nums[j] * nums[j]) ){  
                    result[len--] = nums[i] * nums[i];  
                    i++;  
                } else {  
                    result[len--] = nums[j] * nums[j];  
                    j--;  
                }  
            }  
            return result;  
        }  
    };

Leetcode209 长度最小的子数组 Minimum Size Subarray Sum

暴力解法

  • 时间复杂度O(n^2)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            int result = INT32_MAX; // 最终的结果
            int sum = 0; // 子序列的数值之和
            int subLength = 0; // 子序列的长度
            for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
                sum = 0;
                for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
                    sum += nums[j];
                    if (sum >= s) { // 一旦发现子序列和超过了s，更新result
                        subLength = j - i + 1; // 取子序列的长度
                        result = result < subLength ? result : subLength;
                        break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                    }
                }
            }
            // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
            return result == INT32_MAX ? 0 : result;
        }
    };

滑动窗口

  • 滑动窗口是不断调节子序列的起始位置和终止位置.

跟双指针很像, 但是滑动窗口的指针是在同一起点进行的.

  • 窗口内是什么? 窗口是满足其和≥s的长度最小的连续子数组
  • 如何移动窗口的起始位置? 如果当前值大于s,窗口就要向前移动
  • 如何移动窗口的结束位置? 窗口的结束位置就是遍历数组的指针

核心代码:

1
2
3
4
5
while(sum >= target){  
    temp = i - j + 1; //取子序列的长度
    output = temp < output ? temp : output; 
    sum -= nums[j++]; //不断变更的j(子序列的起始位置)
}
  • 时间复杂度: O(n)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {  
    public:  
        int minSubArrayLen(int target, vector<int>& nums) {  
            int len = nums.size();  
            int temp = 0;  
            int sum = 0;  
            int output = INT32_MAX;  
            int j = 0;  
      
            for (int i = 0; i < len; i++){  
                sum += nums[i];  
                while(sum >= target){  
                    temp = i - j + 1;  
                    output = temp < output ? temp : output;  
                    sum -= nums[j++];  
                }  
            }  
            return output == INT32_MAX ? 0 : output;  
        }  
    };

Leetcode59 螺旋矩阵II Spiral Matrix II

模拟过程

  • 首先要从左向右,从上到下,从右到左,从下到上. 模拟螺旋矩阵的样子.

  • 循环不变量. 每一条先都要左闭右开. 处理从第一个节点到最后一个前一个(最后一个节点不处理,留给下一条边来处理)

  • 转 n/2 圈 ,如果是奇数,最后多一个判断语句如果 n/2 是奇数,把数组最后一个数放在中间.

  • startx 和 starty 定义每次循环的起始点.

  • offset 需要控制每一条边遍历的长度,每次循环右边界收缩以为

  • for (j = starty; j < n-offset; j++)
    - 循环开始,从左到右遍历,j 从循环 starty 起点到n-offset 收缩截止.
    - nums[startx][j] = count++;

  • for (i = startx; i < n-offset; i++)
    - 循环最后边,从上到下,从循环 startx 起点到n-offset 收缩截止.
    - 因为上一个for循环的j 停留在了最后一个,可以直接用.
    - nums[i][j] = count++;

  • for (; j>starty;j--)

    • 循环最下层,从右到左,不需要重新定义j的开始,到j到starty之前截止.
    • nums[i][j] = count++;

  • for (; i > startx; i--)

    • 循环最左层,从下到上,不需要重新定义i的开始,到i到starti之前截止.
    • nums[i][j] = count++;

  • 最后要把每次循环圈的起点增加,和offset 边界收缩增加

    • //第二圈开始起始点x,y都加1
      startx++;
      starty++;
      //offset 控制每一圈里每一条边遍历的长度
      offset++; `
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
class Solution {  
public:  
    vector<vector<int>> generateMatrix(int n) {  
        vector<vector<int>> nums(n, vector<int>(n,0)); //定义二维数组  
        int startx = 0, starty = 0; //定义每次循环的起始点x,y  
        int offset = 1; // 需要控制每一条边遍历的长度，每次循环右边界收缩一位  
        int count = 1; //矩阵里的数  
        int loop = n/2; // 举证循环几次,如果是奇数最后判定  
        int mid = n/2; //圈数奇数判定,中间的值nums[mid][mid]  
        int i,j;  
        while (loop--){  
            for (j = starty; j < n-offset; j++){  
                nums[startx][j] = count++;  
            }  
            for (i = startx; i < n-offset; i++){  
                nums[i][j] = count++;  
            }  
            for (; j>starty;j--){  
                nums[i][j] = count++;  
            }  
            for (; i > startx; i--){  
                nums[i][j] = count++;  
            }  
            //第二圈开始起始点x,y都加1  
            startx++;  
            starty++;  
            //offset 控制每一圈里每一条边遍历的长度  
            offset++;  
        }  
  
        //奇数,要单独给中间赋值  
        if (n % 2){  
            nums[mid][mid] = count;  
        }  
        return nums;  
    }  
};