Re: [閒聊] 每日leetcode已回收
※ 引述《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
推
06/19 16:36,
1年前
, 1F
06/19 16:36, 1F
推
06/19 17:18,
1年前
, 2F
06/19 17:18, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 382 之 1550 篇)：