977.有序數(shù)組的平方

題目鏈接：力扣

思路:同樣使用雙指針的方法，這樣就可以只遍歷一次原數(shù)組。

可以考慮需要按照一個順序來遍歷，那就是從大到小或者從小到大，我選擇的是從大到小。

不難看出，原數(shù)組將每個數(shù)平方后，呈現(xiàn)從兩邊到中間逐漸減小的規(guī)律。

所以使用一個指針指向原數(shù)組最左端，一個指向最右端，比較那邊的數(shù)大，就是原數(shù)組中最大的數(shù)。

我們新建一個數(shù)組，用來存放已經(jīng)排好序的數(shù)組，按照從大到小放數(shù)據(jù)應(yīng)該是從數(shù)組尾開始放。

時間復(fù)雜度：o(n)

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        //這個個地方用.size()函數(shù)來求數(shù)組的長度，注意是vector數(shù)組的函數(shù)方法
        int len=nums.size();
        for(int i=0;i<len;i++) nums[i] = nums[i]*nums[i];
        //需要注意這里vector數(shù)組的定義方法，不會就搜索一下
        vector<int> numss(len);
        //這里使用雙指針i,j來遍歷原數(shù)組
        //同時用一個指針來完成將數(shù)據(jù)放入排序好的數(shù)組
        int i=0,j=len-1,k=len-1;
        //這里每個人可以根據(jù)個人喜好使用不同的循環(huán)語句，for循環(huán)也可以做到
        while(true){
            if(nums[i]<nums[j]){
                numss[k]=nums[j];
                j--;
            }
            else{
                numss[k]=nums[i];
                i++;
            }
            k--;
            if(k<0) break;
        }
        return numss;
    }
};

?本題的難點在于如何考慮到只用時間復(fù)雜度為o(n)的方法，即只遍歷一次原數(shù)組，需要根據(jù)平方后的原數(shù)組找到按從大到小或從小到大的規(guī)律。

209.長度最小的子數(shù)組

題目鏈接：力扣

思路：使用滑動窗口的方法，我們可以想到子序列的變化方法就是，當(dāng)子序列之和大于目標(biāo)值，就要從開頭減去一個，小于目標(biāo)值時，就要從后面再添加進(jìn)一個。

但是我們要考慮所有子序列的可能性，即所有的數(shù)組元素都可能成為子序列的開頭或結(jié)尾，當(dāng)我選擇子序列是從左往右滑動時，那么子序列的結(jié)尾是規(guī)律的，即每次添加一個元素。

而對應(yīng)于每個子序列的結(jié)尾，子序列的開頭可以是在這之前的任意一個元素，但實際上卻并不用考慮在這之前的每個元素，因為當(dāng)結(jié)尾在往右遍歷時，開頭也在往右遍歷，我們只需考慮當(dāng)前開頭的后面元素，而不必考慮當(dāng)前開頭的之前元素。

時間復(fù)雜度：nlogn?

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        //用result來表示最短子序列的長度，先將其賦值為整形最大值是考慮到每次都是按子序列長度更小的進(jìn)行賦值，本題中數(shù)組可能不存在滿足條件的子序列，則result沒有被賦值，輸出0；
        int result = INT_MAX;
        //用sum來表示當(dāng)前子序列內(nèi)所有數(shù)的和
        int sum=0;
        //用i來表示子序列開頭的位置
        int i=0;
        for(int j=0;j<nums.size();j++){
            //j是用來表示子序列結(jié)束的位置，因為我們考慮到數(shù)組的每個元素都有可能成為子序列的結(jié)束位置。
            sum+=nums[j];
            //當(dāng)添加一個元素進(jìn)去后，那么子序列的總和就有可能超過目標(biāo)元素，此時我們需要將子序列中元素減去一個，很顯然就是從開頭減去，因為子序列是連續(xù)的。
            while(sum>=target){
                //len表示子序列的長度
                int len=j-i+1;
                //此時result是表示所有滿足條件的自序中長度最小的，所以它是一個要和所有長度比較的變量，遇到更小的就賦值。
                result=result>len?len:result;
                sum-=nums[i];
                i++;

            }
        }
        return result==INT_MAX?0:result;

    }
};

滑動窗口的運用讓我想到字符串匹配是不是也可以用這種方法？只要是連續(xù)的子序列仿佛都可以用。?

?59.螺旋矩陣2

題目：力扣

思路：數(shù)組里的題最難的就是找出規(guī)律，當(dāng)規(guī)律被發(fā)現(xiàn)了，答案也就浮出水面了。

看到這題，相信每個人都能想到，需要四條邊逐邊進(jìn)行賦值，那么比較難的就是進(jìn)行四條邊的規(guī)律統(tǒng)一，首先找到的就是每四條長度相等的且互相不重復(fù)的邊可以構(gòu)成一個完整的圈，每條邊包含一個拐點。

首先思考每次循環(huán)一圈的起點在哪里，自己在紙上寫一個n=5比較大的循環(huán)，就可以發(fā)現(xiàn)每次的起點在數(shù)組的主對角線上。此處需要一個變量來表示。

其次我們也觀察到，每一圈每一條邊需要賦值的元素都在減少一此處也需要一個變量表示。但我沒用這個變量表示每條邊需要走的步數(shù)，而是用每圈右邊界少抵達(dá)的坐標(biāo)來表示。這樣間接可以用起點減去這個邊界來表示要走的步數(shù)。

最后發(fā)現(xiàn)，當(dāng)n為奇數(shù)時，所有的圈走完，還剩中心一個元素沒有賦值，我們需要單獨為它賦值。?

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int>(n,0));
        //用來表示每圈的起點坐標(biāo)
        int starti=0,startj=0;
        //key用來控制需要循環(huán)幾圈
        int key=n/2;
        //count用來表示需要填入數(shù)組的數(shù)1，2，3，4...
        int count=1;
        //用來控制左右邊界需要收縮多少，每次循環(huán)右邊界多收縮一位，從第二次循環(huán)開始左邊界收縮一位，其實就是每次循環(huán)，一條邊走幾步
        int bianjie=1;
        while(key--){
            int i=starti,j=startj;
            for(;j<n-bianjie;j++) res[i][j]=count++;
            for(;i<n-bianjie;i++) res[i][j]=count++;
            for(;j>startj;j--) res[i][j]=count++;
            for(;i>starti;i--) res[i][j]=count++;
            starti++;
            startj++;
            bianjie++;
        }
        if(n%2==1) res[starti][startj]=count;
        return res;
    }
};

本題難點在于找到規(guī)律，和尋找自己需要表示的變量，應(yīng)該不用自己想出來怎么寫，只要看懂別人的思路，然后自己能敲出來代碼，以后碰到類似的題能想起來這個思路就行。?文章來源地址http://www.zghlxwxcb.cn/news/detail-421438.html

到了這里，關(guān)于算法訓(xùn)練第二天|977.有序數(shù)組的平方、209.長度最小的有序數(shù)組、59.螺旋矩陣2的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！