Skip to content

Commit 8e05c11

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1482. Minimum Number of Days to Make m Bouquets
1 parent e4ccdff commit 8e05c11

File tree

5 files changed

+283
-8
lines changed

5 files changed

+283
-8
lines changed

‎solution/1400-1499/1482.Minimum Number of Days to Make m Bouquets/README.md

Lines changed: 98 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -76,7 +76,7 @@
7676

7777
<!-- 这里可写通用的实现逻辑 -->
7878

79-
利用二分查找快速定位
79+
利用二分查找快速定位。
8080

8181
<!-- tabs:start -->
8282

@@ -91,7 +91,7 @@ class Solution:
9191
return -1
9292

9393
def check(day: int) -> bool:
94-
cnt, cur = 0, 0
94+
cnt = cur = 0
9595
for bd in bloomDay:
9696
cur = cur + 1 if bd <= day else 0
9797
if cur == k:
@@ -101,7 +101,7 @@ class Solution:
101101

102102
left, right = min(bloomDay), max(bloomDay)
103103
while left < right:
104-
mid = (left + right) // 2
104+
mid = (left + right) >> 1
105105
if check(mid):
106106
right = mid
107107
else:
@@ -150,6 +150,101 @@ class Solution {
150150
}
151151
```
152152

153+
### **C++**
154+
155+
```cpp
156+
class Solution {
157+
public:
158+
int minDays(vector<int>& bloomDay, int m, int k) {
159+
if (m * k > bloomDay.size()) {
160+
return -1;
161+
}
162+
int mi = INT_MIN, mx = INT_MAX;
163+
for (int& bd : bloomDay) {
164+
mi = min(mi, bd);
165+
mx = max(mx, bd);
166+
}
167+
int left = mi, right = mx;
168+
while (left < right) {
169+
int mid = left + right >> 1;
170+
if (check(bloomDay, m, k, mid)) {
171+
right = mid;
172+
} else {
173+
left = mid + 1;
174+
}
175+
}
176+
return left;
177+
}
178+
179+
bool check(vector<int>& bloomDay, int m, int k, int day) {
180+
int cnt = 0, cur = 0;
181+
for (int& bd : bloomDay) {
182+
cur = bd <= day ? cur + 1 : 0;
183+
if (cur == k) {
184+
++cnt;
185+
cur = 0;
186+
}
187+
}
188+
return cnt >= m;
189+
}
190+
};
191+
```
192+
193+
### **Go**
194+
195+
```go
196+
func minDays(bloomDay []int, m int, k int) int {
197+
if m*k > len(bloomDay) {
198+
return -1
199+
}
200+
mi, mx := 0, 1000000000
201+
for _, bd := range bloomDay {
202+
mi = min(mi, bd)
203+
mx = max(mx, bd)
204+
}
205+
left, right := mi, mx
206+
for left < right {
207+
mid := (left + right) >> 1
208+
if check(bloomDay, m, k, mid) {
209+
right = mid
210+
} else {
211+
left = mid + 1
212+
}
213+
}
214+
return left
215+
}
216+
217+
func check(bloomDay []int, m, k, day int) bool {
218+
cnt, cur := 0, 0
219+
for _, bd := range bloomDay {
220+
if bd <= day {
221+
cur++
222+
} else {
223+
cur = 0
224+
}
225+
if cur == k {
226+
cnt++
227+
cur = 0
228+
}
229+
}
230+
return cnt >= m
231+
}
232+
233+
func max(a, b int) int {
234+
if a > b {
235+
return a
236+
}
237+
return b
238+
}
239+
240+
func min(a, b int) int {
241+
if a < b {
242+
return a
243+
}
244+
return b
245+
}
246+
```
247+
153248
### **...**
154249

155250
```

‎solution/1400-1499/1482.Minimum Number of Days to Make m Bouquets/README_EN.md

Lines changed: 98 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -134,7 +134,7 @@ It is obvious that we can make two bouquets in different ways.
134134

135135
## Solutions
136136

137-
Quickly locate using binary search
137+
Quickly locate using binary search.
138138

139139
<!-- tabs:start -->
140140

@@ -147,7 +147,7 @@ class Solution:
147147
return -1
148148

149149
def check(day: int) -> bool:
150-
cnt, cur = 0, 0
150+
cnt = cur = 0
151151
for bd in bloomDay:
152152
cur = cur + 1 if bd <= day else 0
153153
if cur == k:
@@ -157,7 +157,7 @@ class Solution:
157157

