260. 只出現(xiàn)一次的數(shù)字 III?（異或）🐂

https://leetcode.cn/problems/single-number-iii/description/?envType=daily-question&envId=2023-10-16

提示：
2 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
除兩個(gè)只出現(xiàn)一次的整數(shù)外，nums 中的其他數(shù)字都出現(xiàn)兩次

---

類(lèi)似分治的思想。
先將數(shù)組全部異或，得出的結(jié)果是兩個(gè)只出現(xiàn)一次數(shù)字的異或結(jié)果。
其中一定有1，因?yàn)檫@兩個(gè)數(shù)字不同。
取出其最低位的1作為判斷標(biāo)準(zhǔn)對(duì)原數(shù)組分組（實(shí)際上任意位的1都可以），分成的兩組分別包括這兩個(gè)只出現(xiàn)一次的數(shù)字。
這樣就把問(wèn)題轉(zhuǎn)換成了兩個(gè) 136. 只出現(xiàn)一次的數(shù)字

class Solution {public int[] singleNumber(int[] nums) {int xor = 0;for (int num: nums) xor ^= num;int mask = xor & (-xor);    // 獲取最低位的1int[] ans = new int[2];for (int num: nums) {if ((num & mask) == 0) ans[0] ^= num;else ans[1] ^= num;}return ans;}
}

2652. 倍數(shù)求和

https://leetcode.cn/problems/sum-multiples/description/?envType=daily-question&envId=2023-10-17

提示：
1 <= n <= 10^3

解法1——枚舉模擬

class Solution {public int sumOfMultiples(int n) {int ans = 0;for (int i = 1; i <= n; ++i) {if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) ans += i;}return ans;}
}

解法2——$O(1)$容斥原理

class Solution {int n;public int sumOfMultiples(int n) {this.n = n;return s(3) + s(5) + s(7) - s(15) - s(21) - s(35) + s(105);}// 計(jì)算從x~(n/x)x，共n/x項(xiàng)public int s(int x) {return n / x * (x + n / x * x) / 2;}
}

相似題目——1201. 丑數(shù) III（二分查找+容斥原理）

https://leetcode.cn/problems/ugly-number-iii/description/

提示：
1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
本題結(jié)果在 [1, 2 * 10^9] 的范圍內(nèi)

為什么會(huì)想到二分？
因?yàn)橹苯忧蟠鸢覆缓们?#xff0c;但是我們可以判斷1~x的范圍內(nèi)是否有n個(gè)丑數(shù)。

class Solution {public int nthUglyNumber(int n, int a, int b, int c) {long x = lcm(a, b), y = lcm(b, c), z = lcm(a, c), q = lcm(x, y);long l = 1, r = (long)2e9;while (l < r) {long mid = l + r >> 1;long aa = mid / a, bb = mid / b, cc = mid / c, xx = mid / x, yy = mid / y, zz = mid / z, qq = mid / q;long s = aa + bb + cc - xx - yy - zz + qq;if (s < n) l = mid + 1;else r = mid;}return (int)l;}public long gcd(long a, long b) {return b == 0? a: gcd(b, a % b);}public long lcm(long a, long b) {return a / gcd(a, b) * b;}
}

2530. 執(zhí)行 K 次操作后的最大分?jǐn)?shù)

https://leetcode.cn/problems/maximal-score-after-applying-k-operations/description/?envType=daily-question&envId=2023-10-18

提示：

1 <= nums.length, k <= 10^5
1 <= nums[i] <= 10^9

解法1——貪心+優(yōu)先隊(duì)列

每次增加最大的數(shù)字即可。

class Solution {public long maxKelements(int[] nums, int k) {long ans = 0;PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);for (int num: nums) pq.offer(num);for (int i = 0; i < k; ++i) {int c = pq.poll();ans += c;pq.offer((c + 2) / 3);}return ans;}
}

解法2——$O(1)$空間原地堆化

https://leetcode.cn/problems/maximal-score-after-applying-k-operations/solutions/2487446/o1-kong-jian-zuo-fa-pythonjavacgojsrust-ztx6f/?envType=daily-question&envId=2023-10-18

原地堆化，把 nums 數(shù)組當(dāng)成一個(gè)堆。
從 h.length / 2 - 1 開(kāi)始倒序下沉。

