lcp366

2894. 分类求和并作差

方法一：求和公式

class Solution {
    public int differenceOfSums(int n, int m) {
        // 能被m整除的和 s1 = m + 2m + 3m + ... + n / m * m
        // = m(1 + 2 + 3 + ... + n / m) = m * (n / m * (1 + n / m) / 2)
        // 不能被m整除的和 s2 = n * (1 + n) / 2 - s1
        // res = s2 - s1 
        return n * (1 + n) / 2 - n / m * m * (1 + n / m);
    }
}

2895. 最小处理时间

方法一：贪心

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

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

方法一：记忆化搜索

class Solution {
    public int minOperations(String s1, String s2, int x) {
        n = s1.length();
        int cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < n; ++i) {
            if (s1.charAt(i) == '1')
                ++cnt1;
            if (s2.charAt(i) == '1')
                ++cnt2;
        }
        if (cnt1 % 2 != cnt2 % 2)
            return -1;
        this.s1 = s1;
        this.s2 = s2;
        this.x = x;
        dp = new int[n][n + 1][2];
        for (int[][] a : dp)
            for (int[] b : a)
                Arrays.fill(b, -1);
        return dfs(0, 0, false);
    }

    public int dfs(int index, int key, boolean reverse) {
        if (index >= n)
            return key == 0 && !reverse ? 0 : inf;
        if (dp[index][key][reverse ? 1 : 0] != -1)
            return dp[index][key][reverse ? 1 : 0];
        char ch1 = s1.charAt(index), ch2 = s2.charAt(index);
        if ((ch1 == ch2) == !reverse)
            return dp[index][key][reverse ? 1 : 0] = dfs(index + 1, key, false);
        int res = Math.min(dfs(index + 1, key + 1, false) + x, dfs(index + 1, key, true) + 1);
        if (key > 0)
            res = Math.min(res, dfs(index + 1, key - 1, false));
        return dp[index][key][reverse ? 1 : 0] = res;
    }

    String s1, s2;
    int x, inf = Integer.MAX_VALUE >> 1, n;
    int[][][] dp;
    
}