当前位置: 首页 > article >正文

Day31补代码随想录20250110贪心算法5 56.合并区间|738.单调递增的数字|968.监控二叉树(可跳过)

【先跳过监控二叉树】

56.合并区间

题目

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

示例 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] 可被视为重叠区间。

提示:

  • 1 <= intervals.length <= 10<sup>4</sup>
  • intervals[i].length == 2
  • 0 <= start<sub>i</sub> <= end<sub>i</sub> <= 10<sup>4</sup>

思路

  • 这个题目是合并所有区间
  • Carl思路
    • 升序排序左边界
    • 初始化
    • for
      • if重叠
        • 左边界不变
        • 更新最远右边界
        • 移除旧区间,为了将重叠的区间合成一个新区间
        • 添加新的区间
      • else 直接加区间
  • 代码
    class Solution {
        public int[][] merge(int[][] intervals) {
            List<int[]> res=new LinkedList<>();
            Arrays.sort(intervals,(o1,o2)->Integer.compare(o1[0],o2[0]));//排序左边界,升序
            res.add(intervals[0]);//初始化
            for(int i=1;i<intervals.length;i++){
                if(intervals[i][0]<=res.getLast()[1]){
                    int start=res.getLast()[0];//左边界不变
                    int end=Math.max(intervals[i][1],res.getLast()[1]);
                    res.removeLast();//将两个重叠区间合并成一个新的,首先要移除旧区间
                    res.add(new int[]{start,end});//添加新的区间
                }
                else{
                    res.add(intervals[i]);//直接加区间
                }
            }
            return res.toArray(new int[res.size()][]); //大小为3的二维数组 
        }
    }
    

总结

  • 为了避免冲突,新建一个数组负责合并和增加数组
  • LinkedList转换为int二维数组,return res.toArray(new int[res.size()][]); //大小为3的二维数组

738.单调递增的数字

题目

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

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

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

提示:

  • 0 <= n <= 10<sup>9</sup>

思路

  • 我的思路
    • 当数组中的最后一个元素<=前一个元素时,将前一个元素赋值为数组中的最后一个元素。
  • 思路
    • 前一位-1,后一位是范围中最大的值
    • 从后往前遍历,不能从前往后遍历
  • 伪代码
    • 转换整数为字符,用于修改字符
    • 遍历for循环,标记需要变换为9的起点
    • 变换为9
    • 转换字符为整数
  • 代码
    • class Solution {
          public int monotoneIncreasingDigits(int n) {
              String s=String.valueOf(n);//数字变字符串
              char[] chars=s.toCharArray();//字符串变字符数组,为了修改字符
              int flag=s.length();
              for(int i=s.length()-2;i>=0;i--){//i-1到0
                  if(chars[i]>chars[i+1]){
                      chars[i]--;
                      flag=i+1;//标记变换为9的起点
                  }
              }
              for(int i=flag;i<s.length();i++){
                  chars[i]='9';
              }
              return Integer.parseInt(String.valueOf(chars));   
              //String.valueOf(chars)字符→字符串;Integer.parseInt()字符串→整数
          }
      }
      

总结

  • flag为什么要进行初始赋值flag=0?因为输入可能本身已经满足条件了,不进入flag循环中。
  • 为什么遇到i-1的值>i的值,要用flag记录下来,而不是直接赋值?
    • 反例:1000,走到前面两位10时,如果直接赋值,结果为0900,但是正确输出时999

http://www.kler.cn/a/503213.html

相关文章:

  • sqlilabs--小实验
  • RK3568平台开发系列讲解(调试篇)网卡队列均衡负载
  • 二次封装axios解决异步通信痛点
  • 在VS2022中配置DirectX12环境,并显示显示一个窗口
  • 蓝桥杯嵌入式备赛(四)—— 中断 + UART
  • Spring Security 学习大纲
  • LoRaWAN节点学习笔记
  • ASP.NET Core - 日志记录系统(一)
  • leetcode 面试经典 150 题:快乐数
  • 云服务信息安全管理体系认证,守护云端安全
  • npm、yarn、pnpm包安装器差异性对比
  • 深度学习中的卷积神经网络(CNN):原理与应用详解
  • 如何使用虚拟机连接到SSH
  • 【0x005B】HCI_Write_Default_Erroneous_Data_Reporting命令详解
  • 【Pandas】pandas Series radd
  • 基于Springboot + vue实现的文档管理系统
  • flutter 装饰类【BoxDecoration】
  • 上传自己的镜像到docker hub详细教程
  • 浅谈云计算06 | 云管理系统架构
  • 论文阅读:《Whole-animal connectomes of both Caenorhabditis elegans sexes》
  • 7.STM32F407ZGT6-RTC
  • 施耐德M241与MR20-MT-1616的组态过程
  • python-leetcode-矩阵置零
  • 当自动包布机遇上Profinet转ModbusTCP网关,“妙啊”,工业智能“前景无限
  • SpiderFlow平台v0.5.0之引入selenium插件
  • linux 文件权限设置详解