leetcode_day2

第二天就有所松懈了，拖到晚上才写，拓展题也没写完，今天的没那么无脑，所以用老本行C++写

有序数组的平方

打眼一瞧，这题就是拿正负数平方之后大小不定来考人，结合卡哥想练的双指针，不难想到左右指针比绝对值大小一个一个插入，虽然这样是从大到小，不过有reverse()可以用，比较方便，也没有增加时间复杂度，还是\(O(n)\)，下附代码，不甚完美，可点击链接去看官解

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

长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0 。

这题是滑动窗口，由于做过多次，所以记得比较清楚，直接写了，结果遇到不少问题，WA了一发才解决，对于区间开闭的把握还不纯熟……

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        if(nums.size() == 1) return target <= nums[0];
        int left = 0, right = 1, sum = nums[0];
        int ans = 0;
        while(right <= nums.size() && left < right) {
            if(sum < target && right < nums.size()) {
                sum += nums[right++];
            }
            else if(sum >= target && left < right) {
                if(ans == 0) ans = right - left;
                else ans = min(ans, right - left);
                sum -= nums[left++];
            }
            else break;
        }
        return ans;
    }
    
};

拓展——水果成篮

这题是卡哥关于滑动窗口的拓展题1，小生不才，WA了五发才过，思路一直不清，将思路转换为代码语言也不准确。

大概描述思路：

俩篮子我用俩变量bucket1、bucket2来模拟，含左右顺序，俩指针做滑动窗口代表当前能摘的树。一个ans作为结果一直维护一个最大值，每遇到新树，则将left前进到第二种水果第一次出现的地方，right重新从left处开始走。至于第一次出现的位置我用一个pair来存。

下附代码，官解与我不同，使用了哈希表，我也想用，苦于set和map系列语法掌握不牢，没写出来……

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        if(fruits.size() == 1) return 1;
        pair<int, int> bucket1, bucket2;
        int left = 0, right = 1;
        bucket1.first = fruits[left];
        bucket1.second = left;
        bucket2.first = -1;
        bucket2.second = -1;
        int ans = 2;
        while(left <= right && right < fruits.size()) {
            if(fruits[right] == bucket1.first) {
                ans = max(ans, right - left + 1);
            }
            else if(fruits[right] == bucket2.first) {
                ans = max(ans, right - left + 1);
            }
            else if(bucket2.first == -1){
                bucket2.first = fruits[right];
                bucket2.second = right;
                ans = max(ans, right - left + 1);
            }
            else {
                left = bucket2.second;
                bucket1.first = bucket2.first;
                bucket1.second = left;
                bucket2.first = -1;
                bucket2.second = -1;
                right = left;
            }
            right++;
        }
        return ans;
    }
};

leetcode 官方题解：水果成篮

拓展——最小覆盖子串

吐了，写的全没了，不记了，直接抛出灵神题解算了，哈希方法的确妙，还有less对于检索的优化。

灵茶山艾府题解

螺旋矩阵II

这题经典模拟，之前做过多次，这次一把过，左sir讲过优雅的四循环，评论区也是优雅的四循环，所以我也优雅的四循环，但还是不够优雅。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int top = 0, bottom = n - 1, right = n - 1, left = 0;
        int row = 0, col = 0;
        int map[n][n];
        int k = 1;
        while(k <= n*n) {
            for(int t = left;t <= right;t++) 
                map[top][t] = k++;
            top++;
            if(k > n*n) break;
            for(int r = top;r <= bottom;r++) 
                map[r][right] = k++;
            right--;
            if(k > n*n) break;
            for(int b = right;b >= left;b--)
                map[bottom][b] = k++;
            bottom--;
            if(k > n*n) break;
            for(int l = bottom;l >= top;l--)
                map[l][left] = k++;
            left++;
        }
        vector<vector<int>> ans;
        for(int i = 0;i < n;i++) {
            vector<int> t;
            for(int j = 0;j < n;j++) {
                t.push_back(map[i][j]);
            }
            ans.push_back(t);
        }
        return ans;
    }
};

总结

数组部分总体不难，主要是双指针和滑动窗口思想，双指针有快慢指针和左右指针，滑动窗口偏贪心一点，大体是right向前去满足条件，满足之后收紧left寻找最优，最后综合所有最优选出整体最优。