Hard

题目描述

给你一个长度为 n 的整数数组 rolls 和一个整数 k。你掷一个有 k 面的骰子（编号从 1 到 k）n 次，其中第 i 次掷骰子的结果是 rolls[i]。

返回最短的掷骰子序列的长度，使得 rolls 中不存在这样的子序列。

长度为 len 的掷骰子序列是掷 k 面骰子 len 次的结果。

示例 1：

输入：rolls = [4,2,1,2,3,3,2,4,1], k = 4
输出：3
解释：每个长度为 1 的序列，[1], [2], [3], [4]，都可以从 rolls 中取得。
每个长度为 2 的序列，[1, 1], [1, 2], ..., [4, 4]，都可以从 rolls 中取得。
序列 [1, 4, 2] 无法从 rolls 中取得，所以我们返回 3。
注意还有其他序列无法从 rolls 中取得。

示例 2：

输入：rolls = [1,1,2,2], k = 2
输出：2
解释：每个长度为 1 的序列，[1], [2]，都可以从 rolls 中取得。
序列 [2, 1] 无法从 rolls 中取得，所以我们返回 2。
注意还有其他序列无法从 rolls 中取得，但 [2, 1] 是最短的。

示例 3：

输入：rolls = [1,1,3,2,2,2,3,3], k = 4
输出：1
解释：序列 [4] 无法从 rolls 中取得，所以我们返回 1。
注意还有其他序列无法从 rolls 中取得，但 [4] 是最短的。

提示：

  • n == rolls.length
  • 1 <= n <= 10^5
  • 1 <= rolls[i] <= k <= 10^5

解题思路

这是一道典型的贪心算法题。关键思路是：如果所有长度为 len 的序列都可以在 rolls 中找到，那么所有长度为 len-1 的序列也一定可以找到。

我们需要找到最小的长度 len，使得存在某个长度为 len 的序列无法在 rolls 中找到。

核心观察：

  • 长度为 1 的序列有 k 个：[1], [2], …, [k]
  • 长度为 2 的序列有 k² 个：[1,1], [1,2], …, [k,k]
  • 长度为 len 的序列有 k^len 个

贪心策略： 我们从左到右遍历 rolls，对于每个长度 len：

  1. 维护一个集合，记录在当前位置之后还需要哪些数字来完成长度为 len 的所有可能序列
  2. 当集合中包含所有 1 到 k 的数字时，说明我们可以构造出所有长度为 len 的序列
  3. 清空集合，开始寻找长度为 len+1 的序列

当我们无法在剩余的 rolls 中找到足够的数字来构成某个长度的所有序列时，就找到了答案。

算法流程：

  1. 初始化 length = 1，表示当前要构造的序列长度
  2. 使用集合 needed 记录当前长度下还需要的数字
  3. 遍历 rolls，每遇到一个数字就从 needed 中移除
  4. 当 needed 为空时，说明当前长度的所有序列都能构造，length++，重新初始化 needed
  5. 如果遍历完成后 needed 仍不为空，返回当前 length

代码实现

class Solution {
public:
    int shortestSequence(vector<int>& rolls, int k) {
        int length = 1;
        unordered_set<int> needed;
        
        // 初始化需要的数字集合
        for (int i = 1; i <= k; i++) {
            needed.insert(i);
        }
        
        for (int roll : rolls) {
            needed.erase(roll);
            
            // 如果当前长度的所有序列都能构造出来
            if (needed.empty()) {
                length++;
                // 重新初始化下一个长度的需求
                for (int i = 1; i <= k; i++) {
                    needed.insert(i);
                }
            }
        }
        
        return length;
    }
};

class Solution:
    def shortestSequence(self, rolls: List[int], k: int) -> int:
        length = 1
        needed = set(range(1, k + 1))
        
        for roll in rolls:
            needed.discard(roll)
            
            # 如果当前长度的所有序列都能构造出来
            if not needed:
                length += 1
                # 重新初始化下一个长度的需求
                needed = set(range(1, k + 1))
        
        return length

public class Solution {
    public int ShortestSequence(int[] rolls, int k) {
        int length = 1;
        HashSet<int> needed = new HashSet<int>();
        
        // 初始化需要的数字集合
        for (int i = 1; i <= k; i++) {
            needed.Add(i);
        }
        
        foreach (int roll in rolls) {
            needed.Remove(roll);
            
            // 如果当前长度的所有序列都能构造出来
            if (needed.Count == 0) {
                length++;
                // 重新初始化下一个长度的需求
                for (int i = 1; i <= k; i++) {
                    needed.Add(i);
                }
            }
        }
        
        return length;
    }
}

var shortestSequence = function(rolls, k) {
    let seen = new Set();
    let length = 1;
    
    for (let roll of rolls) {
        seen.add(roll);
        if (seen.size === k) {
            length++;
            seen.clear();
        }
    }
    
    return length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n)
空间复杂度O(k)

说明：

  • 时间复杂度：我们只需要遍历一次 rolls 数组，每次操作（插入、删除）在哈希集合中都是 O(1)
  • 空间复杂度：我们使用一个大小最多为 k 的哈希集合来存储需要的数字