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

• 算法结构

目录

977 有序数组的平方

209 长度最小的子数组

59 螺旋矩阵 ||

977 有序数组的平方

 先使数组存储递减序列，最后反转数组使其非递减

class Solution {
public:
    vector sortedSquares(vector& nums) {
        int l = 0,r = nums.size() - 1;
        vectorres(nums.size());
        int i = 0;
        for(int i = 0;i  abs(nums[l])){
                res[i] = nums[r] * nums[r--]; 
            }else{
                res[i] = nums[l] * nums[l++];
            }
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

时间复杂度O(n)

空间复杂度O(n)

209 长度最小的子数组

 快慢指针

class Solution {
public:
    int minSubArrayLen(int target, vector& nums) {
        int res = nums.size();
        int sum = 0;
        for(int i = 0;i < nums.size();i++)sum += nums[i];
        if(sum < target)return 0;
        sum = 0;
        for(int r = 0,l = 0;r = target){
                res = min(res,r - l + 1);
                sum -= nums[l++];
            }
        }
        return res;
    }
};

时间复杂度O(n)

空间复杂度O(1)

59 螺旋矩阵 ||

 模拟即可

class Solution {
public:
    vector<vector> generateMatrix(int n) {
        vector<vector>res(n,vector(n));
        int w = 0,s = n - 1,a = 0,d = n - 1,cnt = 1;
        while(cnt <= n * n){
            for(int i = a;i <= d;i++)res[w][i] = cnt++;
            w++;
            for(int i = w;i = a;i--)res[s][i] = cnt++;
            s--;
            for(int i = s;i >= w;i--)res[i][a] = cnt++;
            a++;
        }
        return res;
    }
};

空间复杂度O(1)//返回了res，不计算在空间复杂度内

时间复杂度O(n^2) 

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/d6892d1870.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