競(jìng)賽鏈接

https://leetcode.cn/contest/weekly-contest-363/

Q1：100031. 計(jì)算 K 置位下標(biāo)對(duì)應(yīng)元素的和

https://leetcode.cn/problems/sum-of-values-at-indices-with-k-set-bits/

提示：
1 <= nums.length <= 1000
1 <= nums[i] <= 10^5
0 <= k <= 10

競(jìng)賽時(shí)代碼

class Solution {public int sumIndicesWithKSetBits(List<Integer> nums, int k) {int ans = 0;for (int i = 0; i < nums.size(); ++i) {if (Integer.bitCount(i) == k) ans += nums.get(i);}return ans;}
}

寫法2——手寫二進(jìn)制中1的數(shù)量

class Solution {public int sumIndicesWithKSetBits(List<Integer> nums, int k) {int ans = 0;for (int i = 0; i < nums.size(); ++i) {if (cnt(i) == k) ans += nums.get(i);}return ans;}public int cnt(int x) {int res = 0;while (x != 0) {res++;x &= x - 1;}return res;}
}

Q2：100040. 讓所有學(xué)生保持開心的分組方法數(shù)（排序后枚舉分界）

https://leetcode.cn/problems/happy-students/description/

提示：
1 <= nums.length <= 10^5
0 <= nums[i] < nums.length

競(jìng)賽時(shí)代碼

將學(xué)生排序后， 一個(gè)學(xué)生 x 被選了的時(shí)候，比它小的一定必須被選；同理一個(gè)學(xué)生 y 不被選的時(shí)候，比它大的一定不能被選。

枚舉每個(gè)位置，假設(shè) 0~i 被選擇，i+1~n-1 不被選擇。檢查是否合理，合理則 ans ++；

