算法leetcode

【二分难题】力扣2560-打家劫舍4

字数统计: 1.4k字   |   阅读时长: 5分
, ,

摘要: 值域二分+其他算法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一个最小化最大值的问题，值域二分是解决这种问法的常规思路。对于二分的答案，一般还需要别的算法来判断该答案能否满足要求，本题的这一步比较难，有动态规划和贪心两种算法。

题目

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋 。

小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额 。

给你一个整数数组 nums 表示每间房屋存放的现金金额。形式上，从左起第 i 间房屋中放有 nums[i] 美元。

另给你一个整数 k ，表示窃贼将会窃取的 最少 房屋数。小偷总能窃取至少 k 间房屋。

返回小偷的 最小 窃取能力。

提示：

1
2
3
1 <= nums.length <= 1e5
1 <= nums[i] <= 1e9
1 <= k <= (nums.length + 1)/2

示例 1：
输入：nums = [2,3,5,9], k = 2
输出：5
解释：
小偷窃取至少 2 间房屋，共有 3 种方式：

  • 窃取下标 0 和 2 处的房屋，窃取能力为 max(nums[0], nums[2]) = 5 。
  • 窃取下标 0 和 3 处的房屋，窃取能力为 max(nums[0], nums[3]) = 9 。
  • 窃取下标 1 和 3 处的房屋，窃取能力为 max(nums[1], nums[3]) = 9 。
    因此，返回 min(5, 9, 9) = 5 。

示例 2：
输入：nums = [2,7,9,3,1], k = 2
输出：2
解释：共有 7 种窃取方式。窃取能力最小的情况所对应的方式是窃取下标 0 和 4 处的房屋。返回 max(nums[0], nums[4]) = 2 。

题解

由于偷走的最大金额越小，能偷的房子越少，能偷走的最大金额越大，能偷的房子越多。比如 nums=[2,3,5,9], k=2，当最大金额为 3 时，只有 2, 3 是可以偷的，而当最大金额为 9 时，2,3,5,9 都可以偷。

基于以上的单调性的特性，我们二分偷走的最大金额，记其为 $mid$，接下来要设计一个判断过程 check(mid)，判断 $mid$ 能否满足要求。

在判断过程 check(mid) 中，我们求出最多能偷多少个房间，记其为 $cnt$：

  • 如果 $cnt >= k$，则 $mid$ 满足要求，答案有可能更小，此时设 $right = mid$。
  • 如果 $cnt < k$，则 $mid$ 不满足要求，答案必须更大，此时设 $left = mid + 1$。

下面的问题就是在 check(mid) 中如何求出最多能偷多少个房间。有动态规划和贪心两种方法。

算法1：值域二分 + 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
状态定义：
dp[i] := nums[0..i] 中偷金额不超过 mid 的房屋，最多能偷的房间数

答案：
dp[n - 1]

初始化：
dp[0] = 1   if nums[0] <= mid
        0   other
dp[1] = 1   if dp[0] = 1 or nums[1] <= mid
        0   other

状态转移：
当 nums[i] > mid，只能不选 nums[i]：
    dp[i] = dp[i - 1]
当 nums[i] <= mid 时，还有可能选 nums[i]：
    dp[i] = max(dp[i - 1], dp[i - 2] + 1)

代码 (Python)

实现的时候可以用两个变量 dp0, dp1 滚动计算。

其中 dp0 相当于 dp[i-2]，dp1 相当于 dp[i-1]。

如果 nums[i] > mid，先赋值 dp[i] = dp1，然后滚动 dp0 = dp1, dp1 = dp[i]，整个过程其实就是 dp0 = dp1。

如果 nums[i] <= mid，先赋值 dp[i] = max(dp1, dp0 + 1)，然后滚动 dp0 = dp1, dp1 = dp[i]，整个过程可以写为 dp0, dp1 = dp1, max(dp1, dp0 + 1)。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        # check(mid) 返回最大金额为 mid 时，最多可以偷多少房子
        def check(mid: int) -> int:
            dp0 = dp1 = 0
            for num in nums:
                if num > mid:
                    dp0 = dp1
                else:
                    dp0, dp1 = dp1, max(dp1, dp0 + 1)
            return dp1
        return bisect_left(range(max(nums)), k, key=check)

算法2：值域二分 + 贪心

从左到右遍历，只要当前的房子满足条件 nums[i-1] 没偷且 nums[i] <= mid，则 nums[i] 可以偷，那就直接偷。

考虑动态规划的状态转移方程 $dp[i] = \max(dp[i-1], dp[i-2]+1)$，由此可以知道 $dp[i] \geq dp[i - 1]$，也就是说 dp 数组是递增的。

另一方面 $dp[i] - dp[i - 1] \leq 1$，因为统计的是个数，$dp[i-1]$ 到 $dp[i]$ 最多增加 1。因此 $dp[i - 2] + 1 \geq dp[i - 1]$。

综上，当 $nums[i] \leq mid$ 时，不用判断 $dp[i] = max(dp[i - 1], dp[i - 2] + 1)$，直接赋值 $dp[i] = dp[i - 2] + 1$ 即可。

由上式，在从左到右遍历 nums 时，如果 $nums[i] \leq mid$，那么就直接偷 $nums[i]$，同时跳过 $nums[i + 1]$。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        # check(mid) 返回最大金额为 mid 时，最多可以偷多少房子
        def check(mid: int) -> int:
            n = len(nums)
            i = 0
            ans = 0
            while i < n:
                if nums[i] <= mid:
                    ans += 1
                    i += 2
                else:
                    i += 1
            return ans
        return bisect_left(range(max(nums)), k, key=check)
Share