《代码随想录》Day31打卡！

《代码随想录》贪心算法：合并区间

本题的完整题目如下所示：

本题的完整思路如下所示： 1.本题依然是先对数组的左边界进行排序。将数组的第一个元素赋值给current。 2.遍历数组，判断current中的右边界和当前元素的左边界是否有重叠，如果有，则说明是重叠区间，需要合并。如果没有则将第i个数组赋值给current，并将current添加到结果数组中。 3.合并区间：将current的右边界赋值为max(current的右边界和第i个元素的右边界)，注意是修改current数组的右边界，而不是原数组，此时也不需要将current添加到结果数组中。本题的完整代码如下所示： class Solution { public int merge(int intervals) { // 按区间的起始位置升序排序 Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    List<int[]> res = new ArrayList<>();
    int[] current = intervals[0];
    res.add(current);
    for(int i = 1; i < intervals.length; i++) {
        if(current[1] >= intervals[i][0]) {
            current[1] = Math.max(current[1], intervals[i][1]);
        }else{
            current = intervals[i];
            res.add(current);
        }
    }
    // 将结果转换为二维数组返回
    return res.toArray(new int[res.size()][]);
}

}

《代码随想录》贪心算法：单调递增的数字

本题的完整题目如下所示：

本题的完整思路如下： 1.首先本题是对数字的每一位都进行操作，所以先把数字转换为字符串类型进行操作，方便对每一位进行遍历。 2.本题的重点是从右向左对转换后的字符串进行遍历，判断其是否满足单调递增。只要左边的数字大于右边的数字，此时将左边的数字减去1，此时将该数字右边的所有数字都变为9，这样才能保证最后得到的数字是最大的满足条件的数字。 3.最后将字符串转换为整数返回即可。本题的完整代码如下所示：

//738.单调递增的数字
class Solution16 {
    public int monotoneIncreasingDigits(int n) {
        String str = String.valueOf(n); // 将整数转换为字符串
        StringBuilder sb = new StringBuilder(str);

        // 从右向左检查是否满足单调递增
        for (int i = sb.length() - 1; i > 0; i--) {
            if (sb.charAt(i) < sb.charAt(i - 1)) {
                // 当前位小于前一位，将前一位减 1，当前位以及右侧所有位设置为 '9'
                sb.setCharAt(i - 1, (char)(sb.charAt(i - 1) - 1));
                for (int j = i; j < sb.length(); j++) {
                    sb.setCharAt(j, '9');
                }
            }
        }

        // 将最终结果转为整数并返回
        return Integer.parseInt(sb.toString());
    }
}