题目

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

You are given an integer array rolls of length n and an integer k. You roll a k sided dice numbered from 1 to k, n times, where the result of the ith roll is rolls[i].

Return the length of the shortest sequence of rolls that cannot be taken from rolls.

A sequence of rolls of length len is the result of rolling a k sided dice len times.

Note that the sequence taken does not have to be consecutive as long as it is in order.

Example 1:

Input: rolls = [4,2,1,2,3,3,2,4,1], k = 4
Output: 3
Explanation: Every sequence of rolls of length 1, [1], [2], [3], [4], can be taken from rolls.
Every sequence of rolls of length 2, [1, 1], [1, 2], ..., [4, 4], can be taken from rolls.
The sequence [1, 4, 2] cannot be taken from rolls, so we return 3.
Note that there are other sequences that cannot be taken from rolls.

Example 2:

Input: rolls = [1,1,2,2], k = 2
Output: 2
Explanation: Every sequence of rolls of length 1, [1], [2], can be taken from rolls.
The sequence [2, 1] cannot be taken from rolls, so we return 2.
Note that there are other sequences that cannot be taken from rolls but [2, 1] is the shortest.

Example 3:

Input: rolls = [1,1,3,2,2,2,3,3], k = 4
Output: 1
Explanation: The sequence [4] cannot be taken from rolls, so we return 1.
Note that there are other sequences that cannot be taken from rolls but [4] is the shortest.

Constraints:

• n == rolls.length
• 1 <= n <= 105
• 1 <= rolls[i] <= k <= 105

思路

题目大意，k面的骰子，给定一个序列rolls，求rolls中无法得到的最短的骰子子序列长度。

注意，子序列在rolls中不一定连续。

先来观察一下子序列的性质。

k=3时，长度为1的子序列：[1], [2], [3]

长度为2的子序列：[1,1][2,1][3,1][1,2][2,2][3,2][1,3][2,3][3,3]

得到了m位的子序列，只要在m位后追加1~k，就可以得到m+1位子序列。

可以看出，如果roll[:i]中可以得到所有m位的子序列，只要在roll[:i]后面出现过1~k，就可以保证，一定可以得到m+1位的子序列。

那么我们的思路就很清晰了——按顺序扫描rolls，每遇到一轮完整的1~k，子序列长度+1，直到rolls终止即可。

代码

直接上代码

class Solution(object):
    def shortestSequence(self, rolls, k):
        """
        :type rolls: List[int]
        :type k: int
        :rtype: int
        """
        ret = 1
        p = 0
        s = set()
        while p < len(rolls):
            s.add(rolls[p])
            if len(s) == k:
                s = set()
                ret += 1
            
            p += 1
            
        return ret

AC，收工！

——此处是内容的分割线——

除非注明，否则均为广陌原创文章，转载必须以链接形式标明本文链接

本文链接：https://www.utopiafar.com/2022/07/25/leetcode-2350-shortest-impossible-sequence-of-rolls/

码字不易，如果觉得内容有帮助，欢迎留言or点赞！