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

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

给你一个长度为 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 <= 10^5
1 <= rolls[i] <= k <= 10^5

思路分析

今天的这道题目是一道思维题，乍一看没有思路就会感觉是一道很困难的题目，但当你看透了题目的本质之后，你就会恍然大悟。

从题目中我们可以知道这里的一枚骰子有k个面，所以其结果可能为1~k，如果取子序列长度为1的话，即每一个面的结果都应该至少出现一次，最理想的结果如上图，每个结果都出现一次。

接下来我们再看一下长度为2的情况，其实和长度为1的子序列是类似的，每一个位置上的取值都有1~k，看到这里是不是有了思路了？

所以在原序列rolls中取子序列时，我们可以这样做，如上图，我们看将rolls序列划分成多段包含k种结果的数组段，这样我们在每一段中都可以取到1~k的值，所以我们只需要统计数组可以划分的段数，即可得出可能得到的最长骰子序列，反之也即得到了可能得到的最短骰子序列

AC代码

/**
 * @param {number[]} rolls
 * @param {number} k
 * @return {number}
 */
 var shortestSequence = function(rolls, k) {
 let res = 1;
 let set = new Set();
 for(let i = 0; i < rolls.length; i++){
    set.add(rolls[i]); 
    if(set.size == k) {
        res++;
        set = new Set();
    } 
 }
 return res;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。