Leetcode 977-有序數(shù)組的平方 ｜ LeetCode209-長度最小的子數(shù)組 | Leetcode59-螺旋矩陣

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

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

示例 1： 輸入：nums = [-4,-1,0,3,10] 輸出：[0,1,9,16,100] 解釋：平方后，數(shù)組變?yōu)?[16,1,0,9,100]，排序后，數(shù)組變?yōu)?[0,1,9,16,100]

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

方法一-雙指針法

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
    int left = 0;
    int n = nums.size();
    int right = n-1;
    vector <int>result(n,0);              //  定義一個長度為nums.size()的動態(tài)數(shù)組
    while(left<=right)                               
    {
    if(nums[left] * nums[left]<nums[right] * nums[right])
    {
    result[n-1]=nums[right] * nums[right];     //比較前后倆個指針指向的值將大的數(shù)從后往前排
    n--;
    right--;
    }
    else
    {
     result[n-1]=nums[left] * nums[left];
     n--;
     left++;
    }
    }
    return result;
    }
};

思考：

• 這個數(shù)組為有序數(shù)組，那么即使前面有負的，數(shù)組平方的最大值只能是在數(shù)組的倆端，不是在左邊就是右邊，不可能是在中間
  由此想到雙指針做法，left從前往后，right從后往前，將大的放在新創(chuàng)建數(shù)組的末端
  注意循環(huán)終止的條件，這邊left==right也是有意義的

方法二-暴力排序

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        for (int i = 0; i < A.size(); i++) {
            A[i] *= A[i];
        }
        sort(A.begin(), A.end()); // 快速排序
        return A;
    }
};

LeetCode209-長度最小的整數(shù)組

給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) target 。

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

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

方法一-暴力解法

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
    int result = INT_MAX;         //INT32_MAX可以看成一個相當大的數(shù)
    int sum = 0;
    int sublength = 0;
    int n = nums.size();
    if(n==0) return 0;
    for(int i = 0;i<n;i++)      //i為最小子數(shù)組的起點
    {
    sum = 0;                //每次重新移動起點都要將sum賦值為0
        for(int j = i;j<n;j++)  //j為最小子數(shù)組的終點
        {
        sum += nums[j];
        if(sum>=target)             //當發(fā)現(xiàn)子序列超過sum的時候更新result
        {
        sublength = j-i+1;
        result = result <sublength ? result : sublength;
        break;              //找到最小子序列時跳出循環(huán)
        }
        }
    }
    return result == INT_MAX ? 0 : result;        //result沒有被賦值的話就返回0
    }
};

• 思路：用倆個for循環(huán)尋找子列
• INT_MAX = 2^31-1，INT_MIN= -2^31. 可以看出是一個相當大的數(shù)和一個相當小的數(shù)，如果想要得到數(shù)組中最小值，可以先將最小值賦值為INT_MAX ；
  同理如果想要得到數(shù)組中最大值，可以先將最大值賦值為INT_MIN ；

方法二-滑動窗口

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
    int result = INT_MAX;
    int sum = 0  ;//滑動窗口之和
    int sublength = 0; //滑動窗口的長度
    int i = 0; //滑動窗口的起始位置
    int n = nums.size();
    for(int j = 0; j<n;j++)
    {
    sum += nums[j];
    while(sum>=target)
    {
    sublength = j-i+1;
    result = result< sublength ? result :sublength;
    sum -= nums[i++];   //滑動指針 從sum中減去起始位置的值并且 移動起始位置
    }
    }
    return result==INT_MAX ? 0 : result;  //判斷是否能找到最小的子數(shù)組不能則返回0
    }
};

思路：
利用滑動窗口（起始就是雙指針）
for循環(huán)中遍歷的是 窗口末端位置。為什么只用一個for循環(huán)便利就能達到預(yù)期效果呢？這邊類似一個滑動的窗口，當窗口的末端位置向后移動時，滿足sum>=target的條件后就要將起始位置的指針移動，滿足條件的話不斷更新result的值，使其能成為最小的子序列。

Leetcode59-螺旋矩陣

給你一個正整數(shù) n ，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的 n x n 正方形矩陣 matrix 。文章來源地址http://www.zghlxwxcb.cn/news/detail-587776.html

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

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> res(n,vector<int>(n,0));    //使用vector定義一個二維數(shù)組
    int startx = 0,starty = 0; //定義每循環(huán)一個圈的起始位置
    int loop = n/2; //每個圈循環(huán)的次數(shù)
    int middle = n/2; //矩陣中間的位置
    int count = 1;  //給矩陣中每一個空格賦值
    int offset = 1; //勇于控制每一條邊遍歷的長度
    int i,j;
    while(loop--)
    {
    i = startx;
    j = starty;
    
        
        //四個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++;
    }
    
    startx++;
    starty++;           //從第二圈開始起始位置都各自+1
    offset+=1;          //offset控制每一條邊遍歷的長度
    }
    if(n%2)
    {
        res[middle][middle]=count;  //如果n為奇數(shù)的話，需要單獨給矩陣最中間的值賦值
    }
        return res;
    }
};

• 思路： 堅持循環(huán)不變量-每次循環(huán)里都要遵循同一套規(guī)則，必須保持一些變量的不可變。 這邊始終堅持左閉右開的原則
  —填充上行從左到右；填充右列從上到下；填充下行從右到左；填充左列從下到上

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