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

452. 風船を割るための矢の最小数

XY 平面を表すいくつかの球形の風船が平らな壁にテープで貼り付けられています。バルーンは 2D 整数配列のポイントとして表されます。ここで、points[i] = [xstart, xend] は、水平直径が xstart と xend の間に伸びるバルーンを示します。バルーンの正確な y 座標はわかりません。

矢印は、X 軸に沿ったさまざまな点から垂直方向 (正の Y 方向) に直接発射できます。 xstart <= x <= xend の場合、xstart と xend を持つ風船は x に放たれた矢によって破裂します。発射できる矢の数に制限はありません。放たれた矢は無限に上昇し続け、その途中にある風船を破裂させます。

配列のポイントを指定して、すべての風船を割るために射らなければならない矢の最小数を返します。

例 1:

入力: ポイント = [[10,16],[2,8],[1,6],[7,12]]
出力: 2
説明: 風船は 2 つの矢印で割ることができます:

• x = 6 に矢を放ち、風船 [2,8] と [1,6] を割ります。
• x = 11 に矢を放ち、風船 [10,16] と [7,12] を割ります。 例 2:

入力: ポイント = [[1,2],[3,4],[5,6],[7,8]]
出力: 4
説明: 風船ごとに 1 本の矢を放つ必要があり、合計 4 本の矢を放つ必要があります。
例 3:

入力: ポイント = [[1,2],[2,3],[3,4],[4,5]]
出力: 2
説明: 風船は 2 つの矢印で割ることができます:

• x = 2 に矢を放ち、風船 [1,2] と [2,3] を割ります。
• x = 4 に矢を放ち、風船 [3,4] と [4,5] を割ります。

制約:

1 <= ポイントの長さ <= 105
ポイント[i].length == 2
-2^31 <= xstart <; xend <= 2^31 - 1
オリジナルページ

    public int findMinArrowShots(int[][] points) {
        if(points.length == 0){
            return 0;
        }

        Arrays.sort(points, (a,b) ->{
            if(a[0] == b[0]){
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });

        int arrow = 1;
        int start = points[0][0];
        int end = points[0][1];

        for(int i=0; i<points.length; i++){

            if((points[i][0] >= start && points[i][0]<= end) ||
            (end >=points[i][0] && end <= points[i][1])){

//Narrow the arrow point down 

                if(points[i][0] > start && points[i][0] <= end){
                    start = points[i][0];
                }
                if(points[i][1]>start && points[i][1] < end){
                    end = points[i][1];
                }
                continue;
            }else{

// current arrow point is not satisfied with balloons 

                start = points[i][0];
                end = points[i][1];
                arrow ++;   
            }
        }
        return arrow; 
    }

435. 重複しない間隔

interval[i] = [starti, endi] の間隔の配列が与えられた場合、残りの間隔が重複しないようにするために削除する必要がある間隔の最小数を返します。

例 1:

入力: 間隔 = [[1,2],[2,3],[3,4],[1,3]]
出力: 1
説明: [1,3] は削除でき、残りの間隔は重複しません。
例 2:

入力: 間隔 = [[1,2],[1,2],[1,2]]
出力: 2
説明: 残りの間隔が重複しないようにするには、2 つの [1,2] を削除する必要があります。
例 3:

入力: 間隔 = [[1,2],[2,3]]
出力: 0
説明: 間隔はすでに重複していないため、削除する必要はありません。

制約:

1 <= 間隔.長さ <= 10^5
間隔[i].length == 2
-5 * 10^4 <= starti <;エンディ <= 5 * 10^4
オリジナルページ

間違ったコード

    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length == 0){
            return 0;
        }

        Arrays.sort(intervals, (a,b) ->{
            if(a[0] == b[0]){
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });

        Arrays.stream(intervals)
                .map(Arrays::toString)
                .forEach(System.out::println);

        int count = 0;

        // List<int[]> list = new LinkedList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];

        for(int i=1; i<intervals.length; i++){
            //if the left edge is not included in the previous interval the right will definitely not be in it.
            if(intervals[i][0] >=start && intervals[i][0] <end){
                count++;
                continue;
            }
            start = intervals[i][0];
            end = intervals[i][1];
            // list.add(intervals[i]);
        }
        return count;
    }

