练习题（2024/4/）

1无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

提示:

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• -5 * 104 <= starti < endi <= 5 * 104

思路：

1. 按照区间的结束位置进行排序：

   • 首先，对给定的区间集合按照结束位置进行排序。这样做的目的是，我们希望尽量保留结束位置较早的区间，这样可以为后面的区间留下更多的空间。

2. 遍历排序后的区间集合：

   • 从第二个区间开始遍历排序后的区间集合。
   • 初始化一个计数器，用于记录需要移除的区间数量，初始值为0。

3. 检查是否存在重叠：

   • 对于当前遍历到的区间，与前一个区间比较。
   • 如果当前区间的起始位置小于前一个区间的结束位置，说明存在重叠。
   • 在这种情况下，将计数器加1，并且选择保留结束位置较早的区间（因为它可以为后面的区间留下更多的空间）。

   • 当确定区间 1 和 区间2 重叠后，如何确定是否与 区间3 也重贴呢？

     就是取 区间1 和 区间2 右边界的最小值，因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分，如果这个最小值也触达到区间3，那么说明 区间 1，2，3都是重合的。

4. 返回移除的区间数量：

   • 最后返回计数器的值，即为需要移除的区间数量。

代码：

class Solution {
public:
    // 自定义比较函数，按照区间起始位置从小到大排序
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    // 求解无重叠区间的最大数量
    int eraseOverlapIntervals(vectorint>>& intervals) {
        // 若区间数量为0，返回0
        if (intervals.size() == 0) return 0;
        // 按照区间起始位置排序
        sort(intervals.begin(), intervals.end(), cmp);
        int count = 0; // 记录重叠区间数量
        // 遍历区间数组
        for (int i = 1; i < intervals.size(); i++) {
            // 若当前区间起始位置小于前一个区间的结束位置，说明存在重叠
            if (intervals[i][0] < intervals[i - 1][1]) {
                count++; // 计数加1
                // 更新当前区间的结束位置为前一个区间结束位置与当前区间结束位置的最小值
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);
            }
        }
        return count; // 返回重叠区间数量
    }
};

2划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 

示例 2：

输入：s = "eccbbbbdec"
输出：[10]

提示：

• 1 <= s.length <= 500
• s 仅由小写英文字母组成

思路：

在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。

可以分为如下两步：

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

具体过程：

• 创建一个大小为27的数组 hash，用于记录每个字母在字符串中最后出现的位置。
• 第一个 for 循环遍历字符串 S，记录每个字符的最后出现位置。
• 创建一个存储结果的向量 result。
• 定义区间的左边界 left 和右边界 right，初始都为0。
• 第二个 for 循环再次遍历字符串 S。
• right = max(right, hash[S[i] - 'a']) 找到字符出现的最远边界。
• 如果当前遍历的位置 i 与右边界相等，说明当前位置是一个片段的结束位置，记录当前片段的长度。
• 更新下一个片段的左边界为 i + 1。
• 返回结果。

代码：

class Solution {
public:
    vector<int> partitionLabels(string S) {
        int hash[27] = {0}; // 创建一个大小为27的数组hash，用于记录每个字母在字符串中最后出现的位置
        for (int i = 0; i < S.size(); i++) { // 遍历字符串S
            hash[S[i] - 'a'] = i; // 记录字符 S[i] 出现的最后位置
        }
        vector<int> result; // 创建一个存储结果的向量
        int left = 0; // 定义区间的左边界
        int right = 0; // 定义区间的右边界
        for (int i = 0; i < S.size(); i++) { // 再次遍历字符串S
            right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界
            if (i == right) { // 如果当前遍历的位置i与右边界相等，说明当前位置是一个片段的结束位置
                result.push_back(right - left + 1); // 记录当前片段的长度
                left = i + 1; // 更新下一个片段的左边界
            }
        }
        return result; // 返回结果
    }
};

3 合并区间

以数组 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] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

思路：

1. 排序： 首先将输入的区间集合按照区间的左边界进行升序排序。这样排序后，相邻的区间如果有重叠，它们一定会相邻。

2. 合并重叠区间： 从排好序的区间集合中，逐个考察每个区间。如果当前区间与结果集合中最后一个区间有重叠（即当前区间的左边界小于等于结果集合中最后一个区间的右边界），则将当前区间合并到结果集合中最后一个区间中，更新最后一个区间的右边界为两者的最大值；如果当前区间与结果集合中最后一个区间没有重叠，则将当前区间直接加入结果集合中。

3. 返回结果： 最后返回合并后的结果集合

代码：

class Solution {
public:
    // 定义一个静态函数作为比较函数，用于排序
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0]; // 按照区间的左边界进行升序排序
    }
    
    vectorint>> merge(vectorint>>& intervals) {
        vectorint>> result;
        if (intervals.empty()) return result; // 如果区间集合为空直接返回空结果
        // 使用cmp函数对区间进行排序
        sort(intervals.begin(), intervals.end(), cmp);
 
        // 第一个区间直接放入结果集合中
        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;
    }
};

4单调递增的数字

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

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

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

思路：

1. 将数字转换为字符串： 首先将输入的数字 N 转换为字符串，以便进行逐位操作。

2. 从右向左遍历找到第一个不满足单调递增的位置： 从数字的最右侧开始，逐位比较当前位与前一位的大小。如果发现当前位比前一位小，则将前一位减1，并将标记 flag 设置为当前位的位置。

3. 将 flag 位置后的所有数字都变为9： 从标记位置 flag 开始，将该位置及其后面的所有数字都变为9，以确保最终结果是最大的且满足单调递增。

4. 将字符串转换回数字并返回： 最后将修改后的字符串转换为数字，并返回结果。

举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。

那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299

代码：

class Solution {
public:
    int monotoneIncreasingDigits(int 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;
                strNum[i - 1]--; // 将当前位减1
            }
        }
        for (int i = flag; i < strNum.size(); i++) {
            strNum[i] = '9'; // 从flag位置开始，将后面所有位都变为9
        }
        return stoi(strNum);
    }
};