代码随想录打卡Day2

                                                                                                                                  源自力扣209题

法一 暴力求解 

解答代码如下

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;
    }
};

两个for循环嵌套，蠢蠢的枚举！

法二 双指针（快慢指针/滑动窗口）

解答代码如下

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)，

十分巧妙。

大体思路如下

step1：定义窗口初始长度subLength=0，一个累加器sum=0

step2：上for循环，将j作为窗口终点，如果sum<s,将起始位置向后移一位，即窗口长度增加一；

step3：嵌套一个while循环执行：如果sum>=s,将起始位置向前移一位，即窗口长度尝试缩小一位；同时记录下每次满足题意的长度，大小比较后进行答案的不断更迭。

step4：返回答案

如果result没有被赋值的话，就返回0，说明没有符合条件的子序列

                                                                                                                                     源自力扣59题

解答代码如下

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> result(n, vector<int>(n, 0));  // 初始化 n x n 的矩阵
        int startx = 0, starty = 0;  // 起始位置
        int loop = n / 2;  // 循环的层数
        int offset = 1;  // 每一圈缩小的步数
        int count = 1;  // 用来填充的数字
        int mid = n / 2;  // 如果 n 是奇数时，矩阵的中心位置
 
        // 处理每一圈螺旋
        while(loop--) {
            int i = startx;
            int j = starty;
            
            // 1. 从左到右，填充上边
            for (; j < n - offset; j++) {
                result[i][j] = count++;
            }
            // 2. 从上到下，填充右边
            for (; i < n - offset; i++) {
                result[i][j] = count++;
            }
            // 3. 从右到左，填充下边
            for (; j > starty; j--) {
                result[i][j] = count++;
            }
            // 4. 从下到上，填充左边
            for (; i > startx; i--) {
                result[i][j] = count++;
            }
            
            // 更新每一层起始点
            startx++;
            starty++;
            offset++;
        }
        
        // 如果 n 是奇数，最后剩下中心一个位置
        if (n % 2) {
            result[mid][mid] = count;
        }
        
        return result;
    }
};

不涉及算法，但非常考验对多过程的细节把控

这张图很好地把拐角处理成了换边

但中心位置需要另外考虑（也就是if的选择结构）

先上代码

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, a, b;
    cin >> n;
    vector<int> vec(n);
    vector<int> p(n);
    int presum = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &vec[i]);
        presum += vec[i];
        p[i] = presum;
    }

    while (~scanf("%d%d", &a, &b)) {
        int sum;
        if (a == 0) sum = p[b];
        else sum = p[b] - p[a - 1];
        printf("%d\n", sum);
    }
}

 首先声明，题很简单，但如果把时间复杂度给限制死，不太容易想到。

感觉上，很像dfs与记忆化搜索的区别优化

实现过程

p[1] = vec[0] + vec[1];

p[5] = vec[0] + vec[1] + vec[2] + vec[3] + vec[4] + vec[5];

p[5] - p[1] = vec[2] + vec[3] + vec[4] + vec[5];

平时没有注意复杂度计算的很难注意到。