代码随想录第36、37天| 435. 无重叠区间 763.划分字母区间 56. 合并区间

763.划分字母区间 

763. 划分字母区间 - 力扣（LeetCode）

代码随想录 (programmercarl.com)

贪心算法，寻找最远的出现位置！ LeetCode：763.划分字母区间_哔哩哔哩_bilibili

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

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

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

示例 1：

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

示例 2：

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

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

这个题第一想法就是双指针法，一个指针i指向区间开头的字母，另外一个指针j从区间最左边向右遍历，直到找到和第一个字母相同的字母，返回这个字母的下标，然后指针i向右移动一位，指针j从原地右移；如果没找到，就把左边的指针i向后移动一位，重复上述过程。指针i和指针j的位置就是需要切割的位置。

写完发现好乱。。。。还是看卡哥题解吧。。

🤓看了卡哥题解后发现我有2点没弄清楚所以导致很乱：

1、区间与区间之间一定是不重合的，所以下一个区间起始的位置一定在上一个区间结束位置的后面

2、我最大的问题在于用双指针法很糊。不建议用双指针法，直接标出每个字母的下标，某字母下标最大的位置就是这个字母最远的位置，必须包括在同一个区间内，如图：

卡哥还有一点很巧妙的就是将字母转换成数字做减法，整体代码如下：

class Solution {public List<Integer> partitionLabels(String S) {// 创建一个列表来存储分区的长度List<Integer> list = new LinkedList<>();// 初始化一个数组来存储每个字符在字母表中的最后出现位置的索引int[] edge = new int[26];// 将输入字符串转换为字符数组char[] chars = S.toCharArray();// 遍历字符串的字符，存储每个字符的最后出现位置的索引for (int i = 0; i < chars.length; i++) {edge[chars[i] - 'a'] = i;}// 初始化变量来跟踪当前索引和当前分区的最后一个索引int idx = 0;int last = -1;// 再次遍历字符串的字符for (int i = 0; i < chars.length; i++) {// 更新当前分区的最后一个索引idx = Math.max(idx, edge[chars[i] - 'a']);// 如果当前索引等于当前分区的最后一个索引，// 这意味着我们已经到达当前分区的末尾if (i == idx) {// 将当前分区的长度添加到列表中list.add(i - last);// 更新当前分区的最后一个索引last = i;}}// 返回包含分区长度的列表return list;}
}

56. 合并区间 - 力扣（LeetCode）

代码随想录 (programmercarl.com)

贪心算法，合并区间有细节！LeetCode：56.合并区间_哔哩哔哩_bilibili

以数组 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

先按左边界的值排序：

发现重合后其实只需要更新右边界：

// 更新最右边界为当前区间右边界和原最右边界的较大值rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);

 738.单调递增的数字

738. 单调递增的数字 - 力扣（LeetCode）

代码随想录 (programmercarl.com)

贪心算法，思路不难想，但代码不好写！LeetCode:738.单调自增的数字_哔哩哔哩_bilibili

注意点：

1、这个题要注意从后往前遍历。

2、传进来的数值是int类型，为了方便各个位上的数值比较大小，将int类型转为字符串。

3、start记录位置，start后面的都赋值为9才能得到最大值

4、start初始为s的长度而不是0，为的就是避免s=1234这种情况出现时，再走for (int i = start; i < s.length(); i++) {
            chars[i] = '9'; 的逻辑将s变成1999.

class Solution {public int monotoneIncreasingDigits(int n) {// 将输入的整数转换为字符串String s = String.valueOf(n);// 将字符串转换为字符数组char[] chars = s.toCharArray();// 初始化变量 start 为字符串的长度int start = s.length();// 从倒数第二位开始向前遍历字符数组for (int i = s.length() - 2; i >= 0; i--) {// 如果当前字符大于后面一位字符if (chars[i] > chars[i + 1]) {// 将当前字符减去1，并更新 start 的值为当前位置的后一位chars[i]--;start = i + 1;}}// 将 start 位置后的所有字符设为 '9'for (int i = start; i < s.length(); i++) {chars[i] = '9';}// 将字符数组转换为整数并返回return Integer.parseInt(String.valueOf(chars));}
}