代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个长度为 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.length
1 <= n <= 105
1 <= rolls[i] <= k <= 105
方法一:脑筋急转弯
时间复杂度 $O(n)$。
class Solution:
def shortestSequence(self, rolls: List[int], k: int) -> int:
ans = 1
s = set()
for v in rolls:
s.add(v)
if len(s) == k:
ans += 1
s.clear()
return ans
class Solution {
public int shortestSequence(int[] rolls, int k) {
Set<Integer> s = new HashSet<>();
int ans = 1;
for (int v : rolls) {
s.add(v);
if (s.size() == k) {
s.clear();
++ans;
}
}
return ans;
}
}
class Solution {
public:
int shortestSequence(vector<int>& rolls, int k) {
unordered_set<int> s;
int ans = 1;
for (int v : rolls) {
s.insert(v);
if (s.size() == k) {
s.clear();
++ans;
}
}
return ans;
}
};
func shortestSequence(rolls []int, k int) int {
s := map[int]bool{}
ans := 1
for _, v := range rolls {
s[v] = true
if len(s) == k {
ans++
s = map[int]bool{}
}
}
return ans
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。