湖北营销型网站建设多少钱,wordpress 收邮件,代做毕业设计的网站,望野古诗王绩977 有序数组的平方题目链接#xff1a;977 有序数组的平方介绍给你一个按 非递减顺序 排序的整数数组 nums#xff0c;返回 每个数字的平方 组成的新数组#xff0c;要求也按 非递减顺序 排序。思路看到题目的第一反应#xff0c;首先负数的平方跟正数的平方是相同的…977 有序数组的平方题目链接977 有序数组的平方介绍给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。思路看到题目的第一反应首先负数的平方跟正数的平方是相同的所以想到可以先将Nums中的负数变成正数然后对其进行排序然后再将排好序的正数进行平方。或者直接平方后再排序。暴力解法class Solution {
public:vectorint sortedSquares(vectorint nums) {for(int i0;inums.size();i){nums[i] nums[i]*nums[i];}sort(nums.begin(),nums.end());//快排return nums;}
};双指针解法当对数组进行平方后还能进行一个有序的排列时可发现所有元素平方后由大到小的趋势最大元素在两边。首先可定义一个新的数组result用于存放排列后的数。定义一个索引下标knum.size(-1【新的数组由大到小来更新取两边的最大 然后取次大】定义两个下标ij循环终止的条件ij如果ij是假设i指向的数和j指向的数相同那么就落下了这个数int knum.size(-1
for(i0,jnum.size()-1;ij ; ){
//i和j--取决于哪个对应的是最大值如果i对应的是最大值那么i反之j--if(nums[i]*nums[i] nums[j]*nums[j]){result[k--] nums[i]*nums[i];i;}else{result[k--] nums[j]*nums[j];j--;}
}代码class Solution {
public:vectorint sortedSquares(vectorint nums) {vectorint results(nums.size());//注意定义数组时要在后面说明数组的长度int k nums.size()-1;int i,j;for(i0,jnums.size()-1;ij;){if(nums[i]*nums[i]nums[j]*nums[j]){results[k--] nums[i]*nums[i];i;}else{results[k--] nums[j]*nums[j];j--;}}return results;}
};209 长度最小子数组题目链接209 长度最小子数组介绍思路滑动窗口思想—双指针思路不断的调节子序列的起始位置和终止位置从而得出我们要想的结果。使用一个for循环做两个for循环所做的事。for循环中的下标j指向的是终止位置。而如何移动起始位置就是需要解决的问题。通过利用题中给出的条件集合中的元素若s那么即可将起始位置向后移动。通过移动起始位置去收集不同区间里面的和。result MAX
for(i0,j0;jnums.size();j){ //i是起始位置j是终止位置sum sum nums[j];while(sums) //持续向后移动{subLj-i1;result min(result,subL)sum sum - nums[i]i;}
}
return result;首先移动终止元素j找到起始位置i和j之间的长度s若s满足条件sums则移动起始位置i更新sum值(sumsum-num[i])和区间长度i然后重新判断s是否满足条件如果满足条件继续移动其实位置i更新sum值。如果不满足条件则跳出while循环移动终止位置j(j)更新新区间的sum值在原sum的基础上增加num[j],重新判断是否满足条件。class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int result INT32_MAX;int sum 0;//滑动窗口数值之和int i 0;//滑动窗口起始位置int subLength 0;//滑动窗口的长度for(int j0; jnums.size();j){sum sum nums[j];while(sumtarget){subLength j-i1;result result subLength?subLength:result;sum sum - nums[i];i;}}return result INT32_MAX?0:result;}
};代码59 螺旋矩阵题目链接59 螺旋矩阵介绍给你一个正整数 n 生成一个包含 1 到 n2 所有元素且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。思路问题边界处理最关键边界上的四个点。当前边遍历时处理还是下一条边遍历时处理循环不变量原则坚持一个规律来处理每一条边。若按照左闭右开的原则每条边只处理第一个节点最后一个不处理。把最后一个节点留给下一条边的起始位置处理。while(m/2){ //一共转几圈n/2圈如果n是奇数对nums[][]作为单独的赋值
//每一圈的起始位置不固定startx0;starty0;offset1;count1;//遍历第一条边 j是列for(jstarty;jn-offset;j){nums[startx][j]count;count;}//遍历第二条边 i是行for(istartx;in-offset;i){//此时jn-offsetnums[i][j]count;count;}//遍历第三条边 j已经指向了右下角,不需要初始化了,但终止的边界是jstarty要留给下一条边处理for( ; jstarty;j--){nums[i][j]count;count; }//遍历第四条边 i已经在最下面了也不需要初始化for( ; istartx;i--){nums[i][j]count;count;}startx;starty;offset;if(n%21){nums[i][j]count}}代码class Solution {
public:vectorvectorint generateMatrix(int n) {vectorvectorint res(n, vectorint(n, 0)); // 使用vector定义一个二维数组int startx 0, starty 0; // 定义每循环一个圈的起始位置int loop n / 2; // 每个圈循环几次例如n为奇数3那么loop 1 只是循环一圈矩阵中间的值需要单独处理int mid n / 2; // 矩阵中间的位置例如n为3 中间的位置就是(11)n为5中间位置为(2, 2)int count 1; // 用来给矩阵中每一个空格赋值int offset 1; // 需要控制每一条边遍历的长度每次循环右边界收缩一位int i,j;while (loop --) {i startx;j starty;// 下面开始的四个for就是模拟转了一圈// 模拟填充上行从左到右(左闭右开)for (j starty; j n - offset; j) {res[startx][j] count;}// 模拟填充右列从上到下(左闭右开)for (i startx; i n - offset; i) {res[i][j] count;}// 模拟填充下行从右到左(左闭右开)for (; j starty; j--) {res[i][j] count;}// 模拟填充左列从下到上(左闭右开)for (; i startx; i--) {res[i][j] count;}// 第二圈开始的时候起始位置要各自加1 例如第一圈起始位置是(0, 0)第二圈起始位置是(1, 1)startx;starty;// offset 控制每一圈里每一条边遍历的长度offset 1;}// 如果n为奇数的话需要单独给矩阵最中间的位置赋值if (n % 2) {res[mid][mid] count;}return res;}
};