修正してください

    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length == 0){
            return 0;
        }

        Arrays.sort(intervals, (a,b) ->{
            return a[0] - b[0];
        });

        int count = 0;

        int start = intervals[0][0];
        int end = intervals[0][1];

        for(int i=1; i<intervals.length; i++){
            if(intervals[i][0] < intervals[i-1][1]){
                count++;
                // here we need to find the maximum overlap, the means whether the next element  overlap to above groups of overlaps 
                // if only find overlap from the previous interval, it may cause miss calculation over-add 1 count
                intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);  
            }
        }
        return count;
    }

763. パーティションラベル

文字列 s が与えられます。各文字が多くても 1 つの部分に表示されるように、文字列をできるだけ多くの部分に分割したいと考えています。

すべての部分を順番に連結した後、結果の文字列が s になるように分割が行われることに注意してください。

これらのパーツのサイズを表す整数のリストを返します。

例 1:

入力: s = "ababcbacadefegdehijhklij"
出力: [9,7,8]
説明:
パーティションは「ababcbaca」、「defegde」、「hijhklij」です。
これは、各文字が最大 1 つの部分に表示されるようにするためのパーティションです。
「ababcbacadefegde」、「hijhklij」のようなパーティションは、 をより少ない部分に分割するため、正しくありません。
例 2:

入力: s = "eccbbbbdec"
出力: [10]

制約:

1 <= s.length <= 500
s は英小文字で構成されます。
オリジナルページ

    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        Set<Character> set = new HashSet<>();

        if(s.length() == 0){
            return list;
        }

        int start = 0;
        int end = 0;
        for(int i=0; i<s.length(); i++){
            Character target = s.charAt(i);

            if(!set.contains(target)){
                set.add(target);
                int j = s.length()-1;
                for(;j>i;j--){
                    if(s.charAt(j) == target){
                        break;
                    }
                }
                end = Math.max(end, j);
            }
            if(i == end){
                list.add(end-start+1);
                start = i+1;
                set.clear();
            } 
        }
        return list;
    }






</p>
<pre class="brush:php;toolbar:false">    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        Set<Character> set = new HashSet<>();

        int[] pos = new int[27];

        for(int i=s.length()-1; i>0;i--){
            if(pos[s.charAt(i)-'a'] == 0){
                pos[s.charAt(i)-'a'] = i;
            }
        }

        if(s.length() == 0){
            return list;
        }

        int start = 0;
        int end = 0;
        for(int i=0; i<s.length(); i++){
            Character target = s.charAt(i);

            if(!set.contains(target)){
                set.add(target);

                end = Math.max(end, pos[target-'a']);
            }
            if(i == end){
                list.add(end-start+1);
                start = i+1;
                set.clear();
            } 
        }
        return list;
    }

    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();

        int[] pos = new int[27];

        for(int i=s.length()-1; i>0;i--){
            if(pos[s.charAt(i)-'a'] == 0){
                pos[s.charAt(i)-'a'] = i;
            }
        }

        if(s.length() == 0){
            return list;
        }

        int start = 0;
        int end = 0;
        for(int i=0; i<s.length(); i++){
            Character target = s.charAt(i);

            end = Math.max(end, pos[target-'a']);

            if(i == end){
                list.add(end-start+1);
                start = i+1;
            } 
        }
        return list;
    }

要素がセットに含まれているかどうかを評価するのに重要ではないため、終わりに到達したかどうかにのみ焦点を当てます。同じ要素が発生した場合、終わりは変化せず、異なる要素が結合した場合、 end は変更される可能性があるように見えますが、それらはすべて if 評価に影響を与えないため、削除しても問題ありません。

以上がLeetCode Day貪欲なアルゴリズム パート 4の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。