第 368 场力扣周赛

元素和最小的山形三元组 I

同下。

元素和最小的山形三元组 II

前后缀分解。

class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n + 1], suf = new int[n + 1];
        pre[0] = suf[n] = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            pre[i + 1] = Math.min(pre[i], nums[i]);
        }
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = Math.min(suf[i + 1], nums[i]);
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > pre[i] && nums[i] > suf[i + 1]) {
                ans = Math.min(ans, pre[i] + nums[i] + suf[i + 1]);
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}

合法分组的最少组数

贪心，不太会，直接看题解。

class Solution {
    public int minGroupsForValidAssignment(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
        }
        int k = nums.length;
        for (int x : cnt.values()) {
            k = Math.min(k, x);
        }
        
        for (; ; k--) {
            int ans = 0;
            for (int x : cnt.values()) {
                if (x / k < x % k) {
                    ans = 0;
                    break;
                }
                ans += (x + k) / (k + 1);
            }
            if (ans > 0) {
                return ans;
            }
        }
    }
}

得到 K 个半回文串的最少修改次数

直接记忆化搜索就能搞定，特别注意子字符串的长度要求至少为 \(2\)。当然还可以预处理出所有因子，也可以将记忆化搜索转化为自底向上的动态规划。

class Solution {
    public int minimumChanges(String s, int k) {
        int n = s.length();

        int[][] change = new int[n][n];
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                change[i][j] = calc(s.substring(i, j + 1));
            }
        }

        int[][] dp = new int[n][k];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        return dfs(0, s, n, k - 1, change, dp);
    }

    private int calc(String s) {
        int n = s.length(), res = n;
        for (int d = 1; d < n; d++) {
            if (n % d == 0) {
                int cnt = 0;
                for (int k = 0; k < d; k++) {
                    for (int i = k, j = n - d + k; i < j; i += d, j -= d) {
                        if (s.charAt(i) != s.charAt(j)) {
                            cnt++;
                        }
                    }
                }
                res = Math.min(res, cnt);
            }
        }
        return res;
    }

    private int dfs(int i, String s, int n, int k, int[][] change, int[][] dp) {
        if (k == 0) {
            return change[i][n - 1];
        }

        if (dp[i][k] != -1) {
            return dp[i][k];
        }

        int res = n;
        for (int j = i + 1; j < n - 2 * k; j++) {
            res = Math.min(res, dfs(j + 1, s, n, k - 1, change, dp) + change[i][j]);
        }
        return dp[i][k] = res;
    }
}