158158
left, right = min(bloomDay), max(bloomDay)
159159
while left < right:
160-
mid = (left + right) // 2
160+
mid = (left + right) >> 1
161161
if check(mid):
162162
right = mid
163163
else:
@@ -204,6 +204,101 @@ class Solution {
204204
}
205205
```
206206

207+
### **C++**
208+
209+
```cpp
210+
class Solution {
211+
public:
212+
int minDays(vector<int>& bloomDay, int m, int k) {
213+
if (m * k > bloomDay.size()) {
214+
return -1;
215+
}
216+
int mi = INT_MIN, mx = INT_MAX;
217+
for (int& bd : bloomDay) {
218+
mi = min(mi, bd);
219+
mx = max(mx, bd);
220+
}
221+
int left = mi, right = mx;
222+
while (left < right) {
223+
int mid = left + right >> 1;
224+
if (check(bloomDay, m, k, mid)) {
225+
right = mid;
226+
} else {
227+
left = mid + 1;
228+
}
229+
}
230+
return left;
231+
}
232+
233+
bool check(vector<int>& bloomDay, int m, int k, int day) {
234+
int cnt = 0, cur = 0;
235+
for (int& bd : bloomDay) {
236+
cur = bd <= day ? cur + 1 : 0;
237+
if (cur == k) {
238+
++cnt;
239+
cur = 0;
240+
}
241+
}
242+
return cnt >= m;
243+
}
244+
};
245+
```
246+
247+
### **Go**
248+
249+
```go
250+
func minDays(bloomDay []int, m int, k int) int {
251+
if m*k > len(bloomDay) {
252+
return -1
253+
}
254+
mi, mx := 0, 1000000000
255+
for _, bd := range bloomDay {
256+
mi = min(mi, bd)
257+
mx = max(mx, bd)
258+
}
259+
left, right := mi, mx
260+
for left < right {
261+
mid := (left + right) >> 1
262+
if check(bloomDay, m, k, mid) {
263+
right = mid
264+
} else {
265+
left = mid + 1
266+
}
267+
}
268+
return left
269+
}
270+
271+
func check(bloomDay []int, m, k, day int) bool {
272+
cnt, cur := 0, 0
273+
for _, bd := range bloomDay {
274+
if bd <= day {
275+
cur++
276+
} else {
277+
cur = 0
278+
}
279+
if cur == k {
280+
cnt++
281+
cur = 0
282+
}
283+
}
284+
return cnt >= m
285+
}
286+
287+
func max(a, b int) int {
288+
if a > b {
289+
return a
290+
}
291+
return b
292+
}
293+
294+
func min(a, b int) int {
295+
if a < b {
296+
return a
297+
}
298+
return b
299+
}
300+
```
301+
207302
### **...**
208303

209304
```

‎solution/1400-1499/1482.Minimum Number of Days to Make m Bouquets/Solution.cpp

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
class Solution {
2+
public:
3+
int minDays(vector<int>& bloomDay, int m, int k) {
4+
if (m * k > bloomDay.size()) {
5+
return -1;
6+
}
7+
int mi = INT_MIN, mx = INT_MAX;
8+
for (int& bd : bloomDay) {
9+
mi = min(mi, bd);
10+
mx = max(mx, bd);
11+
}
12+
int left = mi, right = mx;
13+
while (left < right) {
14+
int mid = left + right >> 1;
15+
if (check(bloomDay, m, k, mid)) {
16+
right = mid;
17+
} else {
18+
left = mid + 1;
19+
}
20+
}
21+
return left;
22+
}
23+
24+
bool check(vector<int>& bloomDay, int m, int k, int day) {
25+
int cnt = 0, cur = 0;
26+
for (int& bd : bloomDay) {
27+
cur = bd <= day ? cur + 1 : 0;
28+
if (cur == k) {
29+
++cnt;
30+
cur = 0;
31+
}
32+
}
33+
return cnt >= m;
34+
}
35+
};

‎solution/1400-1499/1482.Minimum Number of Days to Make m Bouquets/Solution.go

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
func minDays(bloomDay []int, m int, k int) int {
2+
if m*k > len(bloomDay) {
3+
return -1
4+
}
5+
mi, mx := 0, 1000000000
6+
for _, bd := range bloomDay {
7+
mi = min(mi, bd)
8+
mx = max(mx, bd)
9+
}
10+
left, right := mi, mx
11+
for left < right {
12+
mid := (left + right) >> 1
13+
if check(bloomDay, m, k, mid) {
14+
right = mid
15+
} else {
16+
left = mid + 1
17+
}
18+
}
19+
return left
20+
}
21+
22+
func check(bloomDay []int, m, k, day int) bool {
23+
cnt, cur := 0, 0
24+
for _, bd := range bloomDay {
25+
if bd <= day {
26+
cur++
27+
} else {
28+
cur = 0
29+
}
30+
if cur == k {
31+
cnt++
32+
cur = 0
33+
}
34+
}
35+
return cnt >= m
36+
}
37+
38+
func max(a, b int) int {
39+
if a > b {
40+
return a
41+
}
42+
return b
43+
}
44+
45+
func min(a, b int) int {
46+
if a < b {
47+
return a
48+
}
49+
return b
50+
}

‎solution/1400-1499/1482.Minimum Number of Days to Make m Bouquets/Solution.py

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@ def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
44
return -1
55

66
def check(day: int) -> bool:
7-
cnt, cur = 0, 0
7+
cnt = cur = 0
88
for bd in bloomDay:
99
cur = cur + 1 if bd <= day else 0
1010
if cur == k:
@@ -14,7 +14,7 @@ def check(day: int) -> bool:
1414

1515
left, right = min(bloomDay), max(bloomDay)
1616
while left < right:
17-
mid = (left + right) // 2
17+
mid = (left + right) >> 1
1818
if check(mid):
1919
right = mid
2020
else:

0 commit comments

Comments
 (0)