力扣 83双周赛T4 6131.不可能得到的最短骰子序列、303 周赛T4 6127.优质数对的数目

双周赛 6131.不可能得到的最短骰子序列

给你一个长度为 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 <= 1e5
• 1 <= rolls[i] <= k <= 1e5

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shortest-impossible-sequence-of-rolls
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功（太慢），这题其实就是比较难想，代码是很短的。这两场比赛发现T4变难了，范围提示没有了，双周赛周赛范围都是1e5，但实际上答案和1e5没关系，不是走优先队列有序集合或者是二分的。这题是O(n)解法。

 方法：贪心

1. 关注相对顺序。假设我们有长度为1的序列，如何能延长到长度为2呢？找到下一组全部的数字。这样已经有的数字就可以都连到这组数字。

2. 对于同一组的 k 个数字，顺序是可变的，不影响上一个数字和他们其中的任意一个相连，因为我们取的是子序列，保证上一个 1_,后面这个下划线对应可以填每个值就可以了。所以同组的 k 个数字，顺序是可变的。

3. 下一组出现的时机。由本组的最后一个出现数字决定。比如本组，最后一个出现的是4.下一组出现的数字在它之前的话，则无法通过最后一个数字4，形成新的全排顺序的链接关系。所以我们直接按顺序数满一组加一就可以。

4. 最后要额外加一个。因为我们累计的是可以达成全排的长度，需要额外加一个才能保证无法形成

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;
        }
    }

时间复杂度：O(n)

空间复杂度：O(k)，需要保存一组数据

6127. 优质数对的数目

给你一个下标从 0 开始的正整数数组 nums 和一个正整数 k 。

如果满足下述条件，则数对 (num1, num2) 是 优质数对 ：

• num1 和 num2 都 在数组 nums 中存在。
• num1 OR num2 和 num1 AND num2 的二进制表示中值为 1 的位数之和大于等于 k ，其中 OR 是按位 或 操作，而 AND 是按位 与 操作。

返回 不同 优质数对的数目。

如果 a != c 或者 b != d ，则认为 (a, b) 和 (c, d) 是不同的两个数对。例如，(1, 2) 和 (2, 1) 不同。

注意：如果 num1 在数组中至少出现 一次 ，则满足 num1 == num2 的数对 (num1, num2) 也可以是优质数对。

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：5
解释：有如下几个优质数对：
- (3, 3)：(3 AND 3) 和 (3 OR 3) 的二进制表示都等于 (11) 。值为 1 的位数和等于 2 + 2 = 4 ，大于等于 k = 3 。
- (2, 3) 和 (3, 2)： (2 AND 3) 的二进制表示等于 (10) ，(2 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。
- (1, 3) 和 (3, 1)： (1 AND 3) 的二进制表示等于 (01) ，(1 OR 3) 的二进制表示等于 (11) 。值为 1 的位数和等于 1 + 2 = 3 。
所以优质数对的数目是 5 。

示例 2：

输入：nums = [5,1,1], k = 10
输出：0
解释：该数组中不存在优质数对。

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-excellent-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功。同样想的太慢

方法：位运算+数学

1. 关键就是（bitcount代表二进制1的个数） bitcount(与+或)=bitcount(和),原因：加法就是这么求的。。。

2. 统计不同数字的数位个数

3. 后缀和数位

4. 循环当前数字，比如当前数位值是 3，k=5,那么我们需要找到剩下大于等于2的，这是后缀dp的2位置就是对应的值，进行累加即可

5. 3和4也可通过数学方式进行转换。假设有数位长度 a 和 b, a+b>=k,那么两者相乘可以累计到答案，因为相乘已经包含了所有累计的结果【范围小，乘积超不了，可以用乘法】

3+4方案：

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优化后方案：

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;
        }
    }