Algoritma LeetCode DayGreedy Bahagian 4

452. Bilangan Minimum Anak Panah untuk Meletup Belon

Terdapat beberapa belon sfera yang dilekatkan pada dinding rata yang mewakili satah XY. Belon diwakili sebagai titik tatasusunan integer 2D di mana titik[i] = [xstart, xend] menandakan belon yang diameter mendatarnya terbentang antara xstart dan xend. Anda tidak tahu koordinat y yang tepat bagi belon itu.

Anak panah boleh dipanah terus secara menegak (dalam arah y positif) dari titik berbeza di sepanjang paksi-x. Belon dengan xstart dan xend dipecahkan oleh panahan anak panah ke arah x jika xstart <= x <= xend. Tiada had bilangan anak panah yang boleh ditembak. Anak panah yang ditembak terus bergerak naik tak terhingga, memecahkan sebarang belon di laluannya.

Memandangkan mata tatasusunan, kembalikan bilangan anak panah minimum yang mesti dipanah untuk memecahkan semua belon.

Contoh 1:

Input: mata = [[10,16],[2,8],[1,6],[7,12]]
Keluaran: 2
Penjelasan: Belon boleh pecah dengan 2 anak panah:

• Tembak anak panah pada x = 6, pecahkan belon [2,8] dan [1,6].
• Tembak anak panah pada x = 11, pecahkan belon [10,16] dan [7,12]. Contoh 2:

Input: mata = [[1,2],[3,4],[5,6],[7,8]]
Keluaran: 4
Penjelasan: Satu anak panah perlu ditembak untuk setiap belon dengan jumlah 4 anak panah.
Contoh 3:

Input: mata = [[1,2],[2,3],[3,4],[4,5]]
Keluaran: 2
Penjelasan: Belon boleh pecah dengan 2 anak panah:

• Tembak anak panah pada x = 2, pecahkan belon [1,2] dan [2,3].
• Tembak anak panah pada x = 4, pecahkan belon [3,4] dan [4,5].

Kekangan:

1 <= mata.panjang <= 105
mata[i].panjang == 2
-2^31 <= xmula < xend <= 2^31 - 1
Halaman Asal

    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. Selang Tidak Bertindih

Memandangkan tatasusunan selang selang di mana selang[i] = [starti, endi], kembalikan bilangan minimum selang yang perlu anda alih keluar untuk menjadikan selang selebihnya tidak bertindih.

Contoh 1:

Input: selang = [[1,2],[2,3],[3,4],[1,3]]
Keluaran: 1
Penjelasan: [1,3] boleh dialih keluar dan selang selebihnya tidak bertindih.
Contoh 2:

Input: selang = [[1,2],[1,2],[1,2]]
Keluaran: 2
Penjelasan: Anda perlu mengalih keluar dua [1,2] untuk menjadikan selang selebihnya tidak bertindih.
Contoh 3:

Input: selang = [[1,2],[2,3]]
Output: 0
Penjelasan: Anda tidak perlu mengalih keluar mana-mana selang kerana ia sudah tidak bertindih.

Kekangan:

1 <= selang.panjang <= 10^5
selang[i].panjang == 2
-5 * 10^4 <= mula < endi <= 5 * 10^4
Halaman Asal

Kod yang salah

    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;
    }

Betulkan

    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. Label Pembahagian

Anda diberi rentetan s. Kami ingin membahagikan rentetan kepada seberapa banyak bahagian yang mungkin supaya setiap huruf muncul dalam paling banyak satu bahagian.

Perhatikan bahawa partition dilakukan supaya selepas menggabungkan semua bahagian mengikut tertib, rentetan yang terhasil hendaklah s.

Kembalikan senarai integer yang mewakili saiz bahagian ini.

Contoh 1:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Penjelasan:
Pembahagiannya ialah "ababcbaca", "defegde", "hijhklij".
Ini ialah partition supaya setiap huruf muncul dalam paling banyak satu bahagian.
Pembahagian seperti "ababcbacadefegde", "hijhklij" adalah tidak betul, kerana ia membahagikan s kepada bahagian yang lebih sedikit.
Contoh 2:

Input: s = "eccbbbbdec"
Output: [10]

Kekangan:

1 <= s.panjang <= 500
s terdiri daripada huruf kecil Inggeris.
Halaman Asal

    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;
    }

Oleh kerana tidak penting untuk menilai sama ada elemen telah berada dalam set, kami hanya fokus pada sama ada penghujungnya tercapai atau tidak, dan jika elemen yang sama berlaku, penghujungnya tidak akan berubah dan jika elemen yang berbeza bergabung, nampaknya akhir mungkin berubah tetapi kesemuanya tidak akan memberi kesan kepada penilaian if supaya kami boleh mengeluarkannya.

Atas ialah kandungan terperinci Algoritma LeetCode DayGreedy Bahagian 4. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!