第 366 场力扣周赛

分类求和并作差

数学性质，\([1,n]\) 中能被 \(m\) 整除的数有 \(\lfloor \frac{n}{m}\rfloor\) 个。

class Solution {
    public int differenceOfSums(int n, int m) {
        return (1 + n) * n / 2 - (1 + (n / m)) * (n / m) * m;
    }
}

最小处理时间

排序 + 贪心。

class Solution {
    public int minProcessingTime(List<Integer> processorTime, List<Integer> tasks) {
        Collections.sort(processorTime);
        Collections.sort(tasks, (a , b) -> b - a);
        int n = processorTime.size(), ans = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, processorTime.get(i) + tasks.get(i * 4));
        }
        return ans;
    }
}

执行操作使两个字符串相等

方法一：动态规划

今天脑子有点笨啊，本来做出来了，但是我将 dp 的初始值设置为 Integer.MAX_VALUE，将 dfs 不满足条件时的返回值也设置为该值，而判断是否记忆化的条件也设置为该值，所以所有不满足条件的方案都没有记忆化上。

我经常会写出从上到下记忆化的代码，但是每次都比从下到上的记忆化慢，经过分析，原因如下：从下到上的记忆化，只要该节点计算过，就会直接返回；而从上到下的记忆化，只有在当前节点的值比记忆化的值大时，才会直接返回，也就是说，这样的代码只会将所有大于记忆化的值的方案给剪枝掉，所有小于记忆化的值的方案会重复计算。

class Solution {
    public int minOperations(String s1, String s2, int x) {
        int n = s1.length();
        int[][][] dp = new int[n][n + 1][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n + 1; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        int ans = dfs(0, 0, 0, s1, s2, x, dp);
        return ans >= (int) 1e9 ? -1 : ans;
    }

    private int dfs(int i, int c, int r, String s1, String s2, int x, int[][][] dp) {
        if (i == s1.length()) {
            if (c % 2 == 0 && r == 0) {
                return -c / 2 * x;
            }
            return (int) 1e9;
        }
        if (dp[i][c][r] != -1) return dp[i][c][r];
        int res = 0;
        if ((s1.charAt(i) == s2.charAt(i)) == (r == 0)) {
            res = dfs(i + 1, c, 0, s1, s2, x, dp);
        } else {
            res = dfs(i + 1, c + 1, 0, s1, s2, x, dp) + x;
            res = Math.min(res, dfs(i + 1, c, 1, s1, s2, x, dp) + 1);
        }
        return dp[i][c][r] = res;
    }
}

方法二：动态规划

时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\) 的解法，其实比赛时第一眼差不多就想到这种解法，但是没有细想。

class Solution {
    public int minOperations(String s1, String s2, int x) {
        int n = s1.length();
        int pre = -1, cnt = 0;
        int dp0 = (int) 1e9, dp1 = 0;
        for (int i = 0; i < n; i++) {
            if (s1.charAt(i) != s2.charAt(i)) {
                cnt ^= 1;
                int t = dp1;
                dp1 = Math.min(dp1 + (cnt == 1 ? x : 0), dp0 + i - pre);
                dp0 = t;
                pre = i;
            }
        }
        return cnt == 1 ? -1 : dp1;
    }
}

对数组执行操作使平方和最大

挺简单一道题，T3 卡太久，脑子短路没时间做这题。对于每一位，每次操作其实就是交换两个数之间的 \(0\) 和 \(1\)，我们应该总是把 \(1\) 交换到更大的数上，这样平方和最大。所以统计每一位的 \(1\) 的个数，贪心的组合成最大的数，然后取平方加入答案即可。

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int maxSum(List<Integer> nums, int k) {
        int[] cnt = new int[30];
        for (int x : nums) {
            for (int i = 0; i < 30; i++) {
                cnt[i] += x >> i & 1;
            }
        }

        long ans = 0L;
        while (k-- != 0) {
            int x = 0;
            for (int i = 0; i < 30; i++) {
                if (cnt[i] > 0) {
                    cnt[i]--;
                    x |= 1 << i;
                }
            }
            ans = (ans + (long) x * x) % MOD;
        }

        return (int) ans;
    }
}