您现在的位置是:首页 >技术杂谈 >代码随想录算法训练营15期 Day 2 | 977.有序数组的平方 、209.长度最小的子数组 、59.螺旋矩阵II 、总结网站首页技术杂谈

代码随想录算法训练营15期 Day 2 | 977.有序数组的平方 、209.长度最小的子数组 、59.螺旋矩阵II 、总结

ASDWYang 2024-06-26 14:23:30
简介代码随想录算法训练营15期 Day 2 | 977.有序数组的平方 、209.长度最小的子数组 、59.螺旋矩阵II 、总结

977.有序数组的平方 

题目建议: 本题关键在于理解双指针思想 

题目链接:力扣

思路一:暴力解算,直接将所有元素变成一个平方,然后进行排序。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {

        for(int i = 0;i<nums.size();i++)
        {
            nums[i]=nums[i]*nums[i];
        }
        sort(nums.begin(),nums.end());
        return nums;
    }
};

思路二:双指针法,首先声明一个数组与原始的数组大小相同,然后由两头的指针由大到小进行排序。

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {

        //首先声明一个数组长度与原始的大小相同
        vector<int> nums1(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])
            {
                nums1[k--]=nums[j]*nums[j];
                j--;
            }
            else
             {
                nums1[k--]=nums[i]*nums[i];
                i++;
            }
        }
        return nums1;
    }
};

 209.长度最小的子数组

题目建议: 本题关键在于理解滑动窗口,这个滑动窗口看文字讲解 还挺难理解的,建议大家先看视频讲解。  拓展题目可以先不做。

题目链接:力扣 

思路一:直接暴力计算,时间很长,不建议。
思路二:双指针法,使用两个指针将中间的数组提取出来。
双指针一般是使用一个for循环做了两个for循环的事情。

起始位置使用i表示,终止位置使用j表示。起始位置与终止位置之间的差距大于等于s,则进行改变。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        
        int result = INT32_MAX;//声明最大的长度
        int i = 0;//起始位置
        int sum = 0;//和

        int length = INT32_MAX;//长度

        for(int j = 0;j<nums.size();j++)//终止位置
        {
            sum+=nums[j];
            while(sum>=target)//注意是while
            {
                
                length = j - i + 1;
                sum = sum-nums[i];
                i++;//起始位置向前移动
                result = result < length ? result : length;
            }
            


        }
        return result<INT32_MAX?result:0;

    }
};

59.螺旋矩阵II

题目建议:  本题关键还是在转圈的逻辑,在二分搜索中提到的区间定义,在这里又用上了。

题目链接:力扣

关键在于四个边界的条件处理,一入循环深似海。注意循环不变量,坚持一个规则处理每一个边,按照左闭右开的规则。

由于一圈等于两行两列,因此,转动的是n/2圈。需要判断转动的圈数是奇数还是偶数。左闭右开,终止位置是不包含的。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        //起始位置
        int startx = 0;
        int starty = 0;

        //偏移量
        int offset = 1;

        //声明一个二维数组
        vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组

        //加入的数字
        int count = 1;

        //转动圈数
        int circle = n/2;
        while(circle--)//转动的圈数
        {
            int i,j;
            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++;
            offset++;
        }
        if(n%2 == 1)
        {
            res[n/2][n/2]=n*n;
        }
        return res;
    }
};

 

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。