Day02：977.有序數(shù)組的平方 ，209.長度最小的子數(shù)組 ，59.螺旋矩陣II

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

【題目建議】： 本題關(guān)鍵在于理解雙指針?biāo)枷?/p>

【隨想錄文章講解】

【卡哥視頻講解】

方法一：暴力排序法

**思路：**先對數(shù)組中每個(gè)數(shù)進(jìn)行平方運(yùn)算，然后再排序

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {  
        for (int i = 0; i < A.size(); i++) {		//先計(jì)算出平方后的數(shù)組
            A[i] *= A[i];
        }
        sort(A.begin(), A.end()); // 快速排序  
        return A;
    }
};

• 時(shí)間復(fù)雜度是 O(n + nlogn) 其中包括計(jì)算平方數(shù)組的O(n)和快速排序的O(nlogn)，總體上是O(nlogn)
• 空間復(fù)雜度：O(logn)。除了存儲答案的數(shù)組以外，需要 O(logn) 的?？臻g進(jìn)行排序。

方法二：雙指針法

思路：原始數(shù)組是有序的數(shù)組，那么平方后數(shù)組中最大的值在兩端（不是在最左面就是最右面），這種情形考慮雙指針法，i指向起始位置，j指向終止位置。

定義一個(gè)新數(shù)組result，和A數(shù)組一樣的大小，讓k指向result數(shù)組終止位置。讓大的數(shù)逐漸進(jìn)入result的隊(duì)尾。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size()-1;						//這里定義k，后面讓k指向result的尾部
        vector<int> result(A.size(),0);			//新知識：定義一個(gè)數(shù)組寫法
        for(int i=0,j=A.size()-1;i<=j;){		// 循環(huán)終止條件，這里一定注意邊界問題<=不然會出現(xiàn)漏掉元素的問題
            if(A[i]*A[i]<A[j]*A[j]){			//比較頭部數(shù)據(jù)大還是尾部數(shù)據(jù)大
                result[k--]=A[j]*A[j];			//尾部數(shù)據(jù)大，進(jìn)入result尾部
                j--;						
            }
            else{
                result[k--]=A[i]*A[i];			//頭部數(shù)據(jù)大，進(jìn)入result尾部
                i++;
            }

        }
               return result;					//輸出這個(gè)數(shù)組
    }
};

• 時(shí)間復(fù)雜度為O(n)
• 空間復(fù)雜度：O(1)

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

題目建議： 本題關(guān)鍵在于理解滑動窗口，這個(gè)滑動窗口看文字講解 還挺難理解的，建議先看視頻講解。 拓展題目二刷做。

【題目鏈接】

【隨想錄文章講解】

【卡哥視頻講解】

相關(guān)題目推薦

• 904.水果成籃

• 76.最小覆蓋子串

方法一：暴力解法

**思路：**暴力解法當(dāng)然是 兩個(gè)for循環(huán)，然后不斷的尋找符合條件的子序列，時(shí)間復(fù)雜度很明顯是O(n^2)。

#include <iostream>         // 包含頭文件。
#include<vector>
using namespace std;        // 指定缺省的命名空間。

int minSubArrayLen(int s, vector<int>& nums) {
    int result = INT32_MAX; // 最終的結(jié)果
    int sum = 0; // 子序列的數(shù)值之和
    int subLength = 0; // 子序列的長度
    for (int i = 0; i < nums.size(); i++) { // 設(shè)置子序列起點(diǎn)為i
        sum = 0;
        for (int j = i; j < nums.size(); j++) { // 設(shè)置子序列終止位置為j
            sum += nums[j];
            if (sum >= s) { // 一旦發(fā)現(xiàn)子序列和超過了s，更新result
                subLength = j - i + 1; // 取子序列的長度
                result = result < subLength ? result : subLength;
                break; // 因?yàn)槲覀兪钦曳蠗l件最短的子序列，所以一旦符合條件就break
            }
        }
    }
    // 如果result沒有被賦值的話，就返回0，說明沒有符合條件的子序列
    return result == INT32_MAX ? 0 : result;
}

    int main() {
        vector<int> v{ 2,3,1,2,4,3 };
        cout << minSubArrayLen(7, v);

}

• 時(shí)間復(fù)雜度：O(n^2)
• 空間復(fù)雜度：O(1)

方法二：滑動窗口（雙指針的思路）

思路：不斷的調(diào)節(jié)子序列的起始位置和終止位置，從而得出我們要想的結(jié)果

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;//獲取有符號 int 對象的最大值  保證result會更新
        int sum = 0; // 滑動窗口數(shù)值之和
        int i = 0; // 滑動窗口起始位置
        int subLength = 0; // 滑動窗口的長度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意這里使用while，每次更新 i（起始位置），并不斷比較子序列是否符合條件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的長度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 這里體現(xiàn)出滑動窗口的精髓之處，不斷變更i（子序列的起始位置）
            }
        }
        // 如果result沒有被賦值的話，就返回0，說明沒有符合條件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

59.螺旋矩陣II

題目建議： 本題關(guān)鍵還是在轉(zhuǎn)圈的邏輯，在二分搜索中提到的區(qū)間定義。本題并不涉及到什么算法，就是模擬過程，但卻十分考察對代碼的掌控能力。

【 題目鏈接 】 【 隨想錄文章講解 】 【 卡哥視頻講解 】

