代码随想录算法训练营第二天|997.有序数组的平方、 209.长度最小的子数组、 59.螺旋矩阵II。网站首页 技术交流

代码随想录算法训练营第二天|997.有序数组的平方、 209.长度最小的子数组、 59.螺旋矩阵II。

Allmight_Q 2024-06-26 14:23:49

简介代码随想录算法训练营第二天|997.有序数组的平方、 209.长度最小的子数组、 59.螺旋矩阵II。

LeetCode 977 有序数组的平方

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        vector<int> result(nums.size(),0);//初始化result，长度为nums.size()，值全为0
        int i = result.size() - 1;
        while(i >= 0){
            int left_Sq = nums[left] * nums[left];
            int right_Sq = nums[right] * nums[right];
            if(left_Sq > right_Sq){
                result[i--] = left_Sq;
                left++;
            }else{
                result[i--] = right_Sq;
                right--;
            }
        }
        return result;
    }
};

看到题的第一想法

时间复杂度需要O(n)，所以不能使用排序算法，而是使用双指针遍历一轮，从两侧往里，比较大的放在新vector的最后，从后往前添加

LeetCode 209 长度最小的子数组

题目链接 209.长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int length = nums.size() + 1;
        int sum = 0;
        int slowIndex = 0;
        for(int fastIndex = 0;fastIndex < nums.size();fastIndex++){
            if(sum < target){
                sum += nums[fastIndex];
            }
            while(sum >= target){
                if(fastIndex - slowIndex < length)
                    length = fastIndex - slowIndex + 1;//子序列长度和
                sum -= nums[slowIndex++];
            }
            
        }
        if(length > nums.size())
            return 0;
        return length;
    }
};

看到题的第一想法

快慢指针，sum随着快指针累加，到sum>=target时判断是否比length小，再sum随着慢指针累减，到sum<target进入下一轮循环

遇到的困难

把慢指针累减部分放在了else里，导致现在还没想清楚的错误（有待解决），子序列长度和fastIndex-slowIndex所以出错了

看完代码随想录后的想法

子序列长度为fastIndex-slowIndex+1,因为这里使用的是闭区间！！

LeetCode 59 螺旋矩阵II

题目链接 59.螺旋矩阵II

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n, vector<int>(n));
        int num = 1;
        int startx = 0;
        int starty = 0;
        int offset = 0;
        int i,j;
        for(int x = 0; x < n/2; x++){
            for(j = offset; j < n - offset - 1; j++)
                matrix[startx][j] = num++;
            for(i = offset; i < n - offset - 1; i++)
                matrix[i][j] = num++;
            for(;j > offset;j--)
                matrix[i][j] = num++;
            for(;i > offset;i--)
                matrix[i][j] = num++;
        }
        if(n/2 != 0)
            matrix[n/2][n/2] = num;
        return matrix;
    }
};