ps和dw做网站,厦门路桥建设集团有限公司网站,学生个人网页制作html报告,网站开发学院977 有序数组的平方
题目链接#xff1a;有序数组的平方
思路
暴力解法
很容易想到的就是按照题目的说明#xff0c;先给非递减数组中的每个元素做平方#xff0c;然后使用一个排序函数对齐进行排序即可。
class Solution {
public:vectorint sortedSquares(ve…977 有序数组的平方
题目链接有序数组的平方
思路
暴力解法
很容易想到的就是按照题目的说明先给非递减数组中的每个元素做平方然后使用一个排序函数对齐进行排序即可。
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;}
};在写这段简单的代码时想到了两个东西一个是使用for循环来进行赋值一个是使用标准库算法sort来进行排序。然后不知道怎么地就想到使用标准库算法对vector进行处理循环赋值看见了几个标准库算法trasform、generate、for_each等。generate是用来生成的transform会产生新的容器for_each倒是可以满足需求。 for_each(nums.begin(), nums.end(), [](int x){x x * x;});可以进行替换。
双指针法
上一节我只理解了双指针就是得有两个东西对容器进行处理。 本题目给定排序数组如果全部为正数则做平方后顺序不变如果全部为负数则做平方后顺序翻转如果既有正数又有负数则最大的数肯定在两边。综合来看平方后最大的数肯定在左右两边然后从左右两边依次向数组中心逼近。
class Solution {
public:vectorint sortedSquares(vectorint nums) {int n nums.size() - 1;vectorint res(nums.size());for(int slow0, fastnums.size()-1; slowfast;){if(nums[slow]*nums[slow] nums[fast]*nums[fast]){res[n] nums[slow]*nums[slow];n n-1;slow;}if(nums[slow]*nums[slow] nums[fast]*nums[fast]){res[n] nums[fast]*nums[fast];n n-1;fast--;}}return res;}
};长度最小的子数组
题目链接长度最小的子数组
思路
暴力解法
一个直接的思路就是循环遍历数组中的每一个元素然后统计在该元素下的长度。 一种方法是将所有元素的长度存起来然后在在其中选择最小的长度。 另一种方法是重中之重的那行代码每次找到长度后就更新最小的长度。
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int length 0;int result INT32_MAX;for(int i0; inums.size(); i){int sum 0;for(int ji; jnums.size(); j){sum nums[j];if(sum target){length j - i 1;// 这一行代码很重要重中之重result result length ? result : length;break;}}}if(result INT32_MAX){return 0;}return result;// return result INT32_MAX ? 0 : result;}
};滑动窗口法
具体有关滑动窗口的方法请参照链接。 我想表达的意思是滑动窗口法是不是也可以理解为是双指针法因为滑动窗口也有两个东西在动。
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int sum 0;int start 0;int length 0;int res INT32_MAX;for(int end0; endnums.size(); end){sum nums[end];while(sum target){length end - start 1;res res length ? res : length;sum - nums[start]; }}return res INT32_MAX ? 0 : res;}
};最精彩的应该就是下面这部分代码它可以在一个for循环里套入一个while循环这个while循环用来处理当前end对应的所有窗口。
while(sum target){length end - start 1;res res length ? res : length;sum - nums[start];
}59 螺旋矩阵||
题目链接螺旋矩阵||
思路
这道题目就是单纯的绕圈填数但是初次看到这题比较懵逼关键是想法不太明确看了讲解视频看是看明白了但是感觉没有消化到位。总结出以下几点
正整数n是几矩阵的边长就是几我们是绕圈填数那么绕几圈呢应该绕n/2圈当n是奇数时最后要在圈中心填上最后一个数。空矩阵的大小应该是n*nvectorvectorint res(n, vectorint(n,0))针对每一圈分别填上、右、下、左每一条边的最后一个位置不能填这样就对应了左闭右开然后每一圈的截止下标在不断发生变化。每一圈的开始位置也在发生变化。第一圈是(0,0)第二圈是(1,1)…填上边时横坐标不变纵坐标在不断填右边时横坐标在不断纵坐标不变纵坐标是填上边时最后的那个纵坐标填下边时倒着填横坐标不变纵坐标在不断–填左边时纵坐标不变横坐标在不断–。
class Solution {
public:vectorvectorint generateMatrix(int n) {/*思路走几圈每圈的起始位置每圈中每一条边的长度(左闭右开的原则)*/// 正整数n是几vectorvectorint res(n, vectorint(n, 0));int row 0, col 0;int num n / 2;int offset 1;int val 1;int i, j;while(num--){ // num是绕几圈i row;j col;for(jcol; j n-offset; j){ // 横坐标不变纵坐标在变res[row][j] val;val; }for(irow; in-offset; i){ // 纵坐标不变横坐标在变res[i][j] val;val;}for(; jcol; j--){ // 横坐标不变纵坐标在变res[i][j] val;val;}for(; irow; i--){ // 纵坐标不变横坐标在变res[i][j] val;val;}row; // 每过一圈起始位置1col;offset1; // 每过一圈偏移量1}if(n%2){ // 如果n是奇数最后中心位置单独赋值res[n/2][n/2] val;}return res;}
};参考链接
https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html#%E6%80%9D%E8%B7%AF
