class Solution {
public:
int shortestSequence(vector<int>& rolls, int k) {
}
};
2350. 不可能得到的最短骰子序列
给你一个长度为 n 的整数数组 rolls 和一个整数 k 。你扔一个 k 面的骰子 n 次，骰子的每个面分别是 1 到 k ，其中第 i 次扔得到的数字是 rolls[i] 。
请你返回 无法 从 rolls 中得到的 最短 骰子子序列的长度。
扔一个 k 面的骰子 len 次得到的是一个长度为 len 的 骰子子序列 。
注意 ，子序列只需要保持在原数组中的顺序，不需要连续。
示例 1：
输入：rolls = [4,2,1,2,3,3,2,4,1], k = 4 输出：3 解释：所有长度为 1 的骰子子序列 [1] ，[2] ，[3] ，[4] 都可以从原数组中得到。 所有长度为 2 的骰子子序列 [1, 1] ，[1, 2] ，... ，[4, 4] 都可以从原数组中得到。 子序列 [1, 4, 2] 无法从原数组中得到，所以我们返回 3 。 还有别的子序列也无法从原数组中得到。
示例 2：
输入：rolls = [1,1,2,2], k = 2 输出：2 解释：所有长度为 1 的子序列 [1] ，[2] 都可以从原数组中得到。 子序列 [2, 1] 无法从原数组中得到，所以我们返回 2 。 还有别的子序列也无法从原数组中得到，但 [2, 1] 是最短的子序列。
示例 3：
输入：rolls = [1,1,3,2,2,2,3,3], k = 4 输出：1 解释：子序列 [4] 无法从原数组中得到，所以我们返回 1 。 还有别的子序列也无法从原数组中得到，但 [4] 是最短的子序列。
提示：
n == rolls.length1 <= n <= 1051 <= rolls[i] <= k <= 105原站题解
cpp 解法, 执行用时: 196 ms, 内存消耗: 105.8 MB, 提交时间: 2023-06-01 09:50:08
class Solution {
public:
int shortestSequence(vector<int>& rolls, int k) {
int ans=0;
unordered_set<int> temp;
for(int i=0;i<rolls.size();i++){
temp.insert(rolls[i]);
if(temp.size()==k){
ans++;
temp.clear();
}
}
return ans+1;
}
};
golang 解法, 执行用时: 100 ms, 内存消耗: 9.1 MB, 提交时间: 2023-06-01 09:48:39
func shortestSequence(rolls []int, k int) int {
mark := make([]int, k+1) // mark[v] 标记 v 属于哪个子段
ans, left := 1, k
for _, v := range rolls {
if mark[v] < ans {
mark[v] = ans
if left--; left == 0 {
left = k
ans++
}
}
}
return ans
}
java 解法, 执行用时: 3 ms, 内存消耗: 54.7 MB, 提交时间: 2023-06-01 09:48:02
class Solution {
public int shortestSequence(int[] rolls, int k) {
var mark = new int[k + 1]; // mark[v] 标记 v 属于哪个子段
int ans = 1, left = k;
for (var v : rolls)
if (mark[v] < ans) {
mark[v] = ans;
if (--left == 0) {
left = k;
++ans;
}
}
return ans;
}
}
python3 解法, 执行用时: 108 ms, 内存消耗: 24.5 MB, 提交时间: 2023-06-01 09:47:51
class Solution:
def shortestSequence(self, rolls: List[int], k: int) -> int:
mark = [0] * (k + 1) # mark[v] 标记 v 属于哪个子段
ans, left = 1, k
for v in rolls:
if mark[v] < ans:
mark[v] = ans
left -= 1
if left == 0:
left = k
ans += 1
return ans