单页网站制作建站仿站,查询学校信息的网站,什么网站做网页好,今天邯郸下的紧急通知一、有序数组的平方
1.1暴力解法
可以直接使用C当时自带的排序算法库函数进行计算#xff0c;属于暴力解法#xff0c;复杂度较高#xff0c;那么有没有运行效率更高的算法思想呢#xff1f;
class Solution {
public:vectorint sortedSquares(vectorint当时自带的排序算法库函数进行计算属于暴力解法复杂度较高那么有没有运行效率更高的算法思想呢
class Solution {
public:vectorint sortedSquares(vectorint nums) {for(int i0;inums.size();i){nums[i]*nums[i];}sort(nums.begin(),nums.end());return nums;}
};
1.2双指针法
class Solution {
public:vectorint sortedSquares(vectorint nums) {int knums.size()-1;int i,j;vectorint result(nums.size(),0);for(i0,jnums.size()-1;ij;){if(nums[i]*nums[i]nums[j]*nums[j]){result[k--]nums[j]*nums[j];j--;}else{result[k--]nums[i]*nums[i];i;}}return result;}
};
二、长度最小的子数组
2.1暴力解法使用两层for循环进行运算
暴力解法确实可以进行运算但是当测试的数组很多数字的时候就超时了
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int resultINT32_MAX;int sum0;int length0;for(int i0;inums.size();i){sum0;for(int ji;jnums.size();j){sumnums[j];if(sumtarget){lengthj-i1;resultresultlength?result:length;break;}}}return resultINT32_MAX?0:result;}
};
2.2使用滑动窗口进行运算
在这里要格外注意为什么使用while(sumtarget)而不是if(sumtarget)来判断
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int resultINT32_MAX;int sum0;int i0;int j0;int length0;//子数组的长度for(j0;jnums.size();j){sumnums[j];while(sumtarget){lengthj-i1;resultresultlength?result:length;sum-nums[i];}}return resultINT32_MAX?0:result;}
};
三、螺旋矩阵
在这里主要是我们要提前规定好怎么查询有规律得查询才能不会发生错误的查询和排序
class Solution {
public:vectorvectorint generateMatrix(int n) {vectorvectorint res(n, vectorint(n, 0));int startx0;int starty0;int count1;int offset1;int loopn/2;int midn/2;int i0,j0;while(loop--){istartx;jstarty;for(jstarty;jn-offset;j){res[i][j]count;}for(istartx;in-offset;i){res[i][j]count;}for(;jstartx;j--){res[i][j]count;}for(;istartx;i--){res[i][j]count;}startx;starty;offset;}if(n%2!0){res[mid][mid]count;}return res;}
};