leetcode
leetcode 2051 ~ 2100
不可能得到的最短骰子序列

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

难度:

标签:

题目描述

代码结果

运行时间: 66 ms, 内存: 23.9 MB


/*
 * 思路:
 * 1. 使用Stream API处理数组。
 * 2. 遍历rolls数组并用一个Set来存储当前已经出现的数字。
 * 3. 当Set的大小等于k时,表示1到k的所有数字已经出现,重置Set并增加计数器。
 * 4. 返回计数器+1,表示无法得到的子序列长度。
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    public int shortestImpossibleSubsequence(int[] rolls, int k) {
        Set<Integer> set = new HashSet<>();
        AtomicInteger count = new AtomicInteger(0);
        Arrays.stream(rolls).forEach(roll -> {
            set.add(roll);
            if (set.size() == k) {
                count.getAndIncrement();
                set.clear();
            }
        });
        return count.get() + 1;
    }
}

解释

方法:

这个题解使用了一种贪心的策略来找到无法从rolls中得到的最短骰子子序列的长度。它维护了一个数组mask,用于记录每个数字最后一次出现在哪个子序列中。变量ans表示当前正在构建的子序列的长度,而left表示在当前子序列中还没有出现的数字的个数。遍历rolls数组,如果当前数字roll在mask中的值小于ans,说明它在当前子序列中还没有出现过,将mask[roll]更新为ans,并将left减一。如果left变为0,说明当前子序列中已经包含了所有1到k的数字,因此需要开始构建新的子序列,将ans加一并重置left为k。

时间复杂度:

O(n)

空间复杂度:

O(k)

代码细节讲解

🦆
在这个算法中,mask数组的具体角色和功能是什么?为何选择使用mask数组来记录数字的出现情况?
在这个算法中,mask数组的角色是用来记录每个数字最后一次出现在哪个子序列中。具体来说,mask的索引表示骰子的面数(例如,索引1代表骰子面为1),而该索引的值表示该面数最后出现在第几个子序列中。选择使用mask数组的原因是为了高效地跟踪和更新每个数字的出现状态。通过检查一个数字的mask值与当前子序列的长度的比较,我们可以快速判断出一个数字是否已经在当前构建的子序列中出现过,从而决定是否需要开始一个新的子序列。这种方法避免了使用复杂的数据结构,简化了实现,并提高了算法的执行效率。
🦆
为什么在发现一个数字第一次出现时,要将其在mask数组中的值更新为当前子序列的长度ans?这样做的目的是什么?
当一个数字第一次在当前子序列中出现时,将其在mask数组中的值更新为当前子序列的长度ans,是为了标记这个数字已经被包括在当前子序列中。这样做的目的是为了在后续的遍历中判断一个数字是否已经在这个子序列中出现过。如果一个数字的mask值小于当前的子序列长度ans,说明这个数字在当前子序列中尚未出现。这样可以确保每次当所有可能的数字都至少出现一次时,我们才开始新的子序列,确保子序列的构建是正确和完整的。
🦆
在遍历结束后直接返回ans作为结果,是否意味着所有可能的子序列长度都已经被检查过?是否有可能存在未被检测到的更短的无法从rolls中得到的子序列?
在遍历结束后直接返回ans作为结果,确实意味着根据当前算法逻辑,所有可能的子序列长度都已经被检查过。算法通过不断更新子序列长度来确保每种数字的出现至少被记录了一次,然后开始一个新的子序列。这种方法保证了只要存在一个无法从rolls中完整构建的子序列,它就会在某个点被识别,因此返回的ans代表的是无法从rolls中得到的最短子序列的长度。因此,根据这种算法策略,不存在未被检测到的更短的无法从rolls中得到的子序列。

相关问题