细节满满的一题,组合计算问题再周赛的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) {
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); for (int i = 21; i >= 0; i--) { int t = arr[i] - key; if (t < 0) break; if (t == key) { res += num * (num - 1); } else if (map.containsKey(t)) { res += num * map.get(t); } } } return (int) ((res >> 1) % MOD); } }
|