LeetCode 周赛 350(2023/06/18)01 背包变型题

leetcode,背包,变型 · 浏览次数 : 30

小编点评

**思路解析:** 1. **备忘录动态规划**:使用 `memo` 数组记录每个状态的最佳答案,以避免重复计算。 2. **贪心策略**:选择开销最小的选项,即使这意味着在某些情况下可能不最优。 3. **0 1 背包**:在每个状态中,考虑两种选择:分配给付费油漆匠或免费油漆匠。 4. **滚动数组优化**:在计算子状态时,可以利用滚动数组存储已计算的答案,以节省空间。 **时间复杂度分析:** * 时间复杂度为 O(n^2),其中 n 是数组的长度。这是因为每个状态被计算两次,一次用于计算子状态,一次用于计算父状态。 * 空间复杂度为 O(n),这是因为 `memo` 数组需要存储每个状态的最佳答案。 **空间复杂度分析:** * 由于使用滚动数组,空间复杂度为 O(n),其中 n 是数组的长度。 * 然而,滚动数组的开销可能比普通动态规划更高,因此实际空间复杂度可能比 O(n) 更高。

正文

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。

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(n2·2n) 总共有 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 背包模型解决。

我们定义 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(n^2)
  • 空间复杂度:(n)

往期回顾

与LeetCode 周赛 350(2023/06/18)01 背包变型题相似的内容:

LeetCode 周赛 350(2023/06/18)01 背包变型题

> **本文已收录到 [AndroidFamily](https://github.com/pengxurui/AndroidFamily),技术和职场问题,请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。** - 往期回顾:[LeetCode 单周赛第 348 场 · 数

LeetCode 周赛 352(2023/07/02)一场关于子数组的专题周赛

> **本文已收录到 [AndroidFamily](https://github.com/pengxurui/AndroidFamily),技术和职场问题,请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问。** - 往期回顾:[LeetCode 单周赛第 350 场 · 滑

LeetCode 周赛 332,在套路里摸爬滚打~

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,今天是 3T 选手小彭。 上周是 LeetCode 第 332 场周赛,你参加了吗?算法解题思维需要长时间锻炼,加入我们一起刷题吧~ 小彭的 Android 交流群 02 群已经建立啦,公众号回复 “

LeetCode 周赛 333,你管这叫 Medium 难度?

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周是 LeetCode 第 333 场周赛,你参加了吗?这场周赛质量很高,但难度标得不对,我真的会谢。算法解题思维需要长时间锻炼,加入我们一起刷题吧~ 小彭的 Android 交流群 0

LeetCode 周赛 334,在算法的世界里反复横跳

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 今天是 LeetCode 第 334 场周赛,你参加了吗?这场周赛考察范围比较基础,整体难度比较平均,第一题难度偏高,第四题需要我们在算法里实现 “反复横跳”,非常有意思。 小彭的 And

LeetCode 周赛 335,纯纯手速场!

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 昨晚是 LeetCode 第 335 场周赛,你参加了吗?这场周赛整体难度不高,有两道模板题,第三题和第四题应该调换一下位置。 小彭的 Android 交流群 02 群来了,公众号回复 “

LeetCode 周赛 336,多少人直接 CV?

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 今天早上是 LeetCode 第 336 场周赛,你参加了吗?这场周赛整体质量比较高,但是最后一题是老题,CV 能过。但是输入数据范围被降低了,这操作也是没谁了。 2587. 统计范围内的

LeetCode 周赛 338,贪心 / 埃氏筛 / 欧氏线性筛 / 前缀和 / 二分查找 / 拓扑排序

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周末是 LeetCode 第 338 场周赛,你参加了吗?这场周赛覆盖的知识点很多,第四题称得上是近期几场周赛的天花板。 小彭的技术交流群 02 群来了,公众号回复 “加群” 加入我们~

LeetCode 周赛 340,质数 / 前缀和 / 极大化最小值 / 最短路 / 平衡二叉树

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周跟大家讲到小彭文章风格的问题,和一些朋友聊过以后,至少在算法题解方面确定了小彭的风格。虽然竞赛算法题的文章受众非常小,但却有很多像我一样的初学者,他们有兴趣参加但容易被题目难度和大神选

LeetCode 周赛 341 场,模拟 / 树上差分 / Tarjan 离线 LCA / DFS

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周末有单双周赛,双周赛我们讲过了,单周赛那天早上有事没参加,后面做了虚拟竞赛,然后整个人就不好了。前 3 题非常简单,但第 4 题有点东西啊,差点就放弃了。最后,被折磨了一个下午和一个大