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

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

做题结果

成功（太慢），这题其实就是比较难想，代码是很短的。这两场比赛发现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 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)，需要保存一组数据

做题结果

成功。同样想的太慢

方法：位运算+数学

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。