对于第202场的周赛的个人题解

前言

本次周赛难度相比前一周来说真的是难度骤降,让人有了安心感(并不),前三题由个人完成,最后一题参考题解。

存在连续三个奇数的数组

给你一个整数数组 arr,请你判断数组中是否存在连续三个元素都是奇数的情况:如果存在,请返回 true ;否则,返回 false 。

示例 1:

输入:arr = [2,6,4,1]
输出:false
解释:不存在连续三个元素都是奇数的情况。
示例 2:

输入:arr = [1,2,34,3,4,5,7,23,12]
输出:true
解释:存在连续三个元素都是奇数的情况,即 [5,7,23] 。

提示:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000

两数相加级别的水题,直接放代码:

1
2
3
4
5
6
7
8
9
10
class Solution {
fun isOdd(number: Int) = number % 2 != 0

fun threeConsecutiveOdds(arr: IntArray): Boolean {
for (i in 0 until arr.size - 2) {
if (isOdd(arr[i]) && isOdd(arr[i + 1]) && isOdd(arr[i + 2])) return true
}
return false
}
}

时间复杂度:
$$
\mathcal{O}(N)
$$
空间复杂度:
$$
\mathcal{O}(1)
$$

使数组中所有元素相等的最小操作数

存在一个长度为 n 的数组 arr ,其中 arr[i] = (2 * i) + 1 ( 0 <= i < n )。

一次操作中,你可以选出两个下标,记作 x 和 y ( 0 <= x, y < n )并使 arr[x] 减去 1 、arr[y] 加上 1 (即 arr[x] -=1 且 arr[y] += 1 )。最终的目标是使数组中的所有元素都 相等 。题目测试用例将会 保证 :在执行若干步操作后,数组中的所有元素最终可以全部相等。

给你一个整数 n,即数组的长度。请你返回使数组 arr 中所有元素相等所需的 最小操作数 。

示例 1:

输入:n = 3
输出:2
解释:arr = [1, 3, 5]
第一次操作选出 x = 2 和 y = 0,使数组变为 [2, 3, 4]
第二次操作继续选出 x = 2 和 y = 0,数组将会变成 [3, 3, 3]
示例 2:

输入:n = 6
输出:9

提示:

1 <= n <= 10^4

这里如果嗯写的话时间复杂度肯定会爆掉的($\mathcal{O}(N^2)$级别数据就已经到达$10^8$了,肯定爆了),所以换思路,仔细查看会发现这是一个遵循一定规律(函数规律)的数列,所以易推出数据以中位数为中心中心对称,即是中位数右边数字减去中位数等于中位数减去中位数左边数字,所以易推出差值为等差数列,奇数除以2的时候会丢失$\frac{1}{2}$的精度,但是我们需要的只是一个和值,只要是损失在1之内都可以接受:

1
2
3
4
5
6
class Solution {
fun minOperations(n: Int): Int {
// 中位数是n
return (n * n) shr 2
}
}

时间复杂度:
$$
\mathcal{O}(1)
$$
空间复杂度:
$$
\mathcal{O}(1)
$$

两球之间的磁力

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

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

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

示例 1:

img
img

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

输入: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

经典暴力思想转二分优化应用题目(其实开始想dp的来着,得亏群里高人指点)。这里其实有个隐藏条件,看似是随意分布的各个球体,其实为了最大化最小磁力,每个球之间的间隔距离其实肯定是一样的,即是理想情况下最大化的最小间隔距离一定是$\frac{length}{m}$,所以根据上面的思路,我们修改一下判断函数,判断是否可以以当前间隔进行等分,然后对于每一次间隔选取进行左右二分,就完成了:

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
class Solution {
fun maxDistance(position: IntArray, m: Int): Int {
position.sort()
val maxp = position.last() - position.first()
var minp = Int.MAX_VALUE
for (i in 0 until position.size - 1) {
if (minp > position[i + 1] - position[i])
minp = position[i + 1] - position[i]
}

var lo = minp
var hi = maxp / (m - 1)

val check = fun(inter: Int): Boolean {
var cnt = 0
// 因为第一个肯定是在首位,所以直接跳过一个
var tmp = position[0] + inter
for (i in position.indices) {
if (position[i] >= tmp) {
cnt++
tmp = position[i] + inter
}
}
return cnt >= m - 1
}

while (lo <= hi) {
val mid = lo + ((hi - lo) shr 1)

if (check(mid))
lo = mid + 1
else
hi = mid - 1
}

return lo - 1
}
}

时间复杂度:
$$
\mathcal{O}(Nlog_2(N))
$$
空间复杂度:
$$
\mathcal{O}(1)
$$

吃掉 N 个橘子的最少天数

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

  • 吃掉一个橘子。

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

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

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

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

示例 1:

输入: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:

输入: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:

输入:n = 1
输出:1

示例 4:

输入:n = 56
输出:6

提示:

1 <= n <= 2*10^9

额,这个题当时盲猜暴力dfs/bfs搜索,但是肯定会超时,所以就没写下去,打算看题解了,下面都是题解思路。

看了一下题解好像dfs+离散化+剪枝好像能解,尝试一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
val map = HashMap<Int, Int>()

fun minDays(n: Int): Int {
// 小于直接返回了
if (n <= 2) {
return n
}

// 记忆化搜索
if (map.containsKey(n)) {
return map[n]!!
}

// 这里+n%3是考虑到吃一个的情况的,吃掉了n%3次的一个,然后和n%2进行次数比较
val min = min(minDays(n / 3) + n % 3, minDays(n / 2) + n % 2) + 1
map[n] = min
return min
}
}

好像写成了贪心+记忆化搜索了…….

解释一下为什么可以这样写,思考三种情况(/3, /2, -1),其中-1效率必是无法与/3,/2的效率相比拟的,所以,最小化天数一定是最大化/3,/2这种情况,至于哪个比较小则需要进一步比较了。

时间复杂度:

这里存在$log_2(N)$和$log_3(N)$混合,统一归为$log(N)$
$$
\mathcal{O}(log(N)^2)
$$
空间复杂度(这个其实不好判断,看数据离散程度了):
$$
\mathcal{O}(N)
$$

参考

[python3] 图解剪枝+递归+记忆化,时间复杂度O(log(N)²)

方法选择:BFS vs DFS vs DP

数学证明:为什么用“贪心”DP是对的?