977.有序数组的平方
https://leetcode.com/problems/squares-of-a-sorted-array/
虽然看了题目提示说推荐使用双指针来做，但是我并没有想出来该怎么写。偷懒的用了sort来做
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for(int i=0; i<nums.size(); i++){
nums[i] = pow(nums[i],2);
}
sort(nums.begin(),nums.end());
return nums;
}
};
写完了暴力解法后，我想到了两个指针一个在前 一个在后来对比哪个大，然后指针再向前或向后移动。看了Carl的视频和文字讲解，才忽然意识到原来是可以创建一个新的数组去储存答案的。但是之前我一直想的是用nums本身这个数组进行挪换，一道简单的题让我给想狭隘了。 没等看完Carl的视频，我就自己急着试一试，然后写出来了。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int res_index = nums.size()-1;
vector<int> res(nums.size(),0);
int slow_ptr = 0;
int fast_ptr = nums.size()-1;
while(slow_ptr <= fast_ptr){
int left = pow(nums[slow_ptr],2);
int right = pow(nums[fast_ptr],2);
if(left > right){
res[res_index] = left;
slow_ptr++;
}
else{
res[res_index] = right;
fast_ptr--;
}
res_index--;
}
return res;
}
};
通过这题明白了，如果题中没有说要在原数据结构上进行修改，其实就可以试着用新的数据结构来储存答案。本以为会牺牲空间，但是对比了我的答案和暴力解法的资源占用，发现基本上是一样的。暴力解法花费38 ms 25.9 MB。而双指针用了30 ms 25.9 MB。简单查阅了一下，毕竟sort这个function本身也需要排序并调用空间资源的。在知乎上看到说：“STL的sort算法，数据量大时采用QuickSort快排算法，分段归并排序。一旦分段后的数据量小于某个门槛（16），为避免QuickSort快排的递归调用带来过大的额外负荷，就改用Insertion Sort插入排序。如果递归层次过深，还会改用HeapSort堆排序。”
209.长度最小的子数组
自己没有想出来怎么写滑动窗口，跟着Carl的视频，跌跌撞撞写出来了。我比较需要注意的两点： 1） 如果遇到大于等于target的情况，应该是用while loop把前面该减的都减去。 2）开始的时候，我老实的用了nums.size()作为res的上限，然后在程序最后的时候检查是不是数组中构不成相应的结果，但其实完全可以把res设置为INT_MAX，胆子大一点设置上限，这样程序结尾在检查res的时候能更轻松的知道是不是找到了结果。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int start = 0;
int sum = 0;
int res = INT_MAX;
for(int end=0; end<nums.size(); end++){
sum = sum + nums[end];
while(sum >= target){
sum = sum - nums[start];
res = min(end-start+1,res);
start++;
}
}
if(res == INT_MAX)
return 0;
else
return res;
}
};
59.螺旋矩阵II
这道题一开始我没什么思路，一直想着如何用聪明的办法去解这道题。想了半天也没想明白，尤其是任务中说用到了“二分搜索中提到的区间定义”，我马虎的认为是用二分搜索的办法做呢。粗略看了题解，才明白思路其实就是模拟螺旋，一步步填数就行。但是要注意的是从哪里开始，又到哪里开始新的填数逻辑。以及利用offset来限制每轮螺旋的区间来限制该多少个数就转弯。我自己写的代码如下：
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int count = 1;
vector<vector<int>> res(n, vector<int>(n,0));
int startx;
int starty;
int loop = n/2;
int offset = 1;
while(loop){
startx = offset - 1;
starty = offset - 1;
int limit = n - (offset - 1)*2 - 1;
for(int i=0; i<limit; i++){
res[startx][starty] = count;
starty++;
count++;
}
for(int i=0; i<limit; i++){
res[startx][starty] = count;
startx++;
count++;
}
for(int i=0; i<limit; i++){
res[startx][starty] = count;
starty--;
count++;
}
for(int i=0; i<limit; i++){
res[startx][starty] = count;
startx--;
count++;
}
loop--;
offset++;
}
if(n%2 != 0){
res[n/2][n/2] = pow(n,2);
}
return res;
}
};
