202期比赛题目解法

发表于

5489. 两球之间的磁力

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

已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |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
}