力扣 第 368 场周赛

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

给你一个下标从 0 开始的整数数组 nums 。

如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：

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

---

复杂度：O(N)
思路：前后缀分解。一个数组记录前缀最小值，一个数组记录后缀最小值。

class Solution {
    public int minimumSum(int[] nums) {
        int n = nums.length;        
        // 这两个都取最小值
        int[] pre = new int[n];
        pre[0] = nums[0];        
        int[] suf = new int[n];
        suf[n-1] = nums[n-1];        
        for(int i=1; i<n; i++) {
            pre[i] = Math.min(nums[i], pre[i-1]);
        }        
        for(int i=n-2; i>=0; i--) {
            suf[i] = Math.min(nums[i], suf[i+1]);
        }
        int ans = Integer.MAX_VALUE;
        for(int i=1; i<n-1; i++) {
            if(pre[i-1]<nums[i] && nums[i]>suf[i+1]) {
                ans = Math.min(ans, pre[i-1]+nums[i]+suf[i+1]);
            }
        }
        if(ans == Integer.MAX_VALUE) {
            return -1;
        }      
        return ans;       
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2910. 合法分组的最少组数

给你一个长度为 n 下标从 0 开始的整数数组 nums 。

我们想将下标进行分组，使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。

如果以下条件成立，我们说这个分组方案是合法的：

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

---

  复杂度：O(N)
  思路：使用HashMap统计每个数字出现的次数，map<数字，出现次数>。由于分组后，两个组的成员数相差不能大于1。所以每个组的成员数最大为min{出现次数}，最小为1，K为出现次数的最小值。由大至小遍历上述的K值，c为当前组的值，q=c/k为当前组可以分的最少组，r=c%k为剩余的人数，显然q>=r时候，该次分组才是有效的。

class Solution {
    public int minGroupsForValidAssignment(int[] nums) {
        Map<Integer, Integer> map = new HashMap();
        for(int num:nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        int minK = Integer.MAX_VALUE;
        for(Map.Entry<Integer, Integer> entry:map.entrySet()) {
            minK = Math.min(minK, entry.getValue());
        }
        int ans = 0;
        int res = Integer.MAX_VALUE;
        boolean f = true;
        for(int k=minK; k>=1; k--) {
            ans = 0;
            f = true;
            for(Map.Entry<Integer, Integer> entry:map.entrySet()) {
                int c = entry.getValue();
                int q = c/k;
                int r = c%k;
                if(q<r) {
                    f = false;
                    break;
                }
                ans = ans + (int)Math.ceil((double)c/(k+1));
            }
            if(f == true) {
                res = Math.min(res, ans);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

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

请你返回一个整数，表示需要修改的 最少 字符数目。

注意：

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

---

class Solution {
    private static Integer C = 202;
    private static List<Integer>[] divisors = new ArrayList[C];

    static{
        Arrays.setAll(divisors, e-> new ArrayList<>());
        for(int i=1; i<C; i++) {
            for(int j=i*2; j<C; j++) {
                divisors[j].add(i);
            }
        }
    }

    private int[][] modify;
    public int minimumChanges(String s, int k) {
        int n = s.length();
        // 表示从i到j需要的变换次数
        modify = new int[n][n];
        for(int i=0; i<n; i++) {
            for(int j=i+1; j<n; j++) {
                modify[i][j] = getModify(s.substring(i, j+1));
            }
        }

        /**
        dp[i][j]: i表示剩余切割的次数，j表示要处理的字符串的最后一位
        dp[i][j] = dp[]
         */
        int[][] memo = new int[k][n];
        for(int i=0; i<k; i++) {
            Arrays.setAll(memo[i],e-> -1);
        }
        
        return dfs(k-1, n-1, modify, memo);
    }

    public Integer dfs(int i, int j, int[][] modify, int[][] memo) {
        // 第一种i=0
        if(i == 0) {
            return modify[0][j];
        }
        if(memo[i][j] != -1) {
            return memo[i][j];
        }
        int min = Integer.MAX_VALUE;
        for(int L = i*2; L<j; L++) {
            min = Math.min(min, dfs(i-1, L-1, modify, memo)+modify[L][j]);
        }
        return memo[i][j] = min;
    }

    private Integer getModify(String s) {
        int n = s.length();
        int ans = Integer.MAX_VALUE;
        for(int d:divisors[n]) {
            int cnt = 0;
            for(int i0=0; i0<d; i0++) {
                for(int i=i0, j=n-1-i0; i<j; i=i+i0, j=j-i0) {
                    if(s.charAt(i)!=s.charAt(j)) {
                        cnt ++;
                    }
                }
            }
            ans = Math.min(ans, cnt);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68