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中文網其他相關文章！