首页 > 其他分享 >代码随想录day31|| 56合并区间 738 递增数字

代码随想录day31|| 56合并区间 738 递增数字

时间:2024-08-03 16:52:38浏览次数:15  
标签:vector 合并 56 随想录 day31 intervals result 区间 strNum

56合并区间 

力扣题目链接

题目描述:

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 1:

输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

代码:(自己写的,省空间但是时间复杂度高)

class Solution {  
public:  
    // 比较函数,用于排序区间  
    static bool cmp(vector<int> &a, vector<int> &b) {  
        // 按照区间的起始值进行升序排序  
        return a[0] < b[0];  
    }  
    
    vector<vector<int>> merge(vector<vector<int>>& intervals) {  
        // 首先对区间按照起始值排序  
        sort(intervals.begin(), intervals.end(), cmp);  
        
        // 从第二个区间开始遍历  
        for (int i = 1; i < intervals.size(); i++) {  
            // 如果当前区间的起始值小于等于前一个区间的结束值,表示有重叠  
            if (intervals[i - 1][1] >= intervals[i][0]) {  
                // 合并两个重叠的区间,更新前一个区间的结束值  
                intervals[i - 1][1] = max(intervals[i][1], intervals[i - 1][1]);  
                // 删去当前区间,因为它已与前一个区间合并  
                intervals.erase(intervals.begin() + i);  
                // 回退i的值,以便继续检查合并后的新前一个区间  
                i--; // 重要:必须将i减1以重新检查合并后的区间  
            }  
        }  
        // 返回合并后的区间集合  
        return intervals;  
    }  
};  

代码解释:

  1. 类与函数定义:

    • class Solution:定义了一个名为 Solution 的类。
    • vector<vector<int>> merge(vector<vector<int>>& intervals):这是类 Solution 中的一个公共成员函数,接受一个二维整数数组 intervals,返回合并后的区间数组。
  2. 排序:

    • sort(intervals.begin(), intervals.end(), cmp):使用自定义比较函数 cmp 依据每个区间的起始值对区间进行排序,以确保处理时能够顺序检查重叠情况。
  3. 合并区间:

    • 使用 for 循环从第一个区间之后开始遍历。对于每个区间,如果当前区间的起始值小于或等于前一个区间的结束值,说明这两个区间有重叠。
    • 使用 max 函数更新合并后的区间的结束值,确保它覆盖了两个区间。
    • 通过 erase 方法删除当前区间,后续可以继续检查合并后是否还有新的重叠。
  4. 返回结果:

    • 最后,函数返回合并后的区间集合。

整体思路:

  • 首先对区间进行排序,以方便合并。
  • 通过遍历检查并合并所有重叠的区间。
  • 删除已合并的区间并返回不重叠的结果集。

代码二(省时间)

class Solution {  
public:  
    vector<vector<int>> merge(vector<vector<int>>& intervals) {  
        vector<vector<int>> result; // 用于存放合并后的区间结果  
        if (intervals.size() == 0) return result; // 如果区间集合为空,直接返回空结果  
        
        // 按照每个区间的起始值进行升序排序,使用lambda表达式作为比较函数  
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {  
            return a[0] < b[0];  
        });  

        // 将第一个区间加入结果集,因为这是最小的区间  
        result.push_back(intervals[0]);   

        // 从第二个区间开始遍历  
        for (int i = 1; i < intervals.size(); i++) {  
            // 检查当前区间的起始值是否小于等于结果集中最后一个区间的结束值  
            if (result.back()[1] >= intervals[i][0]) {   
                // 发现重叠区域,合并区间  
                // 只需更新结果集中最后一个区间的结束值  
                result.back()[1] = max(result.back()[1], intervals[i][1]);   
            } else {  
                // 如果没有重叠,直接将当前区间加入结果集  
                result.push_back(intervals[i]);   
            }  
        }  
        // 返回合并后的区间集  
        return result;  
    }  
};  

