LeetCode 题解工作台
不可能得到的最短骰子序列
给你一个长度为 n 的整数数组 rolls 和一个整数 k 。你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ，其中第 i 次扔得到的数字是 rolls[i] 。 请你返回 无法 从 rolls 中得到的 最短 骰子子序列的长度。 扔一个 k 面的骰子 len 次得到的是一个长度为 …
3
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
时间复杂度 。 class Solution:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个长度为 n 的整数数组 rolls 和一个整数 k 。你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ，其中第 i 次扔得到的数字是 rolls[i] 。
请你返回 无法 从 rolls 中得到的 最短 骰子子序列的长度。
扔一个 k 面的骰子 len 次得到的是一个长度为 len 的 骰子子序列 。
注意 ，子序列只需要保持在原数组中的顺序，不需要连续。
示例 1：
输入：rolls = [4,2,1,2,3,3,2,4,1], k = 4 输出：3 解释：所有长度为 1 的骰子子序列 [1] ，[2] ，[3] ，[4] 都可以从原数组中得到。 所有长度为 2 的骰子子序列 [1, 1] ，[1, 2] ，... ，[4, 4] 都可以从原数组中得到。 子序列 [1, 4, 2] 无法从原数组中得到，所以我们返回 3 。 还有别的子序列也无法从原数组中得到。
示例 2：
输入：rolls = [1,1,2,2], k = 2 输出：2 解释：所有长度为 1 的子序列 [1] ，[2] 都可以从原数组中得到。 子序列 [2, 1] 无法从原数组中得到，所以我们返回 2 。 还有别的子序列也无法从原数组中得到，但 [2, 1] 是最短的子序列。
示例 3：
输入：rolls = [1,1,3,2,2,2,3,3], k = 4 输出：1 解释：子序列 [4] 无法从原数组中得到，所以我们返回 1 。 还有别的子序列也无法从原数组中得到，但 [4] 是最短的子序列。
提示：
n == rolls.length1 <= n <= 1051 <= rolls[i] <= k <= 105
解题思路
方法一：脑筋急转弯
时间复杂度 。
class Solution:
def shortestSequence(self, rolls: List[int], k: int) -> int:
ans = 1
s = set()
for v in rolls:
s.add(v)
if len(s) == k:
ans += 1
s.clear()
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Understanding of efficient array scanning and hash table utilization.
- question_mark
Ability to optimize solutions using greedy algorithms.
- question_mark
Clear explanation of time and space complexities in terms of problem constraints.
常见陷阱
外企场景- error
Overlooking the importance of using a hash table for efficient lookup.
- error
Incorrectly assuming that all subsequences up to a certain length can always be formed.
- error
Failing to optimize the solution for large input sizes, leading to excessive time or space complexity.
进阶变体
外企场景- arrow_right_alt
Change the size of the dice (k) to test scalability of the solution.
- arrow_right_alt
Introduce constraints on the number of rolls that can be made, impacting the solution's efficiency.
- arrow_right_alt
Consider adding additional conditions, like limiting the range of possible subsequences.