[Leetcode Weekly Contest]368

链接：LeetCode

[Leetcode]2908. 元素和最小的山形三元组 I

给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

• i < j < k
• nums[i] < nums[j] 且 nums[k] < nums[j]

请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。
遍历循环即可。

[Leetcode]2909. 元素和最小的山形三元组 II

给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

• i < j < k
• nums[i] < nums[j] 且 nums[k] < nums[j]

请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。

枚举 nums[j] + 前后缀分解。知道了 \(\textit{nums}[j]\)，只需要知道 j 左边的最小值和右边的最小值，就知道了三元组的和的最小值。

class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        int leftMin = nums[0];
        for(int i=1;i<n;++i) {
            if(leftMin < nums[i]) {
                left[i] = leftMin;
            } else {
                left[i] = Integer.MAX_VALUE;
                leftMin = nums[i];
            }
        }
        int rightMin = nums[n-1];
        for(int i=n-2;i>=0;--i) {
            if(rightMin < nums[i]) {
                right[i] = rightMin;
            } else {
                right[i] = Integer.MAX_VALUE;
                rightMin = nums[i];
            }
        }
        int res = Integer.MAX_VALUE;
        for(int i=1;i<n-1;++i) {
            if(left[i] == Integer.MAX_VALUE || right[i] == Integer.MAX_VALUE) continue;
            res = Math.min(res, left[i] + right[i] + nums[i]);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

[Leetcode] 2910. 合法分组的最少组数

给你一个长度为 n 下标从 0 开始的整数数组 nums 。
我们想将下标进行分组，使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。
如果以下条件成立，我们说这个分组方案是合法的：

• 对于每个组 g ，同一组内所有下标在 nums 中对应的数值都相等。
• 对于任意两个组 g1 和 g2 ，两个组中 下标数量 的 差值不超过 1 。
  请你返回一个整数，表示得到一个合法分组方案的 最少 组数。

统计每个数字的出现次数，记在哈希表中。假设可以分成大小为 \(k\) 和 \(k+1\) 的组，现在需要算出每个 \(\textit{cnt}[x]\) 最少可以分成多少组。
由于两个组中下标数量的差值不超过 1， \(k\)最大可以取\(\textit{cnt}[x]\)中的最小值，我们可以把问题分解为两个部分：
1.\(\textit{cnt}[x]\)中的数量是否可以分成大小为 \(k\) 和 \(k+1\) 的组。
2.如果能，输出最小的分组数即可，如果不能，减小\(k\)的值再判断，直到\(k\)为零，输出\(-1\)。
针对第一个问题，我们可以先假设能进行对应的分组，则必定有\(a\)个\(k\)数量的组与\(b\)个\(k+1\)数量的组，那么针对\(\textit{cnt}[x]\)中的元素y必定有：

则

且\(a\),\(b\)为零或者正整数，要满足这个式子，必定有\(a+b>b\)，也就是\(y/k > y\%k\)。反之，如果满足\(y/k > y\%k\)，我们也必定能找到\(a*k+b*(k+1) = y\)的解。
针对第二个问题，如果需要分组的数目最小，我们必定需要尽量多分\(k+1\)的组，那么，求\(y/(k+1)\)的上界即可。

class Solution {
    public int minGroupsForValidAssignment(int[] nums) {
        Map<Integer, Integer> counter = new HashMap<>();
        for(int num:nums) {
            counter.put(num, counter.getOrDefault(num, 0) + 1);
        }
        List<Integer> set = new ArrayList<>();
        int minAssignment = Integer.MAX_VALUE;
        for(int count:counter.values()) {
            set.add(count);
            minAssignment = Math.min(minAssignment, count);
        }
        while(minAssignment > 0) {
            if(minGroups(set, minAssignment))return getMinGroups(set, minAssignment);
            else minAssignment --;
        }
        return -1;
    }

    private boolean minGroups(List<Integer> nums, int minAssignment) {
        for(int num:nums) {
            int a = num / minAssignment;
            int b = num % minAssignment;
            if(a<b) return false;
        }
        return true;
    }

    private int getMinGroups(List<Integer> nums, int minAssignment) {
        System.out.println(minAssignment);
        int res = 0;
        for(int num:nums) {
            res += Math.ceil(num*1.0/(minAssignment+1));
        }
        return res;
    }
}

[Leetcode] 2911. 得到 K 个半回文串的最少修改次数

给你一个字符串 s 和一个整数 k ，请你将 s 分成 k 个 子字符串 ，使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。
请你返回一个整数，表示需要修改的 最少 字符数目。
注意：

• 如果一个字符串从左往右和从右往左读是一样的，那么它是一个 回文串 。
• 如果长度为 len 的字符串存在一个满足 1 <= d < len 的正整数 d ，len % d == 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 ，那么我们说这个字符串是 半回文串 。比方说 "aa" ，"aba" ，"adbgad" 和 "abab" 都是 半回文串 ，而 "a" ，"ab" 和 "abca" 不是。
• 子字符串 指的是一个字符串中一段连续的字符序列。

factors = [[] for _ in range(201)]
for i in range(1, 201):
    for j in range(i * 2, 201, i):
        factors[j].append(i)

class Solution:
    def minimumChanges(self, s: str, steps: int) -> int:
        def f(i, j):
            l = j - i + 1
            ans = inf
            for x in factors[l]:
                res = 0
                for k in range(x):
                    substr = s[i + k:j + 1:x]
                    for idx in range(len(substr) // 2):
                        if substr[idx] != substr[-idx-1]:
                            res += 1
                ans = min(ans, res)
            return ans
        n = len(s)
        calc = [[inf] * n for _ in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                calc[i][j] = f(i, j)
        # dp[i][j] 表示 s[0] 到 s[i-1] 分为 j 个字符串需要修改的字母数量
        dp = [[inf] * (steps + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        for i in range(n):
            for j in range(steps):
                if dp[i][j] < inf:
                    # 枚举新的字符串 s[i] 到 s[k]，注意，所有长度为 1 的字符串不满足条件
                    for k in range(i + 1, n):
                        dp[k+1][j+1] = min(dp[k+1][j+1], dp[i][j] + calc[i][k])
        return dp[-1][-1]

参考：LeetCode