思路：關(guān)鍵點(diǎn)是拐角上的點(diǎn)，求解本題依然是要堅(jiān)持循環(huán)不變量原則，本題的方法是左閉右開。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定義一個(gè)二維數(shù)組
        int startx = 0, starty = 0; // 定義每循環(huán)一個(gè)圈的起始位置
        int loop = n / 2; // 每個(gè)圈循環(huán)幾次，例如n為奇數(shù)3，那么loop = 1 只是循環(huán)一圈，矩陣中間的值需要單獨(dú)處理
        int mid = n / 2; // 矩陣中間的位置，例如：n為3， 中間的位置就是(1，1)，n為5，中間位置為(2, 2)
        int count = 1; // 用來給矩陣中每一個(gè)空格賦值
        int offset = 1; // 需要控制每一條邊遍歷的長度，每次循環(huán)右邊界收縮一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

            // 下面開始的四個(gè)for就是模擬轉(zhuǎn)了一圈
            // 模擬填充上行從左到右(左閉右開)
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            // 模擬填充右列從上到下(左閉右開)
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            // 模擬填充下行從右到左(左閉右開)
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            // 模擬填充左列從下到上(左閉右開)
            for (; i > startx; i--) {
                res[i][j] = count++;
            }

            // 第二圈開始的時(shí)候，起始位置要各自加1， 例如：第一圈起始位置是(0, 0)，第二圈起始位置是(1, 1)
            startx++;
            starty++;

            // offset 控制每一圈里每一條邊遍歷的長度
            offset += 1;
        }

        // 如果n為奇數(shù)的話，需要單獨(dú)給矩陣最中間的位置賦值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

數(shù)組總結(jié)篇

二分法

數(shù)組：每次遇到二分法，都是一看就會，一寫就廢

這道題目呢，考察數(shù)組的基本操作，思路很簡單，但是通過率在簡單題里并不高，不要輕敵。

可以使用暴力解法，通過這道題目，如果追求更優(yōu)的算法，建議試一試用二分法，來解決這道題目

• 暴力解法時(shí)間復(fù)雜度：O(n)
• 二分法時(shí)間復(fù)雜度：O(logn)

在這道題目中我們講到了循環(huán)不變量原則，只有在循環(huán)中堅(jiān)持對區(qū)間的定義，才能清楚的把握循環(huán)中的各種細(xì)節(jié)。

二分法是算法面試中的?？碱}，建議通過這道題目，鍛煉自己手撕二分的能力。

雙指針法

• 數(shù)組：就移除個(gè)元素很難么？

雙指針法（快慢指針法）：通過一個(gè)快指針和慢指針在一個(gè)for循環(huán)下完成兩個(gè)for循環(huán)的工作。

• 暴力解法時(shí)間復(fù)雜度：O(n^2)
• 雙指針時(shí)間復(fù)雜度：O(n)

這道題目迷惑了不少同學(xué)，糾結(jié)于數(shù)組中的元素為什么不能刪除，主要是因?yàn)橐韵聝牲c(diǎn)：

• 數(shù)組在內(nèi)存中是連續(xù)的地址空間，不能釋放單一元素，如果要釋放，就是全釋放（程序運(yùn)行結(jié)束，回收內(nèi)存?？臻g）。
• C++中vector和array的區(qū)別一定要弄清楚，vector的底層實(shí)現(xiàn)是array，封裝后使用更友好。

雙指針法（快慢指針法）在數(shù)組和鏈表的操作中是非常常見的，很多考察數(shù)組和鏈表操作的面試題，都使用雙指針法。

滑動窗口

• 數(shù)組：滑動窗口拯救了你

本題介紹了數(shù)組操作中的另一個(gè)重要思想：滑動窗口。

• 暴力解法時(shí)間復(fù)雜度：O(n^2)
• 滑動窗口時(shí)間復(fù)雜度：O(n)

本題中，主要要理解滑動窗口如何移動 窗口起始位置，達(dá)到動態(tài)更新窗口大小的，從而得出長度最小的符合條件的長度。

滑動窗口的精妙之處在于根據(jù)當(dāng)前子序列和大小的情況，不斷調(diào)節(jié)子序列的起始位置。從而將O(n^2)的暴力解法降為O(n)。

如果沒有接觸過這一類的方法，很難想到類似的解題思路，滑動窗口方法還是很巧妙的。

模擬行為

• 數(shù)組：這個(gè)循環(huán)可以轉(zhuǎn)懵很多人！

模擬類的題目在數(shù)組中很常見，不涉及到什么算法，就是單純的模擬，十分考察大家對代碼的掌控能力。

在這道題目中，我們再一次介紹到了循環(huán)不變量原則，其實(shí)這也是寫程序中的重要原則。

相信大家有遇到過這種情況： 感覺題目的邊界調(diào)節(jié)超多，一波接著一波的判斷，找邊界，拆了東墻補(bǔ)西墻，好不容易運(yùn)行通過了，代碼寫的十分冗余，毫無章法，其實(shí)真正解決題目的代碼都是簡潔的，或者有原則性的，大家可以在這道題目中體會到這一點(diǎn)。文章來源地址http://www.zghlxwxcb.cn/news/detail-426688.html

到了這里，關(guān)于代碼隨想錄Day02：977.有序數(shù)組的平方 ，209.長度最小的子數(shù)組 ，59.螺旋矩陣II的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！