本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 [BaguTree Pro] 常识星球发问。
- 往期回顾：LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗？
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(log_5{n})
- 空间复杂度：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(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(n^2·2^n) 总共有 n·2^n 种状态，每种状态的转移次数最多为 O(n)；
- 空间复杂度：O(n·2^n) 备忘录空间。
T4. 给墙壁刷油漆（Hard）
https://leetcode.cn/problems/painting-the-walls/题解（01 背包）
思路参考灵神的题解。
须要思考到优先让付费油漆匠刷最低开销的墙的贪婪计划是谬误的。
容易发现对于第 i 面墙来说，当且只有调配给付费油漆匠或收费油漆匠 2 种抉择，且有：
- 付费墙数 + 收费墙数 = n
- 付费刷墙工夫之和 ≥ 收费墙数
联结两式有：付费墙数 + 付费刷墙工夫之和 ≥ n，即 (付费刷墙工夫 + 1) 之和 ≥ n。那么，此时问题变成从 n 面墙中抉择 x 面付费墙，使得满足 (刷墙工夫 + 1) ≥ n 时的最小开销，能够用 0 1 背包模型解决。
咱们定义 dpi 示意思考到 i 为止，且 (刷墙工夫 + 1) 为 j 时的最小开销，则对于 第 i 面墙存在两种转移形式：
- 调配给付费油漆匠（选）：那么 dpi = dpi - 1 - 1] + cost[i]
- 调配给收费油漆匠（不选）：那么 dpi = dpi - 1
起始条件：dp0 = 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 墙的开销，即 dpi-1 + 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(n^2)
- 空间复杂度：(n)
往期回顾
- LeetCode 单周赛第 348 场 · 数位 DP 模版学会了吗？
- LeetCode 单周赛第 347 场 · 二维空间上的 LIS 最长递增子序列问题
- LeetCode 双周赛第 104 场 · 流水的动静布局，铁打的结构化思考
- LeetCode 双周赛第 103 场 · 区间求和的树状数组经典利用