模拟。
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
int n = nums.size(), ans = 0;
for (int i = 0; i < n; i++) {
if (Integer.bitCount(i) == k) {
ans += nums.get(i);
}
}
return ans;
}
}
|
比赛时又写复杂了，当时是想到所有相同的数都必须同时选，所以加了一层循环来跳过相同的数。但是相同的数天然的不满足判断条件，所以不需要这样写。这题唯一需要注意的就是特判全都不选的情况，以及全都选的情况必定满足，可以直接加到答案里（以减少判断代码）。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int countWays(List<Integer> nums) {
Collections.sort(nums);
int n = nums.size(), ans = 1;
if (nums.get(0) > 0) ans++;
for (int i = 0; i < n - 1; i++) {
if (i + 1 > nums.get(i) && i + 1 < nums.get(i + 1)) {
ans++;
}
}
return ans;
}
}
|
比赛时又又写复杂了，当时是把所有的库存都清除了再二分的，其实可以直接二分！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
int ans = 0;
for (var cur : composition) {
int lo = 0, hi = (int) 2e8;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
long cnt = 0L;
for (int i = 0; i < n; i++) {
cnt += Math.max((long) cur.get(i) * mid - stock.get(i), 0L) * cost.get(i);
}
if (cnt <= budget) lo = mid + 1;
else hi = mid - 1;
}
ans = Math.max(ans, hi);
}
return ans;
}
}
|
注意题目的描述是每对元素的乘积都是完全平方数。朴素的想法就是对下标进行质因数分解，将所有出现次数为奇数质因数相乘，其结果作为桶的下标，把所有同类的数放在同一个桶里面，然后对每个桶求和取最大值，这样的时间复杂度是 \(O(n\sqrt{n})\)。但是有 \(O(n)\) 的解法，如下所示。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public long maximumSum(List<Integer> nums) {
long ans = 0L;
int n = nums.size();
for (int i = 1; i <= n; i++) {
long sum = 0L;
for (int j = 1; i * j * j <= n; j++) {
sum += nums.get(i * j * j - 1);
}
ans = Math.max(ans, sum);
}
return ans;
}
}
|