Day2力扣打卡

打卡记录

无限数组的最短子数组（滑动窗口）

链接

思路：先求单个数组的总和，再对两个重复数组所组成的新数组上使用 不定长的滑动窗口 来求得满足目标的最小长度。

class Solution {
public:
    int minSizeSubarray(vector<int>& nums, int target) {
        long long sum = accumulate(nums.begin(), nums.end(), 0LL);
        int ans = 0x3f3f3f3f, n = nums.size(), cnt = 0;
        for (int i = 0, j = 0; i < n * 2; ++i)
        {
            cnt += nums[i % n];
            while (cnt > target % sum)
                cnt -= nums[j++ % n];
            if (cnt == target % sum) ans = min(ans, i - j + 1);
        }
        return ans == 0x3f3f3f3f ? -1 : ans + target / sum * n; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

螺旋矩阵 II（模拟）

链接

模拟向四个方向依次行进，遇到边缘调转为下个方向，同时遇到已经赋值过的位置也进行调转方向的操作。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int dx[4]{0, 1, 0, -1}, dy[4]{1, 0, -1, 0}, cnt = 0;
        int x = 0, y = 0, idx = 0;
        vector<vector<int>> mat(n, vector<int> (n, -1));
        while (cnt++ != n * n) {
            mat[x][y] = cnt;
            if (x + dx[idx] < 0 || x + dx[idx] >= n || y + dy[idx] < 0 || y + dy[idx] >= n 
            || mat[x + dx[idx]][y + dy[idx]] != -1)
                idx = (idx + 1) % 4;
            x += dx[idx], y += dy[idx];
        }
        return mat;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16