100031. Sum of Values at Indices With K Set Bits
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
请你用整数形式返回 nums 中的特定元素之 和 ，这些特定元素满足：其对应下标的二进制表示中恰存在 k 个置位。
整数的二进制表示中的 1 就是这个整数的 置位 。
例如，21 的二进制表示为 10101 ，其中有 3 个置位。
测试样例：
输入：nums = [5,10,1,5,2], k = 1
输出：13
解释：
下标 1、2 和 4 在其二进制表示中都存在 k = 1 个置位。因此，答案为 nums[1] + nums[2] + nums[4] = 13 。
解答：按题意计算下标二进制位数和，并累加
class Solution {
public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
int res = 0, offset = 0;
for (int n : nums) {
int cur = offset, count = 0;
while (cur > 0) {
count += (cur % 2);
cur /= 2;
}
if (count == k) {
res += n;
}
++offset;
}
return res;
}
}100040. Happy Students
给你一个下标从 0 开始、长度为 n 的整数数组 nums ，其中 n 是班级中学生的总数。班主任希望能够在让所有学生保持开心的情况下选出一组学生：
如果能够满足下述两个条件之一，则认为第 i 位学生将会保持开心：
- 这位学生被选中，并且被选中的学生人数 严格大于 nums[i] 。
- 这位学生没有被选中，并且被选中的学生人数 严格小于 nums[i] 。
返回能够满足让所有学生保持开心的分组方法的数目。
测试样例：
输入：nums = [1,1]
输出：2
解释：
有两种可行的方法。
- 班主任没有选中学生。
- 班主任选中所有学生形成一组。
如果班主任仅选中一个学生来完成分组，那么两个学生都无法保持开心。因此，仅存在两种可行的方法。
解答：排序后遍历数组。所有学生都选上的情况下，一定能大家都开心。所以遍历数组，查看能产生所有人都开心的断开位置。
class Solution {
public int countWays(List<Integer> nums) {
int len = nums.size();
int[] arr = new int[len];
int offset = 0;
for (int n : nums) {
arr[offset++] = n;
}
Arrays.sort(arr);
int res = arr[0] > 0 ? 1 : 0;
for (int i = 0; i < len; ++i) {
int select = i + 1;
if (arr[i] < select && (i + 1 == len || arr[i + 1] > select)) {
++res;
}
}
return res;
}
}100033. Maximum Number of Alloys
假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。
对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有 stock[i] 份 i 类型金属，而每购入一份 i 类型金属需要花费 cost[i] 的金钱。
给你整数 n、k、budget，下标从 1 开始的二维数组 composition，两个下标从 1 开始的数组 stock 和 cost，请你在预算不超过 budget 金钱的前提下，最大化 公司制造合金的数量。
所有合金都需要由同一台机器制造。
返回公司可以制造的最大合金数。
测试样例
输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3]
输出：2
解释：
最优的方法是使用第 1 台机器来制造合金。要想制造 2 份合金，我们需要购买：
- 2 份第 1 类金属。
- 2 份第 2 类金属。
- 2 份第 3 类金属。
总共需要 2 1 + 2 2 + 2 * 3 = 12 的金钱，小于等于预算 15 。注意，我们最开始时候没有任何一类金属，所以必须买齐所有需要的金属。可以证明在示例条件下最多可以制造 2 份合金。
解答：看错题目了。。。没注意到所有合金都是同一台机器制造。我还在想，为啥这题能这么难。注意到之后，利用折半搜索就能寻找到每种金属的最大生成数。
class Solution {
public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock,
List<Integer> cost) {
long max = 0;
for (List<Integer> list : composition) {
long left = 0, right = 200000000;
while (left < right) {
long mid = (left + right + 1) / 2, count = 0;
for (int i = 0; i < n; i++) {
count += cost.get(i) * Math.max(0, mid * list.get(i) - stock.get(i));
}
if (count > budget) {
right = mid - 1;
} else {
left = mid;
}
}
max = Math.max(max, left);
}
return (int) max;
}
}8041. Maximum Element-Sum of a Complete Subset of Indices
给你一个下标从 1 开始、由 n 个整数组成的数组。
如果一组数字中每对元素的乘积都是一个完全平方数，则称这组数字是一个 完全集 。
下标集 {1, 2, ..., n} 的子集可以表示为 {i1, i2, ..., ik}，我们定义对应该子集的 元素和 为 nums[i1] + nums[i2] + ... + nums[ik] 。
返回下标集 {1, 2, ..., n} 的 完全子集 所能取到的 最大元素和 。
完全平方数是指可以表示为一个整数和其自身相乘的数。
测试样例
输入：nums = [8,7,3,5,7,2,4,9]
输出：16
除了由单个下标组成的子集之外，还有两个下标集的完全子集：{1,4} 和 {2,8} 。
与下标 1 和 4 对应的元素和等于 nums[1] + nums[4] = 8 + 5 = 13 。
与下标 2 和 8 对应的元素和等于 nums[2] + nums[8] = 7 + 9 = 16 。
因此，下标集的完全子集可以取到的最大元素和为 16 。
解答：这道题目其实没啥难度，主要考察的质因数分解。我们需要把一个数分解为可以完全平方部分和不能完全平方部分。同一个小组内的数字，它的不能完全平方部分必然相同。然后计算数字之和最大的小组。
class Solution {
public long maximumSum(List<Integer> nums) {
int len = nums.size();
int[] arr = new int[len];
int offset = 0;
long res = 0;
for (int n : nums) {
arr[offset++] = n;
res = Math.max(res, n);
}
offset = 1;
Set<Integer> perfect = new HashSet<>();
while (offset * offset <= len) {
perfect.add(offset * offset);
++offset;
}
HashMap<Integer, Long> mem = new HashMap<>();
for (int i = 1; i <= len; ++i) {
int num = i, remain = 1;
for (int t = 2; t * t <= num; ++t) {
int count = 0;
while (num % t == 0) {
++count;
num /= t;
}
if (count % 2 == 1) {
remain *= t;
}
}
remain *= num;
mem.put(remain, mem.getOrDefault(remain, 0L) + arr[i - 1]);
}
for (Long result : mem.values()) {
res = Math.max(res, result);
}
return res;
}
}