代碼随想錄算法訓練營第二天 | 977.有序數組的平方 、209.長度最小的子數組 、59.螺旋矩陣II、總結

打卡第二天，認真做了兩道題目，頂不住了好困，明天早上練完車回來再重新看看。

今日任務

第一章數組

• 977.有序數組的平方
• 209.長度最小的子數組
• 59.螺旋矩陣II

977.有序數組的平方

給你一個按 非遞減順序 排序的整數數組 nums，傳回 每個數字的平方 組成的新數組，要求也按 非遞減順序 排序。

示例 1:
輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方後，數組變為 [16,1,0,9,100]
排序後，數組變為 [0,1,9,16,100]
           

示例 2:
輸入：nums = [-7,-3,2,3,11]
輸出：[4,9,9,49,121]
           

提示：

• 1 <= nums.length <= 1 0 4 10^4 104
• − 1 0 4 -10^4 −104 <= nums[i] <= 1 0 4 10^4 104

• nums 已按 非遞減順序 排序

  進階：

• 請你設計時間複雜度為 O(n) 的算法解決本問題

我的解題

暴力做法

void quick_sort(vector<int> &q, int l, int r) {
    if(l >= r) return;
    int i = l - 1, j = r + 1, x = q[(l + r) >> 1];
    while(i < j) {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}
vector<int> sortedSquares(vector<int>& nums) {
    for(int i = 0; i < nums.size(); i++) nums[i] *= nums[i];
    quick_sort(nums, 0, nums.size() - 1);
    // sort(nums.begin(), nums.end());
    return nums;
}
           

看完題目第一想法，暴力把數組每一個數的平方先的出來，然後快排。

雙指針做法

vector<int> sortedSquares(vector<int>& nums) {
    vector<int> res(nums.size(), 0);
    int z = 0;
    while(z < nums.size() && nums[z] < 0) ++z;
    int k = 0, i = z - 1, j = z;
    while(i >= 0 && j < nums.size()) {
        if(nums[i] * nums[i] <= nums[j] * nums[j]) {
            res[k++] = nums[i] * nums[i];
            i--;
        } else {
            res[k++] = nums[j] * nums[j];
            j++;
        }
    }
    while(i >= 0) {
            res[k++] = nums[i] * nums[i];
            i--;
    }
    while(j < nums.size()){
            res[k++] = nums[j] * nums[j];
            j++;
    }
    return res;
}
           

雙指針想法，因為是非遞減數組，有正數負數，平方之後中間的數小，兩邊的大。

• 建立一個數組res，存放結果。
• 找到第一個正數下标z，因為是非遞減數組，是以從這個數開始分成兩邊，平方之後左邊 <- 越來越大，右邊 -> 越來越大，
• 比較 n u m s [ i ] ( i = z − 1 ) ， n u m s [ j ] ( j − z ) nums[i] (i = z - 1)，nums[j] (j - z) nums[i](i=z−1)，nums[j](j−z)下标的值的平方哪個更小，小的存入結果數組res，移動指針。如果 n u m s [ i ] ∗ n u m s [ i ] < n u m s [ j ] ∗ n u m s [ j ] nums[i] * nums[i]< nums[j] * nums[j] nums[i]∗nums[i]<nums[j]∗nums[j], 将 n u m s [ i ] ∗ n u m s [ i ] nums[i] * nums[i] nums[i]∗nums[i] 存入 res, i 往左邊移動一格。
• 當i，j 某一個指針到了邊界，将另外一個還沒到邊界的指針後面的值平方存到結果數組。注意 i ，j指針一個往左，一個往右。

看完卡哥的題解，發現自己把題目搞複雜了，直接在頭尾兩邊定義指針，把大的平方數的指針指向的數的平方，存到結果數組（從後往前存放）就行，當指針相遇後結束就可以了。

代碼随想錄

看完卡哥的題解，

vector<int> sortedSquares(vector<int>& nums) {
    vector<int> res(nums.size(), 0);
    int i = 0, j = nums.size() - 1;
    int k = nums.size() - 1;
    for(int i = 0, j = nums.size() - 1; i <= j;) {
        if(nums[i] * nums[i] >= nums[j] * nums[j]) {
            res[k--] = nums[i] * nums[i];
            i++;
        } else {
            res[k--] = nums[j] * nums[j];
            j--;
        }
    }
    return res;
}
           

209.長度最小的子數組

給定一個含有 n 個正整數的數組和一個正整數 target 。

找出該數組中滿足其和 ≥ target 的長度最小的 連續子數組 [numsl, numsl+1, …, numsr-1, numsr] ，并傳回其長度。如果不存在符合條件的子數組，傳回 0 。

示例1：
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數組 [4,3] 是該條件下的長度最小的子數組。
           

示例2：
 輸入：target = 11, nums = [1,1,1,1,1,1,1,1]
輸出：0
           

提示：

• 1 <= target <= 1 0 9 10^9 109
• 1 <= nums.length <= 1 0 5 10^5 105
• 1 <= nums[i] <= 1 0 5 10^5 105

題解

int minSubArrayLen(int target, vector<int>& nums) {
    int result = INT_MAX;
    int sum = 0; // 滑動視窗的值
    int hh = 0; // 滑動視窗的起始位置
    int length = 0; // 滑動視窗的長度
    for(int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        while(sum >= target) {
            length = i - hh + 1;
            result = min(result, length);
            sum -= nums[hh++];
        }
    }
    if(result != INT_MAX) return result;
    else return 0;
}
           

這道題之前做過，也看過卡哥的視訊，知道用滑動視窗，但是忘記怎麼寫了，又重新溫習了一遍。

定義一個滑動視窗，把原數組的值加到視窗裡面并且計算總值，當總值超過目标值，開始從視窗頭縮小視窗，直到滑動數組的值不超過目标值，繼續往視窗加原數組的值，直到周遊完數組。

59.螺旋矩陣II

給你一個正整數 n ，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的 n x n 正方形矩陣 matrix 。

示例1：
輸入：n = 3
輸出：[[1,2,3],[8,9,4],[7,6,5]]
           

示例2：
 輸入：n = 1
輸出：[[1]]
           

題解

vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> result(n, vector<int>(n, 0)); // 使用vector定義一個二維數組
        int startx = 0, starty = 0;
        int offset = 1; // 圈數縮小大小
        int count = 1;
        int i = 0, j = 0;
        int loop = n / 2; // 矩陣循環圈數
        int mid = n / 2;
        while(loop--) {
            i = startx;
            j = starty;
            for(j = starty; j < n - offset; j++) {
                result[startx][j] = count++;
            }
            for(i = startx; i < n - offset; i++) {
                result[i][j] = count++;
            }
            for(;j > starty; j--) {
                result[i][j] = count++;
            }
            for(; i > startx; i--) {
                result[i][starty] = count++;
            }
            startx++;
            starty++;
            offset++;
        }
        // 如果n為奇數的話，需要單獨給矩陣最中間的位置指派
        if (n % 2) {
            result[mid][mid] = count;
        }
        return result;
    }