LeetCode Day貪欲なアルゴリズム パート 5

56. マージ間隔

interval[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 中国語 Web サイトの他の関連記事を参照してください。