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

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来保证结果是最大可能的单调递增数字。
• 最后将处理后的字符串转换回整数并返回。