LeetCode977
想到了兩種解法
（1）排序后平方，過于簡單，不在此贅述
（2）雙指針法：根據(jù)題意，平方后最大的數(shù)一定在數(shù)組的兩端
故slowIndex初始下標為0，fastIndex初始下標為nums.size() - 1。比較兩指針對應數(shù)據(jù)的平方大小，
取較大的值，存入res末端。同時更新較大值對應的Index
程序：
class?Solution?{
public:
????vector<int>?sortedSquares(vector<int>&?nums)?{
????????vector<int>?res(nums.size(),0);
????????int?k?=?nums.size()?-?1;
????????int?slowIndex?=?0;
????????int?fastIndex?=?nums.size()?-?1;
????????while(slowIndex?<=?fastIndex){
????????????if(nums[slowIndex]?*?nums[slowIndex]?<?nums[fastIndex]?*?nums[fastIndex]){
????????????????res[k--]?=?nums[fastIndex]?*?nums[fastIndex];
????????????????fastIndex--;
????????????}
????????????else{
????????????????res[k--]?=?nums[slowIndex]?*?nums[slowIndex];
????????????????slowIndex++;
????????????}
????????}
????????return?res;
????}
};
LeetCode209
思路：滑動窗口法
個人理解滑動窗口與雙指針法大同小異，都使用兩個指針不斷更新區(qū)域，查找滿足條件的區(qū)域。
解法如下：
另slowIndex = 0；fastIndex = 0；
首先更新fastIndex，使得slowIndex-fastIndex區(qū)間內(nèi)的值求和大于等于tar，滿足上述條件時計算區(qū)域長度，
同時將slowIndex前移，更新sum值，并將區(qū)域長度與其他滿足條件的長度作對比，取最小的區(qū)間長度返回
程序：
class?Solution?{
public:
????int?minSubArrayLen(int?target,?vector<int>&?nums)?{
????????int?sum?=?0;
????????int?slowIndex?=?0;
????????int?len?=?0;
????????int?res?=?INT32_MAX;
????????for(int?fastIndex?=?0;?fastIndex?<?nums.size();?fastIndex++){
????????????sum?+=?nums[fastIndex];
????????????while(sum?>=?target){
????????????????len?=?fastIndex?-?slowIndex?+?1;
????????????????sum?-=?nums[slowIndex++];
????????????????res?=?res?<?len???res?:?len;
????????????}
????????}
????????return?res?==?INT32_MAX???0?:?res;
????}
};
LeetCode59
思路：注意每次填充的區(qū)間固定，與循環(huán)不變量類似。
不同的n會有不同的圈數(shù)，定義loop = n / 2，當n為奇數(shù)，需要單獨填充中心點。定義每次填充區(qū)間為行/列首填充，
尾不填充，即[ )，先填充外圈，再填充內(nèi)圈。
程序：
class?Solution?{
public:
????vector<vector<int>>?generateMatrix(int?n)?{
????????vector<vector<int>>?result(n,vector<int>(n,0));
????????int?loop?=?n?/?2;
????????int?startx,?starty?=?0;
????????int?count?=?1;
????????int?offset?=?1;
????????int?i,j;
????????int?mid?=?n?/?2;
????????while(loop--){
????????????i?=?startx;
????????????j?=?starty;
????????????for(;j?<?n?-?offset;?j++)
????????????????result[startx][j]?=?count++;
????????????for(;i?<?n?-?offset;?i++)
????????????????result[i][j]?=?count++;
????????????for(;j?>?starty;?j--)
????????????????result[i][j]?=?count++;
????????????for(;i?>?startx;?i--)
????????????????result[i][j]?=?count++;
????????????startx++;
????????????starty++;
????????????offset++;
????????}
????????if(n?%?2)???result[mid][mid]?=?count;
????????return?result;
????}
};
總結(jié)：螺旋矩陣較為復雜，但是只需遵守循環(huán)不變量就可解決，注意內(nèi)圈循環(huán)時的起始終止位置需做變化，可模擬內(nèi)圈循環(huán)過程便于理解。其余難度適中，學習時間3h
