⭐️ 本文已收录到 AndroidFamily,技术和职场问题,请重视大众号 [彭旭锐] 和 [BaguTree Pro] 常识星球发问。
学习数据结构与算法的关键在于掌握问题背后的算法思想结构,你的考虑越笼统,它能掩盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题陈述,一起体会上分之旅。
本文是 LeetCode 上分之旅系列的第 27 篇文章,往期回忆请移步到文章末尾~
T1. 总行驶间隔(Easy)
- 标签:模拟
T2. 找出分区值(Medium)
- 标签:排序
T3. 特别的摆放(Medium)
- 标签:图、状况紧缩、回溯
T4. 给墙面刷油漆(Hard)
- 标签:动态规划、01 背包
T1. 总行驶间隔(Easy)
https://leetcode.cn/problems/total-distance-traveled/
题解(模拟)
WA 的举手:
class Solution {
fun distanceTraveled(mainTank: Int, additionalTank: Int): Int {
return mainTank * 10 + Math.min(additionalTank, mainTank / 5) * 10
}
}
这道题需求考虑加油后又补足 5 升油量的状况:
class Solution {
fun distanceTraveled(mainTank: Int, additionalTank: Int): Int {
var ret = 0
var x = mainTank
var y = additionalTank
while (x >= 5) {
val time = x / 5
ret += time * 50
x %= 5
val diff = Math.min(time, y)
y -= diff
x += diff
}
return ret + x * 10
}
}
复杂度剖析:
- 时刻复杂度:O(log5n)O(log_5{n})
- 空间复杂度:O(1)O(1)
T2. 找出分区值(Medium)
https://leetcode.cn/problems/find-the-value-of-the-partition/
题解(排序)
排序后计算最小差值:
class Solution {
fun findValueOfPartition(nums: IntArray): Int {
nums.sort()
var ret = Integer.MAX_VALUE
for(i in 1 until nums.size) {
ret = Math.min(ret, nums[i] - nums[i - 1])
}
return ret
}
}
复杂度剖析
- 时刻复杂度:O(nlgn)O(nlgn)
- 空间复杂度:O(lgn)O(lgn)
T3. 特别的摆放(Medium)
https://leetcode.cn/problems/special-permutations/
题解(图 + 状况紧缩 + 回溯)
因为题目要求相邻元素之间至少存在单向整除联系,简单想到咱们需求预处理数据,记载每个元素在作为 (x, y) 相邻对中的 x 时,下一个数 y 可以挑选什么数,即从 x 到 y 存在单向边。
val edge = HashMap<Int, MutableList<Int>>()
for ((i,x) in nums.withIndex()) {
edge[x] = LinkedList<Int>()
for (y in nums) {
if (x == y) continue
if (x % y == 0 || y % x == 0) edge[x]!!.add(y)
}
}
这道题的最大有 14 个数,那么运用全摆放将至少需求 14! 种状况,暴力全摆放会不会超时呢?可以运用经验值 10! = 3628800 约等于 3 10^6,那么 14! 必定大于 3 10^6 10^4,显然是会超时的。
运用状况紧缩可以处理这个问题,咱们界说 f(x, s) 表明最终挑选 x,且已挑选列表为 s 的状况下的计划数,其间 s 中的二进制位表明不同下标的数的挑选与未挑选状况,经过 s 就可概括多种摆放计划,最终咱们运用备忘录来剪枝。因为 14 可以被短整型的位数掩盖,因而咱们运用 (1 << 14) – 1 来作为初始状况,运用 0 作为停止条件。
class Solution {
private val MOD = 1000000007
fun specialPerm(nums: IntArray): Int {
val n = nums.size
val mask = 1 shl n
// 预处理
val edge = HashMap<Int, MutableList<Int>>()
for (x in nums.indices) {
edge[x] = LinkedList<Int>()
for (y in nums.indices) {
if (nums[x] != nums[y] && nums[x] % nums[y] == 0 || nums[y] % nums[x] == 0) edge[x]!!.add(y)
}
}
// 备忘录
val memo = Array(n) { IntArray(mask) {-1} }
fun backTrack(preIndex: Int, unUsed:Int) : Int{
// 停止条件
if (unUsed == 0) return 1
// 读备忘录
if (-1 != memo[preIndex][unUsed]) return memo[preIndex][unUsed]
var ret = 0
for (choice in edge[preIndex]!!) {
if (unUsed and (1 shl choice) == 0) continue
ret = (ret + backTrack(choice, unUsed xor (1 shl choice))) % MOD
}
// 存备忘录
memo[preIndex][unUsed] = ret
return ret
}
// 枚举首个元素的多种状况
var ret = 0
for (i in nums.indices) {
ret = (ret + backTrack(i, (mask - 1) xor (1 shl i))) % MOD
}
return ret
}
}
复杂度剖析:
- 时刻复杂度:O(n2⋅2n)O(n^22^n) 总共有 n⋅2nn2^n 种状况,每种状况的转移次数最多为 O(n)O(n);
- 空间复杂度:O(n⋅2n)O(n2^n) 备忘录空间。
T4. 给墙面刷油漆(Hard)
https://leetcode.cn/problems/painting-the-walls/
题解(01 背包)
思路参阅灵神的题解。
需求考虑到优先让付费油漆匠刷最低开支的墙的贪心计划是过错的。
简单发现关于第 i 面墙来说,当且只要分配给付费油漆匠或免费油漆匠 2 种挑选,且有:
- 付费墙数 + 免费墙数 = n
- 付费刷墙时刻之和 ≥ 免费墙数
联合两式有:付费墙数 + 付费刷墙时刻之和 ≥ n,即 (付费刷墙时刻 + 1) 之和 ≥ n。那么,此时问题变成从 n 面墙中挑选 x 面付费墙,使得满足 (刷墙时刻 + 1) ≥ n 时的最小开支,可以用 0 1 背包模型处理。
咱们界说 dp[i][j] 表明考虑到 i 停止,且 (刷墙时刻 + 1) 为 j 时的最小开支,则关于 第 i 面墙存在两种转移方法:
- 分配给付费油漆匠(选):那么 dp[i][j] = dp[i – 1][j – time[i] – 1] + cost[i]
- 分配给免费油漆匠(不选):那么 dp[i][j] = dp[i – 1][j]
起始条件:dp[0][0] = 0,表明考虑到第 0 面墙停止,且 (刷墙时刻 + 1) 为 0 时的最小开支为 0。
class Solution {
fun paintWalls(cost: IntArray, time: IntArray): Int {
val INF = 0x3F3F3F3F
val n = cost.size
// 刷墙时刻超越 n 没有意义
val dp = Array(n + 1) { IntArray(n + 1) { INF } }
// 初始状况(付费刷墙时刻为 0,开支为 0)
for (i in 0 .. n) dp[i][0] = 0
// 枚举物品
for (i in 1 .. n) {
// 枚举状况
for (j in 1 .. n) {
val t = time[i - 1] + 1
val c = cost[i - 1]
dp[i][j] = dp[i - 1][j]
dp[i][j] = Math.min(dp[i][j], dp[i - 1][Math.max(j - t, 0)] + c)
}
}
return dp[n][n]
}
}
其间关于 j < t 的状况,因为 j 表明付费刷墙时刻之和,而 t 表明刷第 i 面墙的时刻。假如 j – t < 0,那么等于刷墙之后丢掉一部分付费刷墙时刻,此时的花费不会最坏不会差过从初始状况选第 i 墙的开支,即 dp[i-1][Math.max(j-t,0)] + c。
0 1 背包问题一般可以选用翻滚数组优化空间:
class Solution {
fun paintWalls(cost: IntArray, time: IntArray): Int {
val INF = 0x3F3F3F3F
val n = cost.size
// 刷墙时刻超越 n 没有意义
val dp = IntArray(n + 1) { INF }
// 初始状况(付费刷墙时刻为 0,开支为 0)
dp[0] = 0
// 枚举物品
for (i in 1 .. n) {
// 枚举状况(逆序)
for (j in n downTo 1) {
val t = time[i - 1] + 1
val c = cost[i - 1]
dp[j] = Math.min(dp[j], dp[Math.max(j - t, 0)] + c)
}
}
return dp[n]
}
}
复杂度剖析:
- 时刻复杂度:O(n2)O(n^2)
- 空间复杂度:(n)(n)
引荐阅读
LeetCode 上分之旅系列往期回忆:
LeetCode 单周赛第 348 场 数位 DP 模版学会了吗?
LeetCode 单周赛第 347 场 二维空间上的 LIS 最长递增子序列问题
LeetCode 双周赛第 104 场 流水的动态规划,铁打的结构化考虑
LeetCode 双周赛第 103 场 区间求和的树状数组经典应用
⭐️ 永久相信美好的事情行将发生,欢迎参加小彭的 Android 沟通社群~