不可能得到的最短骰子序列
难度:
标签:
题目描述
代码结果
运行时间: 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数组中的值更新为当前子序列的长度ans?这样做的目的是什么?
▷🦆
在遍历结束后直接返回ans作为结果,是否意味着所有可能的子序列长度都已经被检查过?是否有可能存在未被检测到的更短的无法从rolls中得到的子序列?
▷