2022-10-30:给你一个长度为 n 的整数数组 rolls 和一个整数 k 。 你扔一个 k 面的骰子 n 次

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 {}

执行结果如下:

在这里插入图片描述
在这里插入图片描述


左神java代码

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!