算法DAY02

这篇具有很好参考价值的文章主要介绍了算法DAY02。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

977-有序数组的平分-双指针法

思路

nums数组是由小到大排序,平方之后要么是个V型,要么还是由小到大,设立两个指针leftindexrightindex指向平方后nums数组一头一尾,比较这一头一尾,另外建一个result数组(大小和nums一样),k指向result最后一个元素,将比较出来的较大值放在result数组第k个位置上,然后k–leftindex++(或rightindex–),直到leftindex==rightindex,将nums[rightindex]放在result[0]

code

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

209-长度最小的子数组-滑动窗口

思路

我的思路是外层while循环判断right是不是到达了边界,内层先是for循环找到当前left不能 继续sum+=sum[right]的情况:
有可能是 1:sum>=target,然后判断当前窗口长度now和min的大小
也有可能是
2:right==nums.size()
,应该break跳出while循环。

code

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        long long left=0,right=1;
        long long min=INT32_MAX;
        long long sum=nums[0];
        while(right<=nums.size()){//right一直是下一个要+的元素,也就是sum目前的值是[left...right-1]的和
            for(;sum<target&&right<nums.size();right++){
            sum+=nums[right];
            }
            if(right==nums.size()&&sum<target)//right到了尾部,还是不满足条件,就退出while循环
                {break;}
            else if(sum>=target){//find a 连续子数组
                long long now=right-left;
                if(now<min){
                    min=now;
                }
                sum-=nums[left];
                left++;
            }
        }
        return min==INT32_MAX?0:min;
    }
};

还有来自代码随想录的:
外层for循环,内层while循环,直接找到sum>=target&&right<nums.size()的情况,然后去计算now,和min比较,再缩小窗口。

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;
    }
};

59-螺旋矩阵

思路

要填充的是一个边长为n的正方形,把未填充的边长为length的正方形的最外圈作为一次循环,按顺序分为四步操作:
算法DAY02

1. i=startx,starty<=j<starty+length
2. startx<=i<startx+length,j=starty+length
3. i=startx+length,starty+length>=j>starty
4. startx+length>=i>startx,j=starty

code

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int startx=0,starty=0;
        int loop=n/2;
        int length=n-1;//最开始一圈,每一步要遍历的长度
        int num=1;//要填充的数
        vector<vector<int>> squ(n,vector<int>(n,0));
        while(loop--){
            int i;
            int j;
            for(j=starty;j<starty+length;j++){
                squ[startx][j]=num++;
            }
            for(i=startx;i<startx+length;i++){
                squ[i][j]=num++;
            }
            for(j=starty+length;j>starty;j--){
                squ[i][j]=num++;
            }
            for(i=startx+length;i>startx;i--){
                squ[i][j]=num++;
            }
            startx++;
            starty++;
            length-=2;
        }
        if(n%2){
            squ[n/2][n/2]=num;
        }
        return squ;
    }
};

数组总结

算法DAY02文章来源地址https://www.toymoban.com/news/detail-441055.html

到了这里,关于算法DAY02的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法训练 Day 2 | 数组:977.有序数组的平方,209.长度最小的子数组,59.螺旋矩阵II

    977. 有序数组的平方 第一想法:暴力破解 看完题解想法:朝着双指针方向想 遇到困难: 用双指针的话,一开始想到两边指针往中间靠,逐个将最大值赋给结果数组。和题解不同的是,循环条件我写了  while (left != right) {...} ,相比于题解的  while (left = right) {...} ,我需要在后

    2023年04月12日
    浏览(47)
  • 【每日算法 && 数据结构(C++)】—— 02 | 数组的并交集(解题思路、流程图、代码片段)

    When you feel like giving up, remember why you started. 当你想放弃时,请记住为什么你开始 给你两个数组,请分别求出两个数组的交集和并集 在数学中,我们可以通过交集和并集来描述两个集合之间的关系。 交集(Intersection) :指的是两个集合中共有的元素组成的集合。可以用符号

    2024年02月11日
    浏览(53)
  • 算法刷题Day 23 修剪二叉搜索树+将有序数组转换为二叉搜索树+把二叉搜索树转换为累加树

    递归 好神奇,完全凭感觉写,感觉应该过不了,结果就过了 具体是什么原理可以参考代码随想录的讲解 递归 迭代 使用三个队列来处理(感觉用三个栈也可以) 其实就是以右-中-左的顺序来处理二叉树 每次将当前节点加上上一次访问节点的新值 能想到保存前一次访问节点的

    2024年02月15日
    浏览(42)
  • 【每日算法 && 数据结构(C++)】—— 01 | 平方值去重统计(解题思路STL法,双指针法、流程图、代码片段)

    “Success is not final, failure is not fatal: It is the courage to continue that counts.” - Winston Churchill (成功并非终点,失败并非致命:真正重要的是继续前行的勇气 - 温斯顿·丘吉尔) 给你一个整数数组,数组中的数可以是正数、负数、零,请实现一个函数,返回这个数组中所有数的平方

    2024年02月12日
    浏览(54)
  • Day 2 数组:977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵Ⅱ

    977.有序数组的平方 题目链接 💡思路 暴力解法 将数组内每个数平方每个数平方之后,按升序排序 代码如下: 时间复杂度: O (   n l o g n ) O( nlogn) O (   n l o g n ) 空间复杂度: O ( 1 ) O(1) O ( 1 ) 时间复杂度具体分析: for循环: O(n) 快速排序 : O(nlogn) 因此时间复杂度是 O (  

    2024年02月10日
    浏览(53)
  • 有序数组的平方、长度最小的子数组、螺旋矩阵II(Day2)

    题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/ 第一反应暴力如上代码 下面写一段用双指针思想的代码 题目链接:https://leetcode.cn/problems/minimum-size-subarray-sum/ 本题暴力解法会超时,以下采用滑动窗口的方式(将暴力的两个for循环变成一个) 题目链接:https://leetcode.cn/

    2023年04月26日
    浏览(42)
  • 代码随想录day2|有序数组的平方、长度最小的子数组、螺旋矩阵

    前言:今天去校医院拔了两颗牙,太痛了,今天写的博客就比较水。 所谓滑动窗口,就是不断的调节 子序列的起始位置和终止位置 ,从而得出我们要想的结果。

    2024年02月01日
    浏览(49)
  • 【算法-数组】有序数组的平方

    给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 示例 1: 输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 [16,1,0,9,100] 排序后,数组变为 [0,1,9,16,100] 不停地比较首尾元素平方的大小,并将较大

    2024年04月11日
    浏览(37)
  • LeetCode-Day2-977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,

    双指针法,原来数组是有序的,说明平房之后最左和最右两边的平方和是最大的,比较最大的插入新的vector数组,然后移动指针选下一个元素进行比较。 接下来就开始介绍数组操作中另一个重要的方法: 滑动窗口 。 所谓滑动窗口, 就是不断的调节子序列的起始位置和终止

    2024年02月16日
    浏览(46)
  • 算法刷题-数组-有序数组的平方

    力扣题目链接 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 示例 1: 输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 [16,1,0,9,100],排序后,数组变为 [0,1,9,16,100] 示例 2: 输入:nums = [-7,-

    2024年02月08日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包