977.有序數(shù)組的平方
題目鏈接：https://leetcode.cn/problems/squares-of-a-sorted-array/
算法思想：
簡單的方法：平方之后，快速排序
更近一步的方法：用空間換時(shí)間。
可以發(fā)現(xiàn)，平方之后的數(shù)據(jù)有個(gè)特點(diǎn)，最大的數(shù)分布在兩頭，此時(shí)可以用頭尾指針從前后開始比較，找到一個(gè)大的，放到新定義的數(shù)組末尾，知道兩個(gè)指針相遇就結(jié)束。
代碼：
class Solution {
public:
? ? vector<int> sortedSquares(vector<int>& nums) {
? ? ? ? //要求是O(n)的時(shí)間復(fù)雜度的時(shí)候，可以想到用雙指針法
? ? ? ? int len = nums.size();
? ? ? ? int left =0;
? ? ? ? int right = len-1;
? ? ? ? vector<int> copy(len, 0);
? ? ? ? int i = len;
? ? ? ? while(left<=right)
? ? ? ? {?
? ? ? ? ? ? // cout<<"i:"<<i << " right:"<<right<<" left:"<<left;
? ? ? ? ? ? int r_sqr = nums[right] * nums[right];
? ? ? ? ? ? int l_sqr = nums[left] * nums[left];
? ? ? ? ? ? // cout<<"i:"<<i << " right:"<<right<<" left:"<<left<<"r_sqr"<<r_sqr<<"l_sqr"<<l_sqr;
? ? ? ? ? ? if(r_sqr > l_sqr)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? copy[--i] = r_sqr;
? ? ? ? ? ? ? ? right--;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? copy[--i] = l_sqr;
? ? ? ? ? ? ? ? left++;
? ? ? ? ? ? }
? ? ? ? ? ? cout<<" copy:"<<copy[i]<<endl;
? ? ? ? }
? ? ? ? return copy;
? ? }
};
209.長度最小的子數(shù)組
題目鏈接：https://leetcode.cn/problems/minimum-size-subarray-sum/
算法思想：滑動窗口
思路：
用一個(gè)快慢指針指向窗口的頭尾，要明確快慢指針是用開區(qū)間還是閉區(qū)間?？熘羔樥业揭粋€(gè)區(qū)間，滿足區(qū)間和大于target，此時(shí)慢指針可以往前移動，找到一個(gè)最短的區(qū)間。
class Solution {
public:
? ? int minSubArrayLen(int target, vector<int>& nums) {
? ? ? ? //操作數(shù)組，可以想到用雙指針的方法，其實(shí)雙指針本質(zhì)上是兩個(gè)for循環(huán)的濃縮
? ? ? ? int len = nums.size();
? ? ? ? int fast = 1;
? ? ? ? int slow = 0;
? ? ? ? int min_len = len+1;
? ? ? ? int sum = nums[0];
? ? ? ? while(fast <= len)
? ? ? ? {?
? ? ? ? ? ? if(sum<target) //還不夠，fast往上增加
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(fast>=len)
? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? sum += nums[fast];
? ? ? ? ? ? ? ? fast++;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(min_len>(fast-slow))
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? min_len = fast - slow;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? sum -= nums[slow];
? ? ? ? ? ? ? ? slow++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if(min_len==(len+1))
? ? ? ? ? ? return 0;
? ? ? ? return min_len;
? ? }
};
題目鏈接：https://leetcode.cn/problems/spiral-matrix-ii/
算法思想：循環(huán)不變量
思路：
需要遍歷矩陣的上下左右四個(gè)方向，遍歷的過程其實(shí)是重復(fù)性的過程，但是由于是在矩陣中，邊界之間有重復(fù)，往往搞不清楚邊界問題。只要我們把四個(gè)方向的遍歷長度保持一致，即區(qū)間大小保持一致，就不容易弄亂。
如何定義?即定義左閉右開的區(qū)間，遍歷的時(shí)候遍歷起始節(jié)點(diǎn)而不遍歷終止節(jié)點(diǎn)，因?yàn)榻K止節(jié)點(diǎn)要作為下一個(gè)遍歷的起始節(jié)點(diǎn)。這樣我們就能很容易的寫出來4個(gè)for循環(huán)遍歷完成一圈。
第二圈的時(shí)候，只是把遍歷范圍減小了，其他不變。
需要定義起始邊界：startx, starty
終止邊界：n-offset,n-offset
代碼：
class Solution {
public:
? ? vector<vector<int>> generateMatrix(int n) {
? ? ? ? //用雙指針解決，j表示水平方向移動的指針，i表示豎直方向的指針
? ? ? ? vector<vector<int>> nums(n, vector<int> (n, -1));
? ? ? ? int startx = 0;
? ? ? ? int starty= 0;
? ? ? ? int k = 0;
? ? ? ? int i= startx;
? ? ? ? int j = starty;
? ? ? ? int offset = 1;
? ? ? ? int count = 1;
? ? ? ? while(k<n/2)
? ? ? ? {
? ? ? ? ? ? i = startx;
? ? ? ? ? ? j = starty;
? ? ? ? ? ? for(;j<n-offset;j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? nums[i][j] = count;
? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? ? ? cout<<i<<" "<<j<<" "<<nums[i][j]<<endl;
? ? ? ? ? ? }
? ? ? ? ? ? for(;i<n-offset;i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? nums[i][j] = count;
? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? ? ? cout<<i<<" "<<j<<" "<<nums[i][j]<<endl;
? ? ? ? ? ? }
? ? ? ? ? ? for(;j>starty;j--)
? ? ? ? ? ? {
? ? ? ? ? ? ? nums[i][j] = count;
? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? ? ? cout<<i<<" "<<j<<" "<<nums[i][j]<<endl;
? ? ? ? ? ? }
? ? ? ? ? ? for(;i>startx;i--)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? nums[i][j] = count;
? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? ? ? cout<<i<<" "<<j<<" "<<nums[i][j]<<endl;
? ? ? ? ? ? }
? ? ? ? ? ? // cout<<"end"<<endl;
? ? ? ? ? ? offset++;
? ? ? ? ? ? startx +=1;
? ? ? ? ? ? starty +=1;
? ? ? ? ? ? k++;
? ? ? ? }
? ? ? ? if(n%2==1)
? ? ? ? {
? ? ? ? ? ? nums[n/2][n/2] = count;
? ? ? ? ? ? // cout<<"0:"<<nums[0][0];
? ? ? ? }
? ? ? ? // cout<<1/2<<endl;
? ? ? ? return nums;
? ? }
};
