977、有序陣列的平方

·雙指標思想

題目鏈接：https://leetcode.cn/problems/squares-of-a-sorted-array/

前提：按非遞減順序排序的整數陣列
???（存在重復值）
???可能存在負數

思路：負數平方后，陣列元素大小會變成兩頭大中間小，
???適合雙指標進行比較兩頭大小
???陣列從尾巴開始排起比較方便

方法：雙指標法
???時間復雜度O(n);
???空間復雜度O(n);

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int t=nums.size()-1;
        vector<int> nums2(nums.size(),0);
        int j=0;
        for(int i=t;i>=0;i--){
            if(nums[j]*nums[j]>=nums[t]*nums[t]){
                 nums2[i]=nums[j]*nums[j];
                j++;
            }
            else{
                nums2[i]=nums[t]*nums[t];
                t--;
            }
        }
        return nums2;
    }
};

識訓摘要：一開始考慮能不能不建新陣列，不創建新陣列的話，雙指標走過去會出現陣列覆寫情況doge

學習的文章鏈接：https://programmercarl.com/0977.有序陣列的平方.html
學習的視頻鏈接：https://www.bilibili.com/video/BV1QB4y1D7ep

209、長度最小的子陣列

·雙指標思想（滑~ 動~ 視窗）

題目鏈接：https://leetcode.cn/problems/minimum-size-subarray-sum/

前提：最小連續子陣列
???>=target

思路：依舊是雙指標~回圈節是尾巴指標
???雙指標形成一個區間，就是滑~ 動~ 視窗

方法：雙指標優化了暴力解法：兩層回圈O(n^2)
???時間復雜度O(n);
???空間復雜度O(1);

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int l=nums.size();
        int c=0;
        int min=l+1;
        int i=0;
        int j=0;
        long s=0;
        while(i<l){//尾巴指標      
            s=s+nums[i];
            c++;
            while(s-nums[j]>=target){//縮短頭指標，使得子陣列長度盡可能地小
                s=s-nums[j];
                c--;
                j++;
            }
            if(s>=target&&c<min)min=c;
            i++;
        }
        if(min==l+1)min=0;
        return min;
    }
};

識訓摘要：雙指標的優化很巧妙！省去了多余的比較

學習的文章鏈接：https://programmercarl.com/0209.長度最小的子陣列.html
學習的視頻鏈接：https://www.bilibili.com/video/BV1tZ4y1q7XE

59、螺旋矩陣Ⅱ

·邊界模擬

怎么也飛不出~ 螺旋的世界~

題目鏈接：https://leetcode.cn/problems/spiral-matrix-ii/

思路：注意邊界！！仔細再仔細，邊界上的陣列下標要仔細算！

方法：模擬法
???時間復雜度O(n^2);
???空間復雜度O(n^2);

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int count=0;
        int loop=n/2;
        vector<vector<int>> nums(n,vector<int>(n,0));
        int x0=0;
        int j;
        while(loop>0){
            for(j=x0;j<=n-x0-2;j++){
                count++;
                nums[x0][j]=count;
            }
            for(j=x0;j<=n-x0-2;j++){
                count++;
                nums[j][n-x0-1]=count;
            }
            for(j=n-x0-1;j>=x0+1;j--){
                count++;
                nums[n-x0-1][j]=count;
            }
            for(j=n-x0-1;j>=x0+1;j--){
                count++;
                nums[j][x0]=count;
            }
            x0++;
            loop--;
        }
        if(n%2==1)nums[x0][x0]=n*n;
        return nums;
    }
};

識訓摘要：for回圈一層層模擬，主要是螺旋后每一層的陣列的值和下標發生了變化

學習的文章鏈接：https://programmercarl.com/0059.螺旋矩陣II.html
學習的視頻鏈接：https://www.bilibili.com/video/BV1SL4y1N7mV/

學習時長：4h

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/521851.html

標籤：其他

上一篇：MySQL向表中添加列