202期比赛题目解法

5489. 两球之间的磁力

在代号为 C-137 的地球上,Rick 发现如果他将两个球放在他新发明的篮子里,它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子,第 i 个篮子的位置在 position[i] ,Morty 想把 m 个球放到这些篮子里,使得任意两球间 最小磁力 最大。

已知两个球如果分别位于 xy ,那么它们之间的磁力为 |x - y|

给你一个整数数组 position 和一个整数 m ,请你返回最大化的最小磁力。

示例 1:

img

1
2
3
输入:position = [1,2,3,4,7], m = 3
输出:3
解释:将 3 个球分别放入位于 1,4 和 7 的三个篮子,两球间的磁力分别为 [3, 3, 6]。最小磁力为 3 。我们没办法让最小磁力大于 3 。

示例 2:

1
2
3
输入:position = [5,4,3,2,1,1000000000], m = 2
输出:999999999
解释:我们使用位于 1 和 1000000000 的篮子时最小磁力最大。

提示:

  • n == position.length
  • 2 <= n <= 10^5
  • 1 <= position[i] <= 10^9
  • 所有 position 中的整数 互不相同
  • 2 <= m <= position.length

解答

思路

  • step 1.
    首先我们对position排序,得到按顺序排列的篮子

  • step 2.
    最小的磁力:就是这些m个篮子间那个最短的距离
    最大的磁力:就是把最大间距(position的尾减头)平均分,保证篮子间的距离都一样
    所以能取到的磁力范围必定落在【最小磁力,最大磁力】这个区间上

  • step 3.
    可以从小往大找,也可以从大往小找,也可以使用二分法从中间开始找,这种时间复杂度应该是最低的
    所谓的磁力其实就是间隔,假设我们区间中间的磁力是mid,要对间隔 mid 的放球法做出判断,看看能不能这样放
    验证的方法是:从第一个篮子开始逐个放球,如果下一个篮子距离上一个篮子没有mid那么远,就选后面的一个篮子,直至放球的篮子间达到距离mid的要求。如果球全放完了,证明成功;如果有球无法按要求放了则证明失败

  • step 4.
    如果step 3中的验证成功,我们可以试试更大的距离;如果失败,则用更小的距离。更大更小的距离也是通过二分法选择,直至找到那个最大的距离
    [以上来自力扣题解]

基本代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func maxDistance(position []int, m int) int {
sort.Ints(position)
//1. 获得最大的距离
hi := (position[len(position)-1] - position[0]) / (m - 1)
//2. 最小的距离是 1
lo := 1
ans := 1
//3. 距离一定在 最大和最小之间 ,使用二分法寻找
for lo <= hi {
mid := lo + (hi-lo)/2
//4. 判断找到的位置 是否能够把剩余的球放下
//5. 如果从前半段能够把球放下,则继续把 mid 向后移动,尝试更大的范围
//6. 同理如果前半段放不下,则需要压缩 mid 的值
if judge(position, mid, m) {
ans = mid
lo = mid + 1
} else {
hi = mid - 1
}
}
return ans
}

func judge(position []int, mid, m int) bool {
count := 1
i := 0
//判断在 position 中,放 m 个求能否放下。
for j := 1; j < len(position); j++ {
if position[j]-position[i] >= mid {
i = j
count++
if count >= m {
return true
}
}
}
return false
}


5490. 吃掉 N 个橘子的最少天数

厨房里总共有 n 个橘子,你决定每一天选择如下方式之一吃这些橘子:

  • 吃掉一个橘子。
  • 如果剩余橘子数 n 能被 2 整除,那么你可以吃掉 n/2 个橘子。
  • 如果剩余橘子数 n 能被 3 整除,那么你可以吃掉 2*(n/3) 个橘子。

每天你只能从以上 3 种方案中选择一种方案。

请你返回吃掉所有 n 个橘子的最少天数。

示例 1:

1
2
3
4
5
6
7
8
输入:n = 10
输出:4
解释:你总共有 10 个橘子。
第 1 天:吃 1 个橘子,剩余橘子数 10 - 1 = 9。
第 2 天:吃 6 个橘子,剩余橘子数 9 - 2*(9/3) = 9 - 6 = 3。(9 可以被 3 整除)
第 3 天:吃 2 个橘子,剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。
第 4 天:吃掉最后 1 个橘子,剩余橘子数 1 - 1 = 0。
你需要至少 4 天吃掉 10 个橘子。

示例 2:

1
2
3
4
5
6
7
输入:n = 6
输出:3
解释:你总共有 6 个橘子。
第 1 天:吃 3 个橘子,剩余橘子数 6 - 6/2 = 6 - 3 = 3。(6 可以被 2 整除)
第 2 天:吃 2 个橘子,剩余橘子数 3 - 2*(3/3) = 3 - 2 = 1。(3 可以被 3 整除)
第 3 天:吃掉剩余 1 个橘子,剩余橘子数 1 - 1 = 0。
你至少需要 3 天吃掉 6 个橘子。

示例 3:

1
2
输入:n = 1
输出:1

示例 4:

1
2
输入:n = 56
输出:6

提示:

  • 1 <= n <= 2*10^9

解题思路

递归思路:
n%2 代表如果吃掉 1/2 的时候,需要吃掉 1 的天数
n%3 带边需要吃掉 2/3 多出来的 1 的个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func minDays(n int) int {
m := make(map[int]int)
return core(n,m)
}

func core(n int, m map[int]int) int {
if n == 1 {
return 1
}
if n == 2 {
return 2
}
ret, hasKey := m[n]
if hasKey {
return ret
}
ret = min(core(n/2,m)+n%2+1, min(core(n/3,m)+n%3+1, n))

m[n] = ret
return ret
}

func min(v1, v2 int) int {
if v1 > v2 {
return v2
}
return v1
}
作者

付威

发布于

2020-08-15

更新于

2020-08-22

许可协议

评论