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

本文主要是介绍day02 有序数组的平方 长度最小子数组 螺旋矩阵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目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)

这篇关于day02 有序数组的平方 长度最小子数组 螺旋矩阵的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---