给你一个长度为 n 的整数数组 rolls 和一个整数 k 。
你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ，
其中第 i 次扔得到的数字是 rolls[i] 。
请你返回 无法 从 rolls 中得到的 最短 骰子子序列的长度。
扔一个 k 面的骰子 len 次得到的是一个长度为 len 的 骰子子序列 。
注意 ，子序列只需要保持在原数组中的顺序，不需要连续。
输入：rolls = [4,2,1,2,3,3,2,4,1], k = 4。
输出：3。
这道题很难想到。一次遍历，一套一套收集。
力扣2350。力扣上测试了好几门语言。这次java的运行速度最高，比rust都强了不少。c++表现不好，不见运行速度低，而且内存占用大。rust内存占用最小，go语言次之。
时间复杂度：O(n+k)。
空间复杂度：O(k)。
代码用rust编写。代码如下：
use std::iter::repeat;
impl Solution {
// 所有数字1~k
pub fn shortest_sequence(rolls: Vec<i32>, k: i32) -> i32 {
// 1~k上，某个数字是否收集到了！
// set[i] == true
// set[i] == false
// boolean[] set = new boolean[k + 1];
let mut set: Vec<bool> = repeat(false).take((k + 1) as usize).collect();
// 当前这一套，收集了几个数字了？
let mut size = 0;
let mut ans = 0;
for num in rolls.iter() {
if !set[*num as usize] {
set[*num as usize] = true;
size += 1;
}
if size == k {
ans += 1;
set = repeat(false).take((k + 1) as usize).collect();
size = 0;
}
}
return ans + 1;
}
}
fn main() {
let rolls = vec![4, 2, 1, 2, 3, 3, 2, 4, 1];
let k = 4;
let ans = Solution::shortest_sequence(rolls, k);
println!("ans = {:?}", ans);
}
struct Solution {}执行结果如下：
![2022-10-30：给你一个长度为 n 的整数数组 rolls 和一个整数 k 。 你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ， 其中第 i 次扔得到的数字是 rolls[i]](https://ctyun-collect-0531.gdoss.xstore.ctyun.cn/files/2023/05/23/e468ab92c0bd4e8490dcbd3c2c31694c.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/resize,m_fixed,w_1184 "2022-10-30：给你一个长度为 n 的整数数组 rolls 和一个整数 k 。 你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ， 其中第 i 次扔得到的数字是 rolls[i]")
![2022-10-30：给你一个长度为 n 的整数数组 rolls 和一个整数 k 。 你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ， 其中第 i 次扔得到的数字是 rolls[i]](https://ctyun-collect-0531.gdoss.xstore.ctyun.cn/files/2023/05/23/be1cdf8ff6304275afc3ee6fef5e8440.png?x-oss-process=image/watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=/resize,m_fixed,w_1184 "2022-10-30：给你一个长度为 n 的整数数组 rolls 和一个整数 k 。 你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ， 其中第 i 次扔得到的数字是 rolls[i]")
