Force deduction 83 biweekly T4 6131. The shortest dice sequence impossible to get, 303 weeks T4 6127. The number of high-quality pairs

Biweekly 6131. The shortest dice sequence that cannot be obtained

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 .

Tips ：

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/shortest-impossible-sequence-of-rolls
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The result of doing the question

success （ Too slow ）, This question is actually more difficult to think about , The code is very short . These two games found T4 It's getting harder , The range prompt is gone , The scope of biweekly competition is 1e5, But in fact, the answer is 1e5 No problem , It's not an orderly set of priority queues or binary . This is the question O(n) solution .

  Method ： greedy

1. Focus on relative order . Suppose we have a length of 1 Sequence , How can it be extended to a length of 2 Well ？ Find the next set of all the numbers . In this way, the existing numbers can be connected to this group of numbers .

2. For the same group of k A digital , The order is variable , It does not affect the connection between the previous number and any of them , Because we take subsequences , Ensure the last 1_, The next underline corresponds to each value . So the same group k A digital , The order is variable .

3. The timing of the next group . Determined by the last number in this group . For example, this group , The last one is 4. If the next group of numbers appears before it , Cannot pass the last number 4, Form a new link relationship in full order . So we can add one to the full group in order .

4. Finally, add an extra . Because what we have accumulated is the length of the whole row , An additional one is needed to ensure that it cannot be formed

class Solution {
        public int shortestSequence(int[] rolls, int k) {
            int n = rolls.length;
            Set<Integer> set = new HashSet<>();
            int ans = 0;
            for(int roll:rolls){
                set.add(roll);
                if(k==set.size()){
                    ++ans;
                    set.clear();
                }
            }
            return ans+1;
        }
    }

Time complexity ：O(n)

Spatial complexity ：O(k), You need to save a set of data

6127. The number of high-quality pairs

I'll give you a subscript from  0  Starting array of positive integers  nums  And a positive integer  k .

If the following conditions are met , Then number pair  (num1, num2)  yes   High quality pairs  ：

• num1  and  num2  all   In the array  nums  in .
• num1 OR num2  and  num1 AND num2  The median value of the binary representation of is  1  The sum of digits of is greater than or equal to  k , among  OR  It's bit by bit   or   operation , and  AND  It's bit by bit   And   operation .

return   Different   The number of high-quality pairs .

If  a != c  perhaps  b != d , Think  (a, b)  and  (c, d)  Are two different number pairs . for example ,(1, 2)  and  (2, 1)  Different .

Be careful ： If  num1  At least... Appears in the array   once  , Then meet  num1 == num2  The number of  (num1, num2)  It can also be a high-quality number pair .

Example 1：

 Input ：nums = [1,2,3,1], k = 3
 Output ：5
 explain ： There are several high-quality pairs as follows ：
- (3, 3)：(3 AND 3)  and  (3 OR 3)  The binary representation of is equal to  (11) . The value is  1  The sum of digits of is equal to  2 + 2 = 4 , Greater than or equal to  k = 3 .
- (2, 3)  and  (3, 2)： (2 AND 3)  The binary representation of is equal to  (10) ,(2 OR 3)  The binary representation of is equal to  (11) . The value is  1  The sum of digits of is equal to  1 + 2 = 3 .
- (1, 3)  and  (3, 1)： (1 AND 3)  The binary representation of is equal to  (01) ,(1 OR 3)  The binary representation of is equal to  (11) . The value is  1  The sum of digits of is equal to  1 + 2 = 3 .
 So the number of high-quality pairs is  5 .

Example 2：

 Input ：nums = [5,1,1], k = 10
 Output ：0
 explain ： There are no good number pairs in this array .

Tips ：

• 1 <= nums.length <= 1e5
• 1 <= nums[i] <= 1e9
• 1 <= k <= 60

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/number-of-excellent-pairs
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The result of doing the question

success . Think too slowly

Method ： An operation + mathematics

1. The key is （bitcount For binary 1 The number of ） bitcount( And + or )=bitcount( and ), reason ： That's how we find addition ...

2. Count the number of digits of different figures

3. Suffixes and digits

4. Cycle the current number , For example, the current digit value is 3,k=5, Then we need to find the remaining greater than or equal to 2 Of , This is the suffix dp Of 2 The position is the corresponding value , Add up

5. 3 and 4 It can also be converted mathematically . Suppose there is a digit length a and b, a+b>=k, Then multiplying the two can add up to the answer , Because multiplication already contains all cumulative results 【 Small scope , The product cannot exceed , You can use multiplication 】

3+4 programme ：

class Solution {
        public long countExcellentPairs(int[] nums, int k) {
            List<Integer> list = Arrays.stream(nums).boxed().distinct().collect(Collectors.toList());
            int[] times = new int[33];
            for(int num:list){
                int cnt = Integer.bitCount(num);
                times[cnt]++;
            }

            for(int i = 31; i >= 0; i--){
                times[i] += times[i+1];
            }

            long ans = 0L;
            for(int num:list){
                int cnt = Integer.bitCount(num);
                int last = Math.max(k-cnt,0);
                if(last>=times.length) continue;
                ans += times[last];
            }
            return ans;
        }
    }

5 The optimized scheme ：

class Solution {
        public long countExcellentPairs(int[] nums, int k) {
            Set<Integer> set = new HashSet<>();
            final int LEN = 32;
            int[] times = new int[LEN];
            for(int num:nums){
                if(set.add(num)) times[Integer.bitCount(num)]++;
            }

            long ans = 0L;
            for(int i = 0; i < LEN; i++){
                for(int j = 0; j < LEN; j++){
                    if(i+j>=k) ans += (long)times[i]*times[j];
                }
            }
         
            return ans;
        }
    }