代码解释:

  1. 类与函数定义:

    • class Solution:定义了一个名为 Solution 的类。
    • vector<vector<int>> merge(vector<vector<int>>& intervals):这是类 Solution 中的一个公共成员函数,接受一个二维整数数组 intervals,返回合并后的区间数组。
  2. 初始化和边界条件:

    • vector<vector<int>> result;:定义一个 result 向量,用于存放合并后的区间。
    • if (intervals.size() == 0) return result;:如果输入的区间集合为空,直接返回一个空的结果。
  3. 排序:

    • sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {...});:使用 lambda 表达式依据每个区间的起始值对区间进行升序排序,使得可以顺序检查重叠情况。
  4. 合并区间:

    • result.push_back(intervals[0]);:将第一个区间放入结果集,因为它是最小的。
    • 使用 for 循环从第二个区间开始遍历。检查当前区间的起始值是否小于或等于 result 最后一个区间的结束值。
    • 如果发现重叠,则通过 max 函数更新最后一个区间的结束值,覆盖重叠部分。
    • 如果没有重叠,则将当前区间直接加入到结果集。
  5. 返回结果:

    • 最后,函数返回合并后的区间集合 result

整体思路:

  • 首先对区间进行排序,确保可以顺序比较。
  • 将第一个区间作为初始值,然后遍历后面的区间,检查是否有重叠,若有则合并,若没有则直接添加到结果集中。
  • 最终返回所有合并后的不重叠区间。

738 递增数字

力扣题目链接

题目描述:

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。

给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

代码(自己写的,时间太长)

class Solution {
public:
    static bool cmp(vector<int> &a,vector<int> &b){
        return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
      for(int i=1;i<intervals.size();i++){
        if(intervals[i-1][1]>=intervals[i][0]){
            intervals[i-1][1]=max(intervals[i][1],intervals[i-1][1]);
            intervals.erase(intervals.begin()+i);
            i--;
        }
      }
      return intervals;
    }
};

直接按照规律来的贪心代码:

class Solution {  
public:  
    int monotoneIncreasingDigits(int N) {  
        // 将整数 N 转换为字符串,以便逐位处理  
        string strNum = to_string(N);  
        // flag用来标记赋值9从哪里开始  
        // 设置为这个默认值,是为了防止第二个for循环在flag没有被赋值的情况下执行  
        int flag = strNum.size();   

        // 从右向左遍历字符  
        for (int i = strNum.size() - 1; i > 0; i--) {  
            // 如果左侧的数字大于右侧的数字,说明不满足单调递增的条件  
            if (strNum[i - 1] > strNum[i]) {  
                flag = i; // 标记从哪个位置开始赋值9  
                strNum[i - 1]--; // 将左侧的数字减1  
            }  
        }  
        
        // 从标记的位置开始将之后的数字都设为9  
        for (int i = flag; i < strNum.size(); i++) {  
            strNum[i] = '9'; // 赋值为字符'9'  
        }  
        
        // 将处理后的字符串转换回整数并返回  
        return stoi(strNum);  
    }  
};  

代码解释:

  1. 类与函数定义:

    • class Solution:定义了一个名为 Solution 的类。
    • int monotoneIncreasingDigits(int N):这是类 Solution 中的一个公共成员函数,接受一个整数 N,返回小于或等于 N 的最大单调递增整数。
  2. 字符串转换:

    • string strNum = to_string(N);:将整数 N 转换为字符串形式,以方便逐位进行操作。
  3. 标记和初始化:

    • int flag = strNum.size();:初始化 flag 为字符串的大小,目的是当没有发现不满足条件的位置时,可以在后续操作中有效使用。
  4. 从右向左遍历:

    • 使用 for 循环从右到左遍历字符串中的数字。
    • if (strNum[i - 1] > strNum[i]):检查左侧数字是否大于右侧数字。如果是,说明不满足单调递增的条件。
    • flag = i;:若不满足条件,标记从当前索引 i 开始进行修改。
    • strNum[i - 1]--;:将左侧的数字减1,以尝试生成一个单调递增的数字。
  5. 赋值9:

    • 使用另一个 for 循环,从 flag 位置开始,将之后的所有数字都设置为 '9',以确保生成的数字是最大的单调递增数字。
  6. 返回结果:

    • return stoi(strNum);:将处理后的字符串转换回整数并返回。

整体思路:

  • 通过将数字转换为字符串逐位检查,确保每个数字是单调递增的。
  • 当发现不满足条件的位置时,通过减小前一个数字并将后面的数字补充为9来保证结果是最大可能的单调递增数字。
  • 最后将处理后的字符串转换回整数并返回。