class Solution {public int countWays(List<Integer> nums) {// 按題意——一定先選擇nums值更小的學(xué)生，所以——從小到大排序Collections.sort(nums);int n = nums.size(), ans = 0;if (nums.get(0) > 0) ans++;     // 處理特例是否可以全不選// 枚舉選擇到每個(gè)位置for (int i = 0; i < n; ++i) {  // 檢查已經(jīng)選擇人數(shù)i+1是否嚴(yán)格大于nums[i]if (i + 1 > nums.get(i)) { // 檢查已經(jīng)選擇人數(shù)i+1是否嚴(yán)格小于下一個(gè)沒被選擇的學(xué)生nums[i+1]  （注意要判斷越界）if (i + 1 < n && nums.get(i + 1) <= i + 1) continue;    // 不滿足就跳過ans++;  // 這個(gè)位置合理，答案+1}}return ans;}
}

Q3：100033. 最大合金數(shù)（二分答案）

https://leetcode.cn/problems/maximum-number-of-alloys/description/

提示：
1 <= n, k <= 100
0 <= budget <= 10^8
composition.length == k
composition[i].length == n
1 <= composition[i][j] <= 100
stock.length == cost.length == n
0 <= stock[i] <= 10^8
1 <= cost[i] <= 100

競(jìng)賽時(shí)代碼

注意到題目中說明——“所有合金都需要由同一臺(tái)機(jī)器制造。”，且觀察到 k 的數(shù)據(jù)范圍較小，所以可以枚舉使用每臺(tái)機(jī)器。
對(duì)于每臺(tái)機(jī)器，使用二分查找求出它可以制造出的最大的合金數(shù)量。

二分查找時(shí)判斷的依據(jù)是花費(fèi)的前有沒有在 budget 的范圍內(nèi)。

class Solution {public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {long ans = 0;// 按照題意，所有合金都需要由同一臺(tái)機(jī)器制造。枚舉每個(gè)機(jī)器。for (int i = 0; i < k; ++i) {ans = Math.max(ans, op(n, budget, composition.get(i), stock, cost));}return (int)ans;}// 計(jì)算使用某臺(tái)機(jī)器時(shí)的最大制造數(shù)量public long op(int n, int budget, List<Integer> composition, List<Integer> stock, List<Integer> cost) {// 二分答案long l = 0, r = (long)Integer.MAX_VALUE;while (l < r) {long mid = l + r + 1 >> 1;if (check(mid, n, budget, composition, stock, cost)) l = mid;else r = mid - 1;}return l;}// 檢查是否可以造出 k 個(gè)合金public boolean check(long k, int n, int budget, List<Integer> composition, List<Integer> stock, List<Integer> cost) {long s = 0;     // 記錄額外花費(fèi)for (int i = 0; i < n; ++i) {long need = k * composition.get(i);if (need <= stock.get(i)) continue;s += cost.get(i) * (need - stock.get(i));if (s > budget) return false;   // 額外花費(fèi)超了，不能造出k個(gè)合金}return true;}
}

Q4：8041. 完全子集的最大元素和

https://leetcode.cn/problems/maximum-element-sum-of-a-complete-subset-of-indices/description/

提示：
1 <= n == nums.length <= 10^4
1 <= nums[i] <= 10^9

競(jìng)賽時(shí)代碼——質(zhì)因數(shù)分解+哈希表

對(duì)每個(gè)下標(biāo)質(zhì)因數(shù)分解，兩兩相乘之后的結(jié)果是完全平方數(shù)，那么這兩個(gè)數(shù)字的質(zhì)因數(shù)分解的奇偶性相同。 例如2=2^1，8=23；相同質(zhì)因數(shù)出現(xiàn)的次數(shù)的奇偶性相同，則兩者可以匹配。

根據(jù)質(zhì)因數(shù)分解的結(jié)果將所有數(shù)字分組即可。

class Solution {public long maximumSum(List<Integer> nums) {// 兩兩之間相乘之后是完全平方數(shù)，則質(zhì)因數(shù)分解結(jié)果滿足各個(gè)質(zhì)因數(shù)數(shù)量奇偶性相同int n = nums.size();String[] mask = new String[n];long ans = 0;// key是mask,value是sumMap<String, Long> m = new HashMap<>();     for (int i = 1; i <= n; ++i) {mask[i - 1] = op(i);                                        // 計(jì)算maskm.merge(mask[i - 1], (long)nums.get(i - 1), Long::sum);     // 求和ans = Math.max(ans, m.get(mask[i - 1]));                    // 更新答案}return ans;}// 計(jì)算下標(biāo)x的質(zhì)因數(shù)分解掩碼maskpublic String op(int x) {// 將質(zhì)因數(shù)的數(shù)量為奇數(shù)的部分記錄下來String mask = "";for (int i = 2; i <= x / i; ++i) {if (x % i == 0) {int s = 0;while (x % i == 0) {s++;x /= i;}if (s % 2 == 1) mask += String.valueOf(i) + " ";}}if (x > 1) mask += String.valueOf(x) + " ";return mask;}
}

解法2——定義core(x)為 x 除去完全平方因子后的剩余結(jié)果

https://leetcode.cn/problems/maximum-element-sum-of-a-complete-subset-of-indices/solutions/2446037/an-zhao-corei-fen-zu-pythonjavacgo-by-en-i6nu/

計(jì)算方式同質(zhì)因數(shù)分解，把 n 的所有出現(xiàn)次數(shù)為奇數(shù)的質(zhì)因子相乘，即為 core(n)。

class Solution {public long maximumSum(List<Integer> nums) {// 兩兩之間相乘之后是完全平方數(shù)，則質(zhì)因數(shù)分解結(jié)果滿足各個(gè)質(zhì)因數(shù)數(shù)量奇偶性相同int n = nums.size();long[] sum = new long[n + 1];long ans = 0;for (int i = 1; i <= n; ++i) {int c = op(i);                 // 計(jì)算masksum[c] += nums.get(i - 1);     // 求和ans = Math.max(ans, sum[c]);   // 更新答案}return ans;}// 計(jì)算下標(biāo)x的質(zhì)因數(shù)分解掩碼maskpublic int op(int x) {// 將質(zhì)因數(shù)的數(shù)量為奇數(shù)的部分記錄下來int res = 1;for (int i = 2; i <= x / i; ++i) {if (x % i == 0) {int s = 0;while (x % i == 0) {s++;x /= i;}if (s % 2 == 1) res *= i;}}if (x > 1) res *= x;return res;}
}

成績(jī)記錄

T4 沒有那么難！想得慢了！