Day31补代码随想录20250110贪心算法5 56.归并区间|738.单调递增的数字|968. ...

【先跳过监控二叉树】
56.归并区间

题目

以数组 intervals 表现多少个区间的集合，其中单个区间为 intervals = [start_i, end_i] 。请你归并全部重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的全部区间 。
示例 1：

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

复制代码

示例 2：

1. <strong>输入：</strong>intervals = [[1,4],[4,5]]
2. <strong>输出：</strong>[[1,5]]
3. <strong>解释：</strong>区间 [1,4] 和 [4,5] 可被视为重叠区间。

复制代码

提示：

• 1 <= intervals.length <= 10⁴
  
• intervals.length == 2
  
• 0 <= start_i <= end_i <= 10⁴
  

思路

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

  复制代码

总结

• 为了制止冲突，新建一个数组负责归并和增长数组
  
• LinkedList转换为int二维数组，return res.toArray(new int[res.size()][]); //大小为3的二维数组
  

738.单调递增的数字

题目

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:

1. <strong>输入:</strong> n = 10
2. <strong>输出:</strong> 9

复制代码

示例 2:

1. <strong>输入:</strong> n = 1234
2. <strong>输出:</strong> 1234

复制代码

示例 3:

1. <strong>输入:</strong> n = 332
2. <strong>输出:</strong> 299

复制代码

提示:

• 0 <= n <= 10⁹
  

思路

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

    复制代码
  
  

总结

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。