100103. Divisible and Non-divisible Sums Difference
给你两个正整数 n 和 m 。
现定义两个整数 num1 和 num2 ，如下所示：
- num1：范围 [1, n] 内所有 无法被 m 整除 的整数之和。
- num2：范围 [1, n] 内所有 能够被 m 整除 的整数之和。
返回整数 num1 - num2 。
测试样例：
输入：n = 10, m = 3
输出：19
解释：
在这个示例中：
- 范围 [1, 10] 内无法被 3 整除的整数为 [1,2,4,5,7,8,10] ，num1 = 这些整数之和 = 37 。
- 范围 [1, 10] 内能够被 3 整除的整数为 [3,6,9] ，num2 = 这些整数之和 = 18 。
返回 37 - 18 = 19 作为答案。
解答：暴力遍历。
class Solution {
public int differenceOfSums(int n, int m) {
int n1 = 0, n2 = 0;
for (int i = 1; i <= n; ++i) {
if (i % m == 0) {
n2 += i;
} else {
n1 += i;
}
}
return n1 - n2;
}
}100085. Minimum Processing Time
你有 n 颗处理器，每颗处理器都有 4 个核心。现有 n * 4 个待执行任务，每个核心只执行 一个 任务。
给你一个下标从 0 开始的整数数组 processorTime ，表示每颗处理器最早空闲时间。另给你一个下标从 0 开始的整数数组 tasks ，表示执行每个任务所需的时间。返回所有任务都执行完毕需要的 最小时间 。
注意：每个核心独立执行任务。
测试样例：
输入：processorTime = [8,10], tasks = [2,2,3,1,8,7,4,5]
输出：16
解释：
最优的方案是将下标为 4, 5, 6, 7 的任务分配给第一颗处理器（最早空闲时间 time = 8），下标为 0, 1, 2, 3 的任务分配给第二颗处理器（最早空闲时间 time = 10）。
- 第一颗处理器执行完所有任务需要花费的时间 = max(8 + 8, 8 + 7, 8 + 4, 8 + 5) = 16 。
- 第二颗处理器执行完所有任务需要花费的时间 = max(10 + 2, 10 + 2, 10 + 3, 10 + 1) = 13 。
因此，可以证明执行完所有任务需要花费的最小时间是 16 。
解答：利用排序+贪婪。最早空闲的处理器，就需要处理耗时最长的任务。
class Solution {
public int minProcessingTime(List<Integer> processorTime, List<Integer> tasks) {
Collections.sort(tasks, (a, b) -> (b.compareTo(a)));
Collections.sort(processorTime);
Iterator<Integer> processIterator = processorTime.iterator();
int count = 0, res = 0, cur = processIterator.next();
for (int n : tasks) {
res = Math.max(res, cur + n);
++count;
if (count == 4) {
count = 0;
if (processIterator.hasNext()) {
cur = processIterator.next();
}
}
}
return res;
}
}8028. Apply Operations to Make Two Strings Equal
给你两个下标从 0 开始的二进制字符串 s1 和 s2 ，两个字符串的长度都是 n ，再给你一个正整数 x 。
你可以对字符串 s1 执行以下操作 任意次 ：
- 选择两个下标 i 和 j ，将 s1[i] 和 s1[j] 都反转，操作的代价为 x 。
- 选择满足 i < n - 1 的下标 i ，反转 s1[i] 和 s1[i + 1] ，操作的代价为 1 。
请你返回使字符串 s1 和 s2 相等的 最小 操作代价之和，如果无法让二者相等，返回 -1 。
注意 ，反转字符的意思是将 0 变成 1 ，或者 1 变成 0 。
测试样例：
输入：s1 = "1100011000", s2 = "0101001010", x = 2
输出：4
解释：
我们可以执行以下操作：
- 选择 i = 3 执行第二个操作。结果字符串是 s1 = "1101111000" 。
- 选择 i = 4 执行第二个操作。结果字符串是 s1 = "1101001000" 。
- 选择 i = 0 和 j = 8 ，执行第一个操作。结果字符串是 s1 = "0101001010" = s2 。
总代价是 1 + 1 + 2 = 4 。这是最小代价和。
解答：首先我们需要寻找到所有不相同的位。如果不相同的位数是奇数个，那么返回-1（所有操作只能使得2个不同位同时变化，奇数个无法完成）。然后我们需要利用动态规划，配合一点贪婪的思维。不同的数位，可以和最近的不同位利用操作2缓慢传播或者利用操作1，直接和更远的位变化（必然不会和更远的位利用1传播到达，一点贪婪的思维）。这样利用动态规划可以计算出最小开销。
class Solution {
public int minOperations(String s1, String s2, int x) {
if (!isValid(s1, s2)) {
return -1;
} else if (s1.equals(s2)) {
return 0;
}
List<Integer> nonMatch = new ArrayList<>();
for (int i = 0; i < s1.length(); ++i) {
if (s1.charAt(i) != s2.charAt(i)) {
nonMatch.add(i);
}
}
int len = nonMatch.size();
Integer[][] dp = new Integer[len + 1][2];
dp[0][0] = 0;
dp[1][1] = 0;
for (int i = 1; i < nonMatch.size(); ++i) {
dp[i + 1][0] = add(dp[i][1], x);
dp[i + 1][1] = dp[i][0];
int diff = Math.min(nonMatch.get(i) - nonMatch.get(i - 1), x);
dp[i + 1][0] = min(add(dp[i - 1][0], diff), dp[i + 1][0]);
dp[i + 1][1] = min(add(dp[i - 1][1], diff), dp[i + 1][1]);
}
return dp[len][0];
}
private boolean isValid(String s1, String s2) {
int diff = 0;
for (int i = 0; i < s1.length(); ++i) {
diff += (s1.charAt(i) - '0');
diff -= (s2.charAt(i) - '0');
}
return Math.abs(diff) % 2 == 0;
}
private Integer add(Integer ori, int diff) {
if (ori == null) {
return null;
} else {
return ori + diff;
}
}
private Integer min(Integer ori, Integer other) {
if (ori == null && other == null) {
return null;
} else if (ori == null) {
return other;
} else if (other == null) {
return ori;
} else {
return Math.min(other, ori);
}
}
}100087. Apply Operations on Array to Maximize Sum of Squares
给你一个下标从 0 开始的整数数组 nums 和一个 正 整数 k 。
你可以对数组执行以下操作 任意次 ：
- 选择两个互不相同的下标 i 和 j ，同时 将 nums[i] 更新为 (nums[i] AND nums[j]) 且将 nums[j] 更新为 (nums[i] OR nums[j]) ，OR 表示按位 或 运算，AND 表示按位 与 运算。
你需要从最终的数组里选择 k 个元素，并计算它们的 平方 之和。
请你返回你可以得到的 最大 平方和。
由于答案可能会很大，将答案对 10^9 + 7 取余 后返回。
测试样例
输入：nums = [2,6,5,8], k = 2
输出：261
解释：
我们可以对数组执行以下操作：
- 选择 i = 0 和 j = 3 ，同时将 nums[0] 变为 (2 AND 8) = 0 且 nums[3] 变为 (2 OR 8) = 10 ，结果数组为 nums = [0,6,5,10] 。
- 选择 i = 2 和 j = 3 ，同时将 nums[2] 变为 (5 AND 10) = 0 且 nums[3] 变为 (5 OR 10) = 15 ，结果数组为 nums = [0,6,0,15] 。
从最终数组里选择元素 15 和 6 ，平方和为 152 + 62 = 261 。261 是可以得到的最大结果。
解答：这道题目比较考验思维。假设c = a | b, d = a & b, 那么c + d = a + b。这样我们需要利用一下平方和性质，如果a + b = c + d，那么Math.max(c, d) - Math.min(c, d) > Math.max(a, b) - Math.min(a, b)时，(c,d)平方和更大。利用这个性质，我们需要把最大的k个数尽量放大。
class Solution {
private static final int mod = 1_000_000_007;
public int maxSum(List<Integer> nums, int k) {
int[] arr = new int[nums.size()];
int len = 0;
for (int n : nums) {
arr[len++] = n;
}
Arrays.sort(arr);
long res = 0;
Queue<Integer>[] queues = new Queue[30];
for (int i = 0; i < 30; ++i) {
queues[i] = new LinkedList<>();
}
for (int i = 0; i < len; ++i) {
for (int j = 0; j < 30; ++j) {
if (isOccupy(arr[i], j)) {
queues[j].add(i);
}
}
}
for (int i = len - 1; i >= len - k; --i) {
for (int j = 0; j < 30; ++j) {
if (!isOccupy(arr[i], j) && !queues[j].isEmpty() && queues[j].peek() < i) {
arr[i] += (1 << j);
int p = queues[j].poll();
arr[p] -= (1 << j);
}
}
long tmp = arr[i];
res = (res + tmp * tmp) % mod;
}
return (int) (res % mod);
}
private boolean isOccupy(int num, int offset) {
int m = (num >> offset) & 1;
return m == 1;
}
}