977.有序数组平方
讲解链接：
看解答前：
最直白的想法就是遍历所有数据的平方，再排序。但是这样做的结果会导致计算超时。虽然昨天理解了双指针的思路，但是看到这个题还是无法和双指针联系起来。应该是双指针的精髓还没掌握。
看解答后：
解答讲了两种方法，暴力解和双指针。
- 暴力解思路：
平方后再排序。超时了。。。
class Solution { public: vector<int> sortedSquares(vector<int>& nums) { // for(int i = 0 ; i < nums.size();++i){ // nums[i]*= nums[i]; // } for(int i = 0;i < nums.size() - 1; ++i){ for(int j = 0;j< nums.size() - i - 1 ; ++j){ if(fabs(nums[j]) >fabs( nums[j+1])){ int temp = nums[j]; nums[j] = nums[j + 1] ; nums[j+1] = temp; } } nums[nums.size() - i -1] *= nums[nums.size() - i -1]; } nums[0]*=nums[0]; return nums; } };
2.双指针思路：
既然是有序数组，且未规定正负，那么平方后的值要么是两侧往中间递减，要么是向右单侧递增。根据这个规律可以利用双指针的思想完成代码。
- 双指针的位置一个位于数组最左侧，一个位于最右侧。
- 两侧平方后比较，将最大值放入待返回数组最右侧。
- 左侧较大则左侧值放入待返回数组右侧，左侧指正索引+1，待返回数组索引-1；右侧指正位置不变。
- 右侧较大同理。
- 当左侧索引大于右侧索引的时候终止循环。因为左侧索引等于右侧索引时，待返回数组值还需要填入最后一个值。
代码：
class Solution { public: //双指针法 vector<int> sortedSquares(vector<int>& nums) { int k = nums.size()-1; vector<int>res(nums.size(),0); int left_index = 0; int right_index = k; while(left_index <= right_index){ int left_val = nums[left_index]*nums[left_index]; int right_val = nums[right_index]*nums[right_index]; if(left_val > right_val){ res[k--] = left_val ; left_index++; }else{ res[k--]=right_val; right_index--; } } return res; } };
总结：
还是需要看解答后才能自己写出来，对于双指针的运用还是不熟。期待二刷。
209.长度最小的字数组
讲解链接：
看解答前：
知道要用双指针的思想，想了半个小时还是没想出来。太菜了，呜呜呜呜啊啊啊啊。
看解答后：
确实不看讲解学习，根本想不出来的。思路如下：
- 用双指针的思想那么就要确认左侧指针和右侧指针。由于是找出长度最短的子数组，所以指针位置可以为数组左侧和数组右侧。
- 最开始时数组做右侧都是同一个位置。右侧为子数组终点，那终点可能问数组的任何一个索引位置，所以终点位置需要从数组左侧一直持续到最后。
- 子数组的初始位置并不是数组最左侧，而是根据子数组数据和来决定是否往右移动。如果子数组内的数据和大于或者等于目标值那么初始位置就需要往右侧移动。
- 最重要的一点是维护最短子数组的长度，因为在循环过程中子数组长度并不是递增或者递减的，但是数据的遍历范围需要走完整个数组，所以子数组长度在每次遍历后都需要更新最小值。
- 最后如果最小值没更新过则返回0。
代码：
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int res = INT32_MAX; int sum = 0; int begin = 0; int sublength = 0; for(int end = 0;end<nums.size();++end){ sum+=nums[end]; //难点在target的范围确定 while(sum>= target){ sublength =end - begin + 1; res = res<sublength?res:sublength; sum-=nums[begin++]; } } return res= res<INT32_MAX?res:0; } };
总结：
想不到，期待二刷。
59.螺旋矩阵
讲解链接：
看解答前：
用笔画能画出来，但是写不出来。
看解答后：
- 确定遍历层数，因为一次循环遍历上下左右，所以遍历的层数是n/2，对于奇数层则额外计算。
- 偏移量 offset，每往里遍历一层则偏移量的值要+1。
- 上层:开始往右遍历，最右侧的数据不用处理交给下一步处理。所以遍历的数据个数是n - offset。
- 有层：同理
- 下层：同理
- 做层：同理
- 遍历完一层上下左右以后，刷新初始位置和偏移量，因为外面层数据已经处理过，所以初始位置向中心靠拢一个，上下左右遍历的数据也会减小所以对应的偏移量减小1.
- 上述步骤循环往复遍历直至跳出循环
- 最后判定是奇数层还是偶数层，偶数层不管，技术层直接对初始位置（初始位置再循环中会向中心靠拢，所以此时的初始位置是中心位置）赋值。
代码：
class Solution { public: vector<vector<int>> generateMatrix(int n) { vector<vector<int>>res(n,vector<int>(n,0)); int startx = 0; //纵向起始位置 int starty = 0; //横向起始位置 int offset = 1; //偏移量,每循环一次,偏移量+1; int count = 1; //螺旋矩阵初始值 int loop = n/2; //循环圈数,一次循环会遍历两行两列,所以除2,奇数额外考虑 int j = 0,i = 0;//遍历量 while(loop --){ //向右遍历 for( j = starty;j<n-offset;++j){ res[startx][j] = count++; } //向下遍历 for( i = starty;i<n - offset;++i){ res[i][j] = count++; } //向左遍历 for(;j>starty;--j){ res[i][j] = count++; } //向上遍历 for(;i>startx;--i){ res[i][j] = count++; } //遍历完一层,初始位置向中心靠拢一格,偏移量增加一个. startx++; starty++; offset++; } if(n%2==1){ //循环结束的时候初始位置已经靠近中心了 res[startx][starty]=count; } return res; } };
总结：
一样的不看解题思路写不出来。
数组总结
主要学习了二分法，双指针法。时间太赶，来不及了先粗略写一版。
