Re: [閒聊] 每日leetcode

[Rushia (早瀬ユウカの体操服 )]

※ 引述《oin1104 (是oin的說)》之銘言：
: 1482. Minimum Number of Days to Make m Bouquets
: You are given an integer array bloomDay, an integer m and an integer k.
: You want to make m bouquets. To make a bouquet, you need to use k adjacent flowe
: rs from the garden.
: The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] a
: nd then can be used in exactly one bouquet.
: Return the minimum number of days you need to wait to be able to make m bouquets
:  from the garden. If it is impossible to make m bouquets return -1.
: Example 1:
: Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
: Output: 3
: 題目 :
: 花園裡面有花
: 在他們的 bloomDay[i] 天開花
: 如果想要有m群 有k個相鄰的花 的花叢
: 那麼最少需要幾天
思路：
1.一樣偷看提示發現可以二分搜，我本來第一個corner case判斷是寫
  m * k > bloomDay.length 結果第92個 case 給了一個超大的 m和k
  導致溢位WA，結論就是恨py。

java code
----------------------------------------------
class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        if (m > bloomDay.length / k) {
            return -1;
        }
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int day : bloomDay) {
            min = Math.min(min, day);
            max = Math.max(max, day);
        }
        while (min < max) {
            int day = (min + max)/2;
            int currBouquets = 0;
            int numerOfBouquet = 0;
            for (int i = 0; i < bloomDay.length; i++) {
                if (bloomDay[i] > day) {
                    numerOfBouquet = 0;
                    continue;
                }
                if (++numerOfBouquet == k) {
                    currBouquets++;
                    numerOfBouquet = 0;
                    if (currBouquets == m) {
                        break;
                    }
                }
            }
            if (currBouquets == m) {
                max = day;
            } else {
                min = day + 1;
            }
        }
        return min;
    }
}
----------------------------------------------

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1718786180.A.F90.html
推 JIWP: 大師
推 oin1104: 大師