2022-10-30：给你一个长度为 n 的整数数组 rolls 和一个整数 k 。你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ，其中第 i 次扔得到的数字是 rolls[i]

2022-10-30
北京
本文字数：826 字
阅读完需：约 3 分钟

2022-10-30：给你一个长度为 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。

答案 2022-10-30：

这道题很难想到。一次遍历，一套一套收集。力扣 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 {}