题目描述

leetcode2350. 不可能得到的最短骰子序列

给你一个长度为 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.length
  • 1 <= n <= 105
  • 1 <= rolls[i] <= k <= 105

题解——脑筋急转弯——详细解释

不妨考虑一下，在我们已经找到了所有长度为t的所有排列时，怎样才能找到所有长度为t+1的排列
结论是：当且仅当在已经使用过的序列之后，还能找到1~k的所有数，这样就能形成所有排列
比如示例rolls = [4,2,1,2,3,3,2,4,1], k = 4中，就有[4,2,1,3],[3,2,4,1]两个完整的子序列，则3就是最小的找不到的序列
因此题目可以转化为能形成多少个互不交叉的完整的序列(不必有序)
为了尽可能多地找到完整序列，总是应该选择还没搜索过的最小的下标，也就是从上一次使用的最后一个下标之后开始查找，因此下标具有传递性 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int shortestSequence(vector<int>& rolls, int k) {
        int index=0, ans=1;//index是搜索下标,ans记录搜索了多少轮
        while(true) {
        	unordered_set<int>memo;//记录查找的值
            for(; index<rolls.size(); ++index) {
                memo.insert(rolls[index]);//保存新值，自动去重
                if(memo.size() == k)//找满了k个，此轮结束
                {
                    ++index;
                    break;
                }
            }
            if(memo.size() < k)//没找到1~k的所有数，失败！
                return ans;
            ++ans;
        }
    }
};