1711. 大餐计数 {#1711-大餐计数}

细节满满的一题，组合计算问题再周赛的T3与T4经常出，对于常见的组合计算问题应该要掌握。

|------------------------------------------------------------------------------------------------------------------------------------------------------------------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------| | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | class Solution { public int countPairs(int[] deliciousness) { /* HashMap+计数+容斥原理: 1 <= deliciousness.length <= 1e5 0 <= deliciousness[i] <= 2^20 看数据范围只能用O(N)、O(C*N)、O(NlogN)的时间复杂度算法进行求解 1.预处理出2的0~21次幂 2.HashMap统计每个数字出现的个数 3.枚举每个HashMap中的数字进行计数，以key为锚点，枚举所有的可能的二次幂并球出目标匹配数字； 之后先统计相同数字组成的对，再统计不同数字组成的对进行相加 4.最后记得对统计的数字/2 坑点: 1.2^0=1也是2的次幂 2.相同数字的计算方法为:num*(num-1)/2，其中num为数字个数 3.相同数字的计算方法为:cnt[t]*cnt[key]/2，其中t为要匹配的目标数字，key为当前数字 可以将2与3统一起来最后一起除2 4.这里long类型在统计过程中可以不进行MOD(<1e10)，最后才取余即可 最好先进行除2操作最后再取余，如果顺序反了最后取余再除2结果不对! 还有最后取余的一定一定要把MOD括起来，否则就会将res先转换为int了!!!! 5.枚举二次幂可以倒序提前退出 */ // 美味程度之和上限为2^21，预处理出2^0~2^21的幂 int cur = 1, MOD = (int) 1e9 + 7; int[] arr = new int[22]; for (int i = 0; i <= 21; i++) { arr[i] = cur; cur *= 2; } // 统计数字对应个数 HashMap<Integer, Integer> map = new HashMap<>(); for (int num : deliciousness) { map.put(num, map.getOrDefault(num, 0) + 1); } long res = 0L; // 寻找每个数字缺失的另一半 for (int key : map.keySet()) { long num = map.get(key); // 该数字key的数目 for (int i = 21; i >= 0; i--) { int t = arr[i] - key; // 要找的目标数字 if (t < 0) break; // 从大的开始枚举，如果当前已经小于0，那么前面的必定小于0，提前break // 1.先统计相同数字组成的:组合种数=cnt[key]*(cnt[key]-1)/2 if (t == key) { res += num * (num - 1); } else if (map.containsKey(t)) { // 2.再统计不同数字之间的cnt[t]*cnt[key]/2 res += num * map.get(t); } } } // 最后统计重了一倍应该除2 return (int) ((res >> 1) % MOD); } } |