算法训练第二天|977.有序数组的平方、209.长度最小的有序数组、59.螺旋矩阵2-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法训练第二天|977.有序数组的平方、209.长度最小的有序数组、59.螺旋矩阵2。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

977.有序数组的平方

题目链接：力扣

思路:同样使用双指针的方法，这样就可以只遍历一次原数组。

可以考虑需要按照一个顺序来遍历，那就是从大到小或者从小到大，我选择的是从大到小。

不难看出，原数组将每个数平方后，呈现从两边到中间逐渐减小的规律。

所以使用一个指针指向原数组最左端，一个指向最右端，比较那边的数大，就是原数组中最大的数。

我们新建一个数组，用来存放已经排好序的数组，按照从大到小放数据应该是从数组尾开始放。

时间复杂度：o(n)

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        //这个个地方用.size()函数来求数组的长度，注意是vector数组的函数方法
        int len=nums.size();
        for(int i=0;i<len;i++) nums[i] = nums[i]*nums[i];
        //需要注意这里vector数组的定义方法，不会就搜索一下
        vector<int> numss(len);
        //这里使用双指针i,j来遍历原数组
        //同时用一个指针来完成将数据放入排序好的数组
        int i=0,j=len-1,k=len-1;
        //这里每个人可以根据个人喜好使用不同的循环语句，for循环也可以做到
        while(true){
            if(nums[i]<nums[j]){
                numss[k]=nums[j];
                j--;
            }
            else{
                numss[k]=nums[i];
                i++;
            }
            k--;
            if(k<0) break;
        }
        return numss;
    }
};

本题的难点在于如何考虑到只用时间复杂度为o(n)的方法，即只遍历一次原数组，需要根据平方后的原数组找到按从大到小或从小到大的规律。

209.长度最小的子数组

题目链接：力扣

思路：使用滑动窗口的方法，我们可以想到子序列的变化方法就是，当子序列之和大于目标值，就要从开头减去一个，小于目标值时，就要从后面再添加进一个。

但是我们要考虑所有子序列的可能性，即所有的数组元素都可能成为子序列的开头或结尾，当我选择子序列是从左往右滑动时，那么子序列的结尾是规律的，即每次添加一个元素。

而对应于每个子序列的结尾，子序列的开头可以是在这之前的任意一个元素，但实际上却并不用考虑在这之前的每个元素，因为当结尾在往右遍历时，开头也在往右遍历，我们只需考虑当前开头的后面元素，而不必考虑当前开头的之前元素。

时间复杂度：nlogn

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        //用result来表示最短子序列的长度，先将其赋值为整形最大值是考虑到每次都是按子序列长度更小的进行赋值，本题中数组可能不存在满足条件的子序列，则result没有被赋值，输出0；
        int result = INT_MAX;
        //用sum来表示当前子序列内所有数的和
        int sum=0;
        //用i来表示子序列开头的位置
        int i=0;
        for(int j=0;j<nums.size();j++){
            //j是用来表示子序列结束的位置，因为我们考虑到数组的每个元素都有可能成为子序列的结束位置。
            sum+=nums[j];
            //当添加一个元素进去后，那么子序列的总和就有可能超过目标元素，此时我们需要将子序列中元素减去一个，很显然就是从开头减去，因为子序列是连续的。
            while(sum>=target){
                //len表示子序列的长度
                int len=j-i+1;
                //此时result是表示所有满足条件的自序中长度最小的，所以它是一个要和所有长度比较的变量，遇到更小的就赋值。
                result=result>len?len:result;
                sum-=nums[i];
                i++;

            }
        }
        return result==INT_MAX?0:result;

    }
};

滑动窗口的运用让我想到字符串匹配是不是也可以用这种方法？只要是连续的子序列仿佛都可以用。

59.螺旋矩阵2

题目：力扣

思路：数组里的题最难的就是找出规律，当规律被发现了，答案也就浮出水面了。

看到这题，相信每个人都能想到，需要四条边逐边进行赋值，那么比较难的就是进行四条边的规律统一，首先找到的就是每四条长度相等的且互相不重复的边可以构成一个完整的圈，每条边包含一个拐点。

首先思考每次循环一圈的起点在哪里，自己在纸上写一个n=5比较大的循环，就可以发现每次的起点在数组的主对角线上。此处需要一个变量来表示。

其次我们也观察到，每一圈每一条边需要赋值的元素都在减少一此处也需要一个变量表示。但我没用这个变量表示每条边需要走的步数，而是用每圈右边界少抵达的坐标来表示。这样间接可以用起点减去这个边界来表示要走的步数。

最后发现，当n为奇数时，所有的圈走完，还剩中心一个元素没有赋值，我们需要单独为它赋值。

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int>(n,0));
        //用来表示每圈的起点坐标
        int starti=0,startj=0;
        //key用来控制需要循环几圈
        int key=n/2;
        //count用来表示需要填入数组的数1，2，3，4...
        int count=1;
        //用来控制左右边界需要收缩多少，每次循环右边界多收缩一位，从第二次循环开始左边界收缩一位，其实就是每次循环，一条边走几步
        int bianjie=1;
        while(key--){
            int i=starti,j=startj;
            for(;j<n-bianjie;j++) res[i][j]=count++;
            for(;i<n-bianjie;i++) res[i][j]=count++;
            for(;j>startj;j--) res[i][j]=count++;
            for(;i>starti;i--) res[i][j]=count++;
            starti++;
            startj++;
            bianjie++;
        }
        if(n%2==1) res[starti][startj]=count;
        return res;
    }
};

本题难点在于找到规律，和寻找自己需要表示的变量，应该不用自己想出来怎么写，只要看懂别人的思路，然后自己能敲出来代码，以后碰到类似的题能想起来这个思路就行。文章来源地址https://www.toymoban.com/news/detail-421438.html

到了这里，关于算法训练第二天|977.有序数组的平方、209.长度最小的有序数组、59.螺旋矩阵2的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！