济南企业建站哪家做的好,教育类网页设计,中国wordpress用的人少,玉林做网站这是二分法的第23篇算法#xff0c;力扣链接。 给你一个整数数组 bloomDay#xff0c;以及两个整数 m 和 k 。 现需要制作 m 束花。制作花束时#xff0c;需要使用花园中 相邻的 k 朵花 。 花园中有 n 朵花#xff0c;第 i 朵花会在 bloomDay[i] 时盛开#xff0c;恰好 可…这是二分法的第23篇算法力扣链接。 给你一个整数数组 bloomDay以及两个整数 m 和 k 。 现需要制作 m 束花。制作花束时需要使用花园中 相邻的 k 朵花 。 花园中有 n 朵花第 i 朵花会在 bloomDay[i] 时盛开恰好 可以用于 一束 花中。 请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。 示例 1 输入bloomDay [1,10,3,10,2], m 3, k 1
输出3
解释让我们一起观察这三天的花开过程x 表示花开而 _ 表示花还未开。
现在需要制作 3 束花每束只需要 1 朵。
1 天后[x, _, _, _, _] // 只能制作 1 束花
2 天后[x, _, _, _, x] // 只能制作 2 束花
3 天后[x, _, x, _, x] // 可以制作 3 束花答案为 3示例 2 输入bloomDay [1,10,3,10,2], m 3, k 2
输出-1
解释要制作 3 束花每束需要 2 朵花也就是一共需要 6 朵花。而花园中只有 5 朵花无法满足制作要求返回 -1 。示例 3 输入bloomDay [7,7,7,7,12,7,7], m 2, k 3
输出12
解释要制作 2 束花每束需要 3 朵。
花园在 7 天后和 12 天后的情况如下
7 天后[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花因为它们不相邻。
12 天后[x, x, x, x, x, x, x]
显然我们可以用不同的方式制作两束花。示例 4 输入bloomDay [1000000000,1000000000], m 1, k 1
输出1000000000
解释需要等 1000000000 天才能采到花来制作花束 这道题不整花里胡哨的了直接开始二分法分析题目。这里左指针右指针取值范围一定会在数组范围内所以这里尝试取最大值最小值为右指针左指针关于指针移动的临界条件的话这里考虑去遍历数组查看采到的花数来比较。
注意这里的mid取值相等于预期花束也不着急返回因为不一定是最小值这里要尝试取到左边界。
func minDays(bloomDay []int, m int, k int) int {if len(bloomDay) m*k {return -1}l, r : math.MaxInt, 0for _, day : range bloomDay {if l day {l day}if r day {r day}}for l r {mid : l (r-l)/2flowerCount : checkFlowers(mid, bloomDay, k)if flowerCount m {r mid - 1} else {l mid 1}}return l
}func checkFlowers(day int, bloomDay []int, k int) int {result, count : 0, 0for _, bloomDay : range bloomDay {if bloomDay day {countif count k {resultcount 0}} else {count 0}}return result
}
