代码随想录算法训练营第二天 | Leetcode977，Leetcode209，Leetcode59

Leetcode977

题目：

写的贼长还Debug不出来的代码,后来发现我想手动快排不如直接调用Sort（），代码经验太少了——失败

自己写的垃圾代码：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int Size,left=0,right,i,tmp,A[10000],Zero,mid=1;
        Size=nums.size();
        right=Size-1;
         if(Size==1)
         {
            nums[0]= pow(nums[0],2);
            return nums;
         }
        if(nums[0]>0)
        return nums;
        
        for(i=0;i<Size-1;i++)
        {
            if(nums[i]<0&&nums[i+1]>=0)
            {
                Zero=i+1;
            }
            nums[i]=pow(nums[i],2);
        }
        
        left=Zero-1;
        right=Zero+1;
        A[0]=nums[Zero];
        while(left>=0&&right<Size-1)
        {
            if(left>0&&nums[left]<=nums[right])
            {
                A[mid++]=nums[left];
                left--;
            }
            if(right<Size-1&&nums[left]>nums[right])
            {
                A[mid++]=nums[right];
                right++;
            }
            if(left==0&&right==Size-1)
            {
                if(nums[left]>nums[right])
                {
                    A[mid++]=nums[right];
                    A[mid++]=nums[left];
                }
                else 
                {
                    A[mid++]=nums[left];
                    A[mid++]=nums[right];    
                }
            }
        }
         for(i=0;i<Size;i++)
            {
                nums[i]=A[i];
            }
        return nums;
    }
};

暴力解法（复杂度O（nlogn））：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int Size,left=0,right,i,tmp,A[10000],Zero,mid=1;
        Size=nums.size();
        for(i=0;i<Size;i++)
        {    
            nums[i]=pow(nums[i],2);
        }
        sort(nums.begin(), nums.end());
       return nums;
    }
};

双指针解法：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int Size,left,right,A[10000],mid,i;
        Size=nums.size();
        left=0;
        right=Size-1;
        for(i=Size-1;i>=0;i--)
        {
            if(nums[left]*nums[left]<=nums[right]*nums[right])
            {
                A[i]=nums[right]*nums[right];
                right--;
            }
            else if(nums[left]*nums[left]>nums[right]*nums[right])
            {
                A[i]=nums[left]*nums[left];
                left++;
            }
        }
        for(i=0;i<Size;i++)
        {
            nums[i]=A[i];
        }
       return nums;
    }
};

感悟:

•  代码写少了，没想到直接可以调用快排sort（），导致手撕快排代码半天
• 双指针没想到还可以这么用，以后继续加油熟悉

  ---

 Leetcode209

本人暴力解法：（似滑非滑）

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left,right,Size,i,sum=0,lr;
        Size=nums.size();
        left=0;
        right=0; 
            while(sum<target&&right<Size)
            {
                sum+=nums[right];
                right++;
            }
            lr=right;
            if(right==Size&&sum<target)
            {
                return 0;
            }
            else if(sum>=target&&right<=Size){
                while(right<=Size)
                {
                    if(right<Size)
                    sum+=nums[right++];
                    while(sum-nums[left]>=target)
                    {
                        sum-=nums[left];
                        left++;    
                    }
                    if(lr>right-left)
                    {
                        lr=right-left;
                    }
                    if(sum-nums[left]<target&&right==Size)
                         break;
                }
                
            }
         
                return lr;
            }
            
};

滑动窗口 

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        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++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

感悟：

• 明白要更改滑动开始值和结束值，但是在窗口滑动上选择while并不明智，while的条件判断比For循环难找很多，对于每个元素都要查看的循环来说，for循环更加适合。 

Leetcode59 螺旋矩阵2

 标准解法

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> array(n,vector<int>(n,0));
        int loop=n/2,i,j,m=1,s=0,n2=n*n,n3=n/2;
        int startx=0;
        int starty=0;
 
        while(loop--)
        {
            i=startx;
            j=starty;
            for(j=starty;j<n-m;j++)
            {
                array[startx][j]=(++s);
            }
            for(i=startx;i<n-m;i++)
            {
                array[i][j]=(++s);
            }
            for(;j>starty;j--)
            {
                array[i][j]=(++s);
            }
            for(;i>startx;i--)
            {
                array[i][j]=(++s);
            }
            
            startx++;
            starty++;
            m++;
        }
        if(n%2==1)
        {
            array[n3][n3]=++s;
        }
        return array;
    }
};

感悟：

• 遇见模拟的题目是一点也没头绪，没想到用这种循环的方式可以做，以后还是要对相关题目多加练习