Algoritma LeetCode DayGreedy Bahagian 1

455. Berikan Kuki

Anggap anda seorang ibu bapa yang hebat dan ingin memberi anak-anak anda beberapa kuki. Tetapi, anda harus memberi setiap kanak-kanak paling banyak satu kuki.

Setiap kanak-kanak i mempunyai faktor ketamakan g[i], iaitu saiz minimum kuki yang kanak-kanak akan berpuas hati dengannya; dan setiap kuki j mempunyai saiz s[j]. Jika s[j] >= g[i], kita boleh menetapkan kuki j kepada anak i, dan anak i akan berpuas hati. Matlamat anda adalah untuk memaksimumkan bilangan anak kandungan anda dan mengeluarkan bilangan maksimum.

Contoh 1:

Input: g = [1,2,3], s = [1,1]
Keluaran: 1
Penjelasan: Anda mempunyai 3 anak dan 2 kuki. Faktor tamak 3 anak ialah 1, 2, 3.
Dan walaupun anda mempunyai 2 kuki, memandangkan saiz kedua-duanya adalah 1, anda hanya boleh menjadikan kanak-kanak yang faktor tamaknya ialah 1 kandungan.
Anda perlu mengeluarkan 1.
Contoh 2:

Input: g = [1,2], s = [1,2,3]
Keluaran: 2
Penjelasan: Anda mempunyai 2 anak dan 3 kuki. Faktor tamak 2 anak ialah 1, 2.
Anda mempunyai 3 biskut dan saiznya cukup besar untuk memuaskan hati semua kanak-kanak,
Anda perlu mengeluarkan 2.

Kekangan:

1 <= g.panjang <= 3 * 104
0 <= s.panjang <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

    public int findContentChildren(int[] g, int[] s) {
        // avoid null pointer
        if(g.length == 0 || s.length ==0){
            return 0;
        }
        // 2 * nlogn
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0;
        int j = 0;
        int count = 0;
        while(i < g.length && j < s.length){
            if(g[i] <= s[j]){
                i++;
                j++;
                count++;
            } else{
                j++;
            }
        }
        return count;   
    }

masa : n`log masuk

Versi lain untuk gelung
`
public int findContentChildren(int[] g, int[] s) {
// elakkan penunjuk nol
if(g.length == 0 || s.length ==0){
pulangkan 0;
}
// 2 * nlogn
Arrays.sort(g);
Arrays.sort(s);

    int j = 0;
    int count = 0;
    for(int i=0; i<s.length && j<g.length; i++){
        if(s[i] >= g[j]){
            j++;
            count++;
        }
    }
    return count;   
}


</p>
<p>`</p>

<h2>
  
  
  376. Goyangkan Susulan
</h2>

<p>Jujukan goyang ialah jujukan di mana perbezaan antara nombor berturut-turut berselang-seli antara positif dan negatif. Perbezaan pertama (jika ada) mungkin sama ada positif atau negatif. Jujukan dengan satu elemen dan jujukan dengan dua unsur tidak sama adalah jujukan goyang secara remeh.</p>

<p>Contohnya, [1, 7, 4, 9, 2, 5] ialah jujukan goyang kerana perbezaan (6, -3, 5, -7, 3) silih berganti antara positif dan negatif.<br>
Sebaliknya, [1, 4, 7, 2, 5] dan [1, 7, 4, 5, 5] bukan jujukan goyang. Yang pertama bukan kerana dua perbezaan pertamanya adalah positif, dan yang kedua bukan kerana perbezaan terakhirnya ialah sifar.<br>
Susunan diperoleh dengan memadamkan beberapa unsur (mungkin sifar) daripada jujukan asal, meninggalkan unsur yang selebihnya dalam susunan asalnya.</p>

<p>Diberi nombor tatasusunan integer, kembalikan panjang urutan nombor goyang terpanjang.</p>

<p>Contoh 1:</p>

<p>Input: nombor = [1,7,4,9,2,5]<br>
Keluaran: 6<br>
Penjelasan: Keseluruhan jujukan ialah jujukan goyang dengan perbezaan (6, -3, 5, -7, 3).<br>
Contoh 2:</p>

<p>Input: nombor = [1,17,5,10,13,15,10,5,16,8]<br>
Keluaran: 7<br>
Penjelasan: Terdapat beberapa urutan yang mencapai panjang ini.<br>
Satu ialah [1, 17, 10, 13, 10, 16, 8] dengan perbezaan (16, -7, 3, -3, 6, -8).<br>
Contoh 3:</p>

<p>Input: nombor = [1,2,3,4,5,6,7,8,9]<br>
Keluaran: 2</p>

<p>Kekangan:</p>

<p>1 <= nums.length <= 1000<br>
0 <= angka[i] <= 1000</p>

<p>Susulan: Bolehkah anda menyelesaikan masalah ini dalam masa O(n)?</p>

<p>`<br>
    public int wiggleMaxLength(int[] nums) {<br>
        if(nums.length == 0){<br>
            pulangkan 0;<br>
        }<br>
        int count = 1;<br>
        int preFlag = 0;<br>
        int pra = angka[0];</p>

<pre class="brush:php;toolbar:false">    for(int i=1; i<nums.length; i++){
        if(nums[i]-nums[i-1] != 0){
            int flag = (nums[i]-nums[i-1])/Math.abs(nums[i]-nums[i-1]);

            if(flag == -preFlag || preFlag == 0){
                preFlag = flag;
                count++;
            }
        }
    }
    return count;
}

`

53. Subarray Maksimum

Memandangkan nombor tatasusunan integer, cari
subarray
dengan jumlah terbesar, dan pulangkan jumlahnya.

Contoh 1:

Input: nombor = [-2,1,-3,4,-1,2,1,-5,4]
Keluaran: 6
Penjelasan: Subarray [4,-1,2,1] mempunyai jumlah terbesar 6.
Contoh 2:

Input: nums = [1]
Keluaran: 1
Penjelasan: Subarray [1] mempunyai jumlah terbesar 1.
Contoh 3:

Input: nombor = [5,4,-1,7,8]
Keluaran: 23
Penjelasan: Subarray [5,4,-1,7,8] mempunyai jumlah terbesar 23.

Kekangan:

1 <= nums.length <= 105
-104 <= angka[i] <= 104

Susulan: Jika anda telah mengetahui penyelesaian O(n), cuba kodkan penyelesaian lain menggunakan pendekatan bahagi dan takluk, yang lebih halus.

`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
pulangkan 0;
}
int max = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
untuk(int i=0; i if(bilangan[i] > 0){
jika(jumlah < 0){
jumlah = bilangan[i];
}lain{
jumlah += bilangan[i];

            }
            max = Math.max(max, sum);
        }else{
            if(sum<0){
                sum = nums[i];
            }else{
            sum += nums[i];
            }
            max = Math.max(max, sum);
        }
    }
    return max;

}

`

improve code
`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int max = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
for(int i=0; i if(sum < 0){
sum = nums[i];
}else{
sum += nums[i];

            }
            max = Math.max(max, sum);
    }
    return max;

}

`

Another way for greedy
`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int max = Integer.MIN_VALUE;
// int sum = Integer.MIN_VALUE;

    int sum = 0;
    for(int i=0; i<nums.length; i++){
        sum+= nums[i];
        if(max < sum){
            max = sum;
        }
        if(sum <0){
            sum = 0;
        }
            // if(sum < 0){
            //     sum = nums[i];
            // }else{
            //     sum += nums[i];

            // }
            // max = Math.max(max, sum);

    }
    return max;

}

`

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