Leetcode-6131: the shortest dice sequence impossible to get

subject

Topic linking
Give you a length of n Array of integers for rolls And an integer k . You throw one k Face dice n Time , Each side of the dice is 1 To k , Among them the first i The number of times thrown is rolls[i] .

Please return unable from rolls Obtained in The shortest The length of the dice sequence .

Throw one k Face dice len The result is a length of len Of Dice sequence .

Be careful , Subsequences only need to maintain the order in the original array , There is no need for continuity .

Example 1：

 Input ：rolls = [4,2,1,2,3,3,2,4,1], k = 4
 Output ：3
 explain ： All lengths are  1  Dice sequence  [1] ,[2] ,[3] ,[4]  Can be obtained from the original array .
 All lengths are  2  Dice sequence  [1, 1] ,[1, 2] ,... ,[4, 4]  Can be obtained from the original array .
 Subsequence  [1, 4, 2]  Cannot get from the original array , So we go back to  3 .
 There are other subsequences that cannot be obtained from the original array .

Example 2：

 Input ：rolls = [1,1,2,2], k = 2
 Output ：2
 explain ： All lengths are  1  The subsequence  [1] ,[2]  Can be obtained from the original array .
 Subsequence  [2, 1]  Cannot get from the original array , So we go back to  2 .
 There are other subsequences that cannot be obtained from the original array , but  [2, 1]  Is the shortest subsequence .

Example 3：

 Input ：rolls = [1,1,3,2,2,2,3,3], k = 4
 Output ：1
 explain ： Subsequence  [4]  Cannot get from the original array , So we go back to  1 .
 There are other subsequences that cannot be obtained from the original array , but  [4]  Is the shortest subsequence .

Problem solving

Method 1 ： brain twists

These numbers can be divided into A few paragraphs , Each paragraph contains 1 To K Value , The last value of each paragraph , It must only appear once in the current paragraph .

So the final result , Is the number of segments that can be divided +1

class Solution {
    
public:
    int shortestSequence(vector<int>& rolls, int k) {
    
        unordered_set<int> set;
        int res=1;
        for(int roll:rolls){
    
            if(set.count(roll)==0){
    
                set.insert(roll);
                if(set.size()==k){
    
                    res++;
                    set.clear();
                }
            }
        }
        return res;
    }
};