LeetCode 题解工作台
破解锁的最少时间 I
Bob 被困在了一个地窖里，他需要破解 n 个锁才能逃出地窖，每一个锁都需要一定的 能量 才能打开。每一个锁需要的能量存放在一个数组 strength 里，其中 strength[i] 表示打开第 i 个锁需要的能量。 Bob 有一把剑，它具备以下的特征： 一开始剑的能量为 0 。 剑的能量增加因子…
6
题型
5
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
class Solution: def findMinimumTime(self, strength: List[int], K: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
Bob 被困在了一个地窖里，他需要破解 n 个锁才能逃出地窖，每一个锁都需要一定的 能量 才能打开。每一个锁需要的能量存放在一个数组 strength 里，其中 strength[i] 表示打开第 i 个锁需要的能量。
Bob 有一把剑，它具备以下的特征：
- 一开始剑的能量为 0 。
- 剑的能量增加因子
X一开始的值为 1 。 - 每分钟，剑的能量都会增加当前的
X值。 - 打开第
i把锁，剑的能量需要到达 至少strength[i]。 - 打开一把锁以后，剑的能量会变回 0 ，
X的值会增加一个给定的值K。
你的任务是打开所有 n 把锁并逃出地窖，请你求出需要的 最少 分钟数。
请你返回 Bob 打开所有 n 把锁需要的 最少 时间。
示例 1：
输入：strength = [3,4,1], K = 1
输出：4
解释：
| 时间 | 能量 | X | 操作 | 更新后的 X |
|---|---|---|---|---|
| 0 | 0 | 1 | 什么也不做 | 1 |
| 1 | 1 | 1 | 打开第 3 把锁 | 2 |
| 2 | 2 | 2 | 什么也不做 | 2 |
| 3 | 4 | 2 | 打开第 2 把锁 | 3 |
| 4 | 3 | 3 | 打开第 1 把锁 | 3 |
无法用少于 4 分钟打开所有的锁，所以答案为 4 。
示例 2：
输入：strength = [2,5,4], K = 2
输出：5
解释：
| 时间 | 能量 | X | 操作 | 更新后的 X |
|---|---|---|---|---|
| 0 | 0 | 1 | 什么也不做 | 1 |
| 1 | 1 | 1 | 什么也不做 | 1 |
| 2 | 2 | 1 | 打开第 1 把锁 | 3 |
| 3 | 3 | 3 | 什么也不做 | 3 |
| 4 | 6 | 3 | 打开第 2 把锁 | 5 |
| 5 | 5 | 5 | 打开第 3 把锁 | 7 |
无法用少于 5 分钟打开所有的锁，所以答案为 5 。
提示：
n == strength.length1 <= n <= 81 <= K <= 101 <= strength[i] <= 106
解题思路
方法一
class Solution:
def findMinimumTime(self, strength: List[int], K: int) -> int:
@cache
def dfs(i: int) -> int:
if i == (1 << len(strength)) - 1:
return 0
cnt = i.bit_count()
x = 1 + cnt * K
ans = inf
for j, s in enumerate(strength):
if i >> j & 1 ^ 1:
ans = min(ans, dfs(i | 1 << j) + (s + x - 1) // x)
return ans
return dfs(0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to model the problem using dynamic programming.
- question_mark
Evaluate the candidate's understanding of bit manipulation and backtracking techniques.
- question_mark
Assess if the candidate can effectively handle permutations and manage time calculations.
常见陷阱
外企场景- error
Overlooking the need for bit masking or efficient state transitions in dynamic programming.
- error
Incorrectly assuming that brute-forcing all permutations is the only solution.
- error
Failing to consider the impact of breaking locks in different orders on the overall time.
进阶变体
外企场景- arrow_right_alt
Try solving with different values for k to see how it impacts the time calculation.
- arrow_right_alt
Handle larger values of n and test the performance of the solution.
- arrow_right_alt
Explore using different optimization techniques, such as greedy methods or additional pruning.