class Solution {public long maxKelements(int[] nums, int k) {heapify(nums);long ans = 0;while (k-- > 0) {ans += nums[0];nums[0] = (nums[0] + 2) / 3;sink(nums, 0);      // 下沉}return ans;}// 保證h[0]>=max(h[2*i+1],h[2*i+2])public void heapify(int[] h) {for (int i = h.length / 2 - 1; i >= 0; --i) {sink(h, i);}}public void sink(int[] h, int i) {int n = h.length;while (2 * i + 1 < n) {// 挑選左右兒子中更大的和i交換int j = 2 * i + 1;          // i的左兒子if (j + 1 < n && h[j + 1] > h[j]) j++;if (h[j] <= h[i]) break;    // 停止下沉swap(h, i, j);i = j;}}public void swap(int[] h, int i, int j) {int tmp = h[i];h[i] = h[j];h[j] = tmp;}
}

1726. 同積元組（哈希表+組合數(shù)學(xué)）

https://leetcode.cn/problems/tuple-with-same-product/description/

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 10^4
nums 中的所有元素 互不相同

計(jì)算出數(shù)組中所有兩兩組合的乘積的各個(gè)數(shù)量。
那么各個(gè)成績(jī)的組合數(shù)就是$C_x^2=x?(x?1)$，即任選兩組。每種組合4個(gè)數(shù)字可以任意排位置，最后結(jié)果*4。

class Solution {public int tupleSameProduct(int[] nums) {int n = nums.length, ans = 0;Map<Integer, Integer> cnt = new HashMap<>();for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {cnt.merge(nums[i] * nums[j], 1, Integer::sum);}}for (int v: cnt.values()) {if (v > 1) ans += v * (v - 1);}return ans * 4;}
}

2525. 根據(jù)規(guī)則將箱子分類(lèi)（按題意模擬，分類(lèi)討論）

https://leetcode.cn/problems/categorize-box-according-to-criteria/description/?envType=daily-question&envId=2023-10-20

提示：

1 <= length, width, height <= 10^5
1 <= mass <= 10^3

class Solution {public String categorizeBox(int length, int width, int height, int mass) {boolean bulky = false, heavy = false;if (length >= 10000 || width >= 10000 || height >= 10000 || mass >= 10000 || (long)length * width * height >= 1000000000) bulky = true;if (mass >= 100) heavy = true; if (bulky && heavy) return "Both";if (!bulky && !heavy) return "Neither";if (bulky) return "Bulky";return "Heavy";}
}

2316. 統(tǒng)計(jì)無(wú)向圖中無(wú)法互相到達(dá)點(diǎn)對(duì)數(shù)

https://leetcode.cn/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/description/?envType=daily-question&envId=2023-10-21

提示：

1 <= n <= 10^5
0 <= edges.length <= 2 * 10^5
edges[i].length == 2
0 <= ai, bi < n
ai != bi
不會(huì)有重復(fù)邊。

解法1——并查集

關(guān)于并查集可見(jiàn)：【算法基礎(chǔ)：數(shù)據(jù)結(jié)構(gòu)】2.3 并查集

并查集得出各個(gè)聯(lián)通集合中元素的數(shù)量，不同集合中的元素都可以兩兩組合。

class Solution {public long countPairs(int n, int[][] edges) {long ans = 0;// 并查集int[] p = new int[n];Arrays.setAll(p, e -> e);for (int[] e: edges) {if (p[e[0]] != p[e[1]]) p[find(p, e[0])] = find(p, e[1]);}// 記錄每個(gè)集合中的元素個(gè)數(shù)Map<Integer, Integer> cnt = new HashMap<>();for (int i = 0; i < n; ++i) {cnt.merge(find(p, i), 1, Integer::sum);}for (int v: cnt.values()) {ans += (long)v * (n - v);       // 和其它所有集合的一一對(duì)應(yīng)}return ans / 2;                     // 結(jié)果除以2去掉重復(fù)計(jì)算的}public int find(int[]p, int x) {if (p[x] != x) p[x] = find(p, p[x]);return p[x];}
}

解法2——dfs求連通塊大小

class Solution {public long countPairs(int n, int[][] edges) {long ans = 0, total = 0;List<Integer>[] g = new ArrayList[n];boolean[] st = new boolean[n];Arrays.setAll(g, e -> new ArrayList<Integer>());for (int[] e: edges) {g[e[0]].add(e[1]);g[e[1]].add(e[0]);}for (int i = 0; i < n; ++i) {if (!st[i]) {int cnt = dfs(g, st, i);    // dfs計(jì)算連通塊大小ans += total * cnt;total += cnt;}}return ans;}public int dfs(List<Integer>[] g, boolean[] st, int x) {int res = 1;st[x] = true;for (int y: g[x]) {if (!st[y]) {res += dfs(g, st, y);}}return res;}
}

1402. 做菜順序

https://leetcode.cn/problems/reducing-dishes/description/?envType=daily-question&envId=2023-10-22

提示：

n == satisfaction.length
1 <= n <= 500
-1000 <= satisfaction[i] <= 1000

解法1——?jiǎng)討B(tài)規(guī)劃

dp[i][j] 表示前 i+1 個(gè)菜，選擇 j 個(gè)時(shí)的值。
最后結(jié)果是前 n 個(gè)菜中，選擇 0~n 個(gè)時(shí)的最大值。

class Solution {public int maxSatisfaction(int[] satisfaction) {int n = satisfaction.length;int[][] dp = new int[n + 1][n + 1];Arrays.sort(satisfaction);dp[0][1] = satisfaction[0];for (int i = 1; i < n; ++i) {for (int j = 1; j <= i + 1; ++j) {dp[i][j] = dp[i - 1][j - 1] + satisfaction[i] * j;}}return Arrays.stream(dp[n - 1]).max().getAsInt();}
}

解法2——貪心?

見(jiàn)：https://leetcode.cn/problems/reducing-dishes/solutions/198214/zuo-cai-shun-xu-by-leetcode-solution/?envType=daily-question&envId=2023-10-22

class Solution {public int maxSatisfaction(int[] satisfaction) {Arrays.sort(satisfaction);int ans = 0, s = 0;for (int i = satisfaction.length - 1; i >= 0; --i) {s += satisfaction[i];if (s <= 0) return ans;ans += s;}return ans;}
}