LeetCode Day 贪心算法第 5 部分

56. 合并区间

给定一个间隔数组，其中间隔[i] = [starti, endi]，合并所有重叠间隔，并返回覆盖输入中所有间隔的非重叠间隔数组。

示例1：

输入：间隔 = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：由于区间 [1,3] 和 [2,6] 重叠，因此将它们合并为 [1,6]。
示例2：

输入：间隔 = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 被视为重叠。

限制：

1 间隔[i].length == 2
0 原始页面

    public int[][] merge(int[][] intervals) {
        if(intervals.length <= 1){
            return intervals;
        }
        Arrays.sort(intervals, (a,b)->{
            return Integer.compare(a[0], b[0]);
        });

        List<int[]> list = new ArrayList();
        for(int i=1; i<intervals.length; i++){
            if(intervals[i-1][1] >= intervals[i][0]){
                intervals[i][0] = intervals[i-1][0];
                intervals[i][1] = Math.max(intervals[i-1][1], intervals[i][1]);

            } else{
                list.add(intervals[i-1]);
            }
        }
        list.add(intervals[intervals.length-1]);
        return list.toArray(new int[list.size()][]);
    }

738. 单调递增数字

整数具有单调递增的数字当且仅当每对相邻数字 x 和 y 满足 x

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

示例1：

输入：n = 10
输出：9
示例2：

输入：n = 1234
输出：1234
示例 3：

输入：n = 332
输出：299

限制：

0

    public int monotoneIncreasingDigits(int n) {
        if(n<10){
            return n;
        }
        String str = Integer.toString(n);
        char[] arr = new char[str.length()];
        arr[0] = str.charAt(0);

        int pos = -1;
        for(int i=1; i<str.length(); i++){
            char num = str.charAt(i);
            if(num < arr[i-1]){
                int j;
                if(pos == -1){
                    j = 0;
                }else{
                    j = pos;
                }
                for(;j<arr.length; j++){
                    if(j==0||j==pos){
                        arr[j] = (char) (arr[j]-1);
                    }else{
                        arr[j] = '9';
                    }
                }
                break;
            }
            else if(num > arr[i-1]){
                pos = i;
            }
            arr[i] = str.charAt(i);
        }
        if(arr[0] <=0){
            // cost space by using String
            str = new String(arr, 1,arr.length);
        }else{
            str = new String(arr);
        }
        return Integer.valueOf(str);
    }

以上是LeetCode Day 贪心算法第 5 部分的详细内容。更多信息请关注PHP中文网其他相关文章！