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

思路：

? ? ? ? 雙指針應(yīng)用

? ? ? ? 因?yàn)閿?shù)組是有序的，數(shù)組中可能存在負(fù)數(shù)，所以其平方的最大值只可能是數(shù)組的頭或尾，因此可以定義兩個(gè)指針，i指向頭，j指向尾。同時(shí)定義一個(gè)新數(shù)組result，讓k指向新數(shù)組的最后一個(gè)元素，當(dāng)nums[i] * nums[i] >= nums[j] * nums[j]，result[k] = nums[i] * nums[i]，k--，i++；nums[i] * nums[i] < nums[j] * nums[j]，result[k] = nums[j] * nums[j]，k--，j--。

代碼：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> result(nums.size(), 0);
        int k = nums.size() - 1;
        for(int i = 0, j = nums.size() - 1; i <= j; ){
            if(nums[i] * nums[i] > nums[j] * nums[j]){
                result[k--] = nums[i] * nums[i];
                i++;
            }else{
                result[k--] = nums[j] * nums[j];
                j--;
            }
        }
        return result;
    }
};
//時(shí)間復(fù)雜度:O(n)

?LeetCode209.長(zhǎng)度最小的子數(shù)組

思路：

? ? ? ? 滑動(dòng)窗口? ? ? ?

窗口就是 滿足其和 ≥ s 的長(zhǎng)度最小的 連續(xù) 子數(shù)組。

窗口的起始位置如何移動(dòng)：如果當(dāng)前窗口的值大于s了，窗口就要向前移動(dòng)了（也就是該縮小了）。

窗口的結(jié)束位置如何移動(dòng)：窗口的結(jié)束位置就是遍歷數(shù)組的指針，也就是for循環(huán)里的索引。

解題的關(guān)鍵在于 窗口的起始位置如何移動(dòng)。

具體分析：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html#%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3

代碼：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT32_MAX;
        int Sublength = 0;
        int i = 0;
        int sum = 0;
        for (int j = 0; j < nums.size(); j++){
            sum += nums[j];
            while(sum >= target){
                Sublength = j - i + 1;
                result = result < Sublength ? result : Sublength;
                sum -= nums[i++];
            }
        }
        return result == INT32_MAX ? 0 : result;
    }
};
//時(shí)間復(fù)雜度：O(n)

LeetCode59.螺旋矩陣II

思路：

????????堅(jiān)持了每條邊左閉右開(kāi)的原則。

具體分析見(jiàn)：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html#%E6%80%9D%E8%B7%AF文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-419812.html

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; // 用來(lái)給矩陣中每一個(gè)空格賦值
        int offset = 1; // 需要控制每一條邊遍歷的長(zhǎng)度，每次循環(huán)右邊界收縮一位
        int i,j;
        while (loop --) {
            i = startx;
            j = starty;

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

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

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

        // 如果n為奇數(shù)的話，需要單獨(dú)給矩陣最中間的位置賦值
        if (n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};
//時(shí)間復(fù)雜度：O(n^2)
//空間復(fù)雜度：O(1)

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