LeetCode Contest 366

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;
    }
}