阅读量:4
学习记录，主要参考：代码随想录
977.有序数组的平方
题目链接：https://leetcode.cn/problems/remove-element/
文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP
实现情况：
思路是先对元素进行平方，然后进行排序
int abs(int i) //返回整型参数i的绝对值
int a = pow(4,2);// 4的平方=16
因为数组是一个非递减顺序 排序的整数数组，所以可以使用双指针方式进行操作
vector a(n+1);// 初始化一个新的数组，并且都初始化为0
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int n = nums.size()-1; vector<int> a(n+1); for(int h = 0, t = n; h<=t;){ if(abs(nums[h]) < abs(nums[t])){ nums[t] = nums[t]*nums[t]; a[n--] = nums[t--]; }else{ nums[h] = nums[h]*nums[h]; a[n--] = nums[h++]; } } return a; } }; 
还可以直接使用快排序 sort(A.begin(), A.end());
class Solution { public: vector<int> sortedSquares(vector<int>& A) { for (int i = 0; i < A.size(); i++) { A[i] *= A[i]; } sort(A.begin(), A.end()); // 快速排序 return A; } }; 
209.长度最小的子数组
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
文章讲解：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
视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE
实现情况：
解决这道题重要的方法是使用滑动窗口
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
需要注意如果数组当中没有满足条件的数据的情况，最后返回值的判断很重要
h:表示滑动窗口左边界
t:表示滑动窗口右边界
t++：表示滑动窗口的程度在不断增加，右边界在不断右移
while(sum >= target) //这里使用while 就是不断将滑动窗口右移
t - h + 1 //是计算当前的到的子数组的长度
sum -= nums[h++];//这里是先减去滑动窗口最右边的一个数据，然后将滑动窗口右进一格
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int sum = 0; int result_end = INT_MAX; for (int h = 0, t = 0; t < nums.size(); t++) { sum += nums[t]; while(sum >= target) { result_end = (result_end < t - h + 1) ? result_end : t - h + 1; sum -= nums[h++]; } } return result_end == INT_MAX ? 0 : result_end; } }; 
59.螺旋矩阵II
题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/
求解本题依然是要坚持循环不变量原则
模拟顺时针画矩阵的过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
由外向内一圈一圈这么画下去
按照左闭右开的原则
1、循环的圈数计算：n/2 ，需要注意如果是奇数最后一个数需要添加
2、确定好每行每列填充的条件，找到变量和不变量
class Solution { public: vector<vector<int>> generateMatrix(int n) { int j= 0,i=0; int startx = 0, starty = 0; int offset = 1; int count = 1; int loop = n/2; int mid = n/2; vector<vector<int>> b(n, vector<int>(n, 0)); while(loop--){ i = startx; j = starty; for (j; j < n - offset; j++) { b[i][j] = count++; } for (i; i < n - offset; i++) { b[i][j] = count++; } for(;j> starty;j--){ b[i][j] = count++; } for(;i> startx;i--){ b[i][j] = count++; } starty++; startx++; offset += 1; } if(n%2){ b[mid][mid] = count; } return b; } }; 
数组总结
数组是存放在连续内存空间上的相同类型数据的集合。
数组下标都是从0开始的。
数组内存空间的地址是连续的
因为数组在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。
数组的元素是不能删的，只能覆盖。
二分法：
暴力解法时间复杂度：O(n)
二分法时间复杂度：O(logn)
双指针法：
双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
暴力解法时间复杂度：O(n^2)
双指针时间复杂度：O(n)
滑动窗口
暴力解法时间复杂度：O(n^2)
滑动窗口时间复杂度：O(n)
滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置
模拟行为
记住循环不变量原则！
