day02 有序数组的平方 长度最小子数组 螺旋矩阵

2024-01-03 01:46:35

题目1:977? 有序数组的平方

题目链接:977 有序数组的平方

题意?

返回非递减整数数组的每个数字的平方和? 也按照递减排序

双指针★

代码

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> result(nums.size(), 0);
        int k = nums.size() - 1;
        for(int i = 0,j=nums.size() - 1;i <= j;){
           if(nums[i] * nums[i] > nums[j] * nums[j]){
               result[k] = nums[i] * nums[i];
               k--;
               i++;
           }
           else{
               result[k] = nums[j] * nums[j];
               k--;
               j--;
           } 
        }
        return result;
    }
};

时间复杂度O(n)

空间复杂度O(n)

暴力解法

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i = 0;i < nums.size();i++){
            nums[i] = nums[i] * nums[i];
        }
        sort(nums.begin(), nums.end());//排序
        return nums;
    }
};

时间复杂度O(n+nlogn)

题目2:209? 长度最小的子数组

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

题意

数组中含有n个正整数,返回数组中总和大于等于target的长度最小的连续子数组的长度,注意数组中一定要是正整数,因为只有正整数才会越加越大,如果没有则,返回0

滑动窗口★

思想:不断更新连续子数组的起始位置和终止位置,使用1个for循环就可以完成这些操作

for循环中的变量应该是终止位置,这样才能避免暴力解法两层for循环的情况

滑动窗口移动的条件:当前窗口的值大于等于s

遇到某个滑动窗口内的总和大于等于target,就移动这个滑动窗口的起始位置,看是否还有更短的长度的子数组满足大于等于target的条件;如果滑动窗口内的总和小于target,说明整个滑动窗口扩充的还不够长,于是需要移动终止位置

代码

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i = 0;//滑动窗口起始位置
        int sum = 0;//总和
        int subL = 0;//子数组长度
        int result = INT32_MAX;
        for(int j = 0;j < nums.size();j++){
            sum += nums[j];  //子数组总和
            while(sum >= target){
                subL = j - i + 1;
                result = min(result,subL);
                sum -= nums[i];//将起始位置的数值从总和中减去
                i++; //注意同时移动起始位置
            }
        }
        return result==INT32_MAX ? 0 : result;
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

暴力解法

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT32_MAX;
        int subL = 0;
        for(int i = 0;i < nums.size();i++){
            int sum = 0;
            for(int j = i;j < nums.size();j++){
                sum += nums[j];
                if(sum >= target){
                    subL = j - i + 1;
                    result = min(result,subL);
                    break;//此处跳过for循环是因为数组中都是正整数,越往后加数值肯定越大,越满足sum>target
                }
            }
        }
        return result==INT32_MAX ? 0 : result;
    }
};
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

使用暴力解法会超时,如下图

题目3:59 螺旋矩阵Ⅱ

题目链接:59.螺旋矩阵Ⅱ

题意

正整数1~n^2的所有元素,按照顺时针排列成n*n的正方形矩阵,并按照矩阵的形式一行一行的输出

循环不变量

本题还是要坚持循环不变量原则,每一圈的处理规则要统一,均是左闭右开,由外向内一圈一圈画,每一圈都可以使用一套代码,每一圈的每一条边的情况列出来,遍历圈数

使用左闭右开的原则,即拐角处的元素放到下一条边处理? ? i代表行,j代表列

转的圈数是 n/2? 的原因是:将整个正方形对半分,看一半有多少条边,就可以转多少圈

代码

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
       vector<vector<int>> nums(n,vector<int>(n,0));
       int startx = 0;  //i的起始位置
       int starty = 0;  //j的终止位置
       int offset = 1;  //第一圈的偏移量
       int count = 1;   //每个位置的数,计数,不断累加
       int loop = n / 2;  //圈数
       int mid = n / 2;  //中间的位置
       int i,j;
       while(loop--){
           //上行   i代表行,j代表列   行不变,列++
           for(j = starty;j < n - offset;j++){
               nums[startx][j] = count++;//跳出循环时,i=startx,j=n-offset
           }
           //右列    行++,列不变
           for(i = startx;i < n - offset;i++){
               nums[i][j] = count++; //跳出循环时,i=n-offset,j=n-offset
           }
           //下行    行不变,列--
           for(;j > starty;j--){
               nums[i][j] = count++;//跳出循环时,i=n-offset,j=0
           }
           //左列    行--,列不变
           for(;i>startx;i--){
               nums[i][j] = count++;//跳出循环时,i=0,j=0
           }
           //进入下一圈做准备
           startx++;
           starty++;
           offset++;
       }
       if(n % 2 == 1) {
           nums[mid][mid] = count;  //这里不是i,j因为是i和j的话,指向的是最后一圈的第一个位置,不符
       }
       return nums;
    }
};
  • 时间复杂度 O(n^2): 模拟遍历二维矩阵的时间
  • 空间复杂度 O(1)

文章来源:https://blog.csdn.net/qq_43773652/article/details/135259455
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。