标签:vector,合并,56,随想录,day31,intervals,result,区间,strNum
From: https://blog.csdn.net/2301_80639580/article/details/140872653

相关文章

  • 【代码随想录】图论复习(Python版)
    深度优先搜索1.搜索过程一个方向搜,不到黄河不回头,直到遇到绝境了,搜不下去了,再换方向(换方向的过程就涉及到了回溯)2.代码框架回溯法的代码框架:defbacktracking(参数):if终止条件:存放结果returnfor选择本层集合中的元素(树中节点孩子的数量......
  • 【代码随想录】数组篇
    一、二分查找给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。二分查找的前提有序数组,无重复元素二分法的写法1.左闭右闭,即[left,right]而(左<=右)如果nums[mid]>......
  • AGC056A 题解
    首先考虑\(n\equiv0\pmod3\)的情况。非常简单,然后考虑\(n\equiv1\pmod3\)的情况。只要把多出来的第一列第一行填满就行了。还要比原来情况多一个连通块。然后考虑\(n\equiv2\pmod3\)的情况。手玩一下,再往左上角添一点东西就行了。#include<bits/stdc++.h>us......
  • 「代码随想录算法训练营」第二十八天 | 动态规划 part1
    509.斐波那契数题目链接:https://leetcode.cn/problems/fibonacci-number/题目难度:简单文章讲解:https://programmercarl.com/0509.斐波那契数.html视频讲解:https://www.bilibili.com/video/BV1f5411K7mo题目状态:过!思路:当n=0时,返回0;当n=1时,返回1;当n>=2时,返回fib(......
  • 2560战法+选股指标+主图
    2560战法+选股指标+主图 作者: 深海游鱼  QQ:396068801 日期:2024年8月需要指标的朋友请加QQ交流。买点1:冲量,量价金叉买点2:做量,即日线回踩25日均线后反弹上穿25日均线,同时五日均量线<=60日均量线卖点3:二次金叉        ......
  • 代码随想录Day3
    203.移除链表元素给你一个链表的头节点head和一个整数val,请你删除链表中所有满足Node.val==val的节点,并返回新的头节点。示例1:输入:head=[1,2,6,3,4,5,6],val=6输出:[1,2,3,4,5]示例2:输入:head=[],val=1输出:[]示例3:输入:head=[7,7,7,7],val=7......
  • 【代码随想录训练营第42期 Day17打卡 二叉树Part5-LeetCode 654.最大二叉树 617.合并
    目录一、做题心得二、题目与题解题目一:654.最大二叉树题目链接题解:递归题目二:617.合并二叉树题目链接题解:递归(前序遍历)题目三:617.合并二叉树题目链接题解:BFS层序遍历 题目四:98.验证二叉搜索树题目链接题解:递归(中序遍历)三、小结一、做题心得今天是代码随想......
  • Luogu P5005 中国象棋 - 摆上马 / Luogu P8756 国际象棋 题解 [ 蓝 ] [ 状压 dp ] [
    国际象棋:模板棋盘状压。摆上马:需要点思维的棋盘状压,相比上一道题加了“蹩马脚”的设定。Easy_version:国际象棋概述一下此类棋盘问题的思路:用二进制数表示出棋盘上某一行的状态。用位运算预处理出合法的单行状态,以及需要用到的一些东西。用位运算判断前一行或者前几行能否......
  • 米尔发布RK3568工控板和工控机,更丰富的场景应用
    国产之星-瑞芯微RK3568一直备受关注,米尔电子推广的RK3568核心板采用创新LGA设计,核心板质量更可靠,成本更优。除米粉派RK3568(MYD-LR3568开发板)之外,米尔加推MYD-LR3568-GK工控板和MYD-LR3568-GK-B工控机,丰富更多的应用场景。MYD-LR3568-GK工控板基于MYC-LR3568工业级核心板设计,搭载4......
  • 代码随想录day17 || 654 最大二叉树,617 合并二叉树,700 二叉搜索树搜索,98 验证二叉搜索
    645最大二叉树funcconstructMaximumBinaryTree(nums[]int)*TreeNode{ //思路,算法思路基本等同于通过中序前序构造二叉树 //1,取最大值作为根节点 //2,切割数组 //3,递归左右子树 iflen(nums)==0{ returnnil } //切割数组取最大值 max,left,right:=......