LeetCode Contest 389

100248. Existence of a Substring in a String and Its Reverse

给你一个字符串 s ，请你判断字符串 s 是否存在一个长度为 2 的子字符串，在其反转后的字符串中也出现。

如果存在这样的子字符串，返回 true；如果不存在，返回 false 。

测试样例：

输入：s = "leetcode"

输出：true

解释：子字符串 "ee" 的长度为 2，它也出现在 reverse(s) == "edocteel" 中。

解答：无脑暴力。

class Solution {
    public boolean isSubstringPresent(String s) {
        String reverse = new StringBuilder(s).reverse().toString();
        for (int i = 0; i < s.length(); ++i) {
            StringBuilder tmp = new StringBuilder();
            for (int j = i; j < s.length(); ++j) {
                tmp.append(s.charAt(j));
                if (j > i && reverse.contains(tmp)) {
                    return true;
                }
            }
        }
        return false;
    }
}

100236. Count Substrings Starting and Ending with Given Character

给你一个字符串 s 和一个字符 c 。返回在字符串 s 中并且以 c 字符开头和结尾的非空子字符串的总数。

测试样例：

输入：s = "abada", c = "a"

输出：6

解释：以 "a" 开头和结尾的子字符串有： "abada"、"abada"、"abada"、"abada"、"abada"、"abada"。

解答：排列组合题。

class Solution {
    public long countSubstrings(String s, char c) {
        int count = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == c) {
                ++count;
            }
        }
        if (count == 0) {
            return 0;
        }
        return (1L + count) * count / 2;
    }
}

100255. Minimum Deletions to Make String K-Special

给你一个字符串 word 和一个整数 k。

如果 |freq(word[i]) - freq(word[j])| <= k 对于字符串中所有下标 i 和 j 都成立，则认为 word 是 k 特殊字符串。

此处，freq(x) 表示字符 x 在 word 中的出现频率，而 |y| 表示 y 的绝对值。

返回使 word 成为 k 特殊字符串 需要删除的字符的最小数量。

测试样例：

输入：word = "aabcaba", k = 0

输出：3

解释：可以删除 2 个 "a" 和 1 个 "c" 使 word 成为 0 特殊字符串。word 变为 "baba"，此时 freq('a') == freq('b') == 2。

解答：这道题目需要注意，除了把出现频次较大的数减小来满足要求，也能直接把出现频次较小的数字完全干掉来完成要求。小写字母一共就26个，排序之后，直接暴力枚举两种情况，就能获取结果。

class Solution {
    public int minimumDeletions(String word, int k) {
        int[] count = new int[26];
        for (int i = 0; i < word.length(); ++i) {
            count[word.charAt(i) - 'a'] += 1;
        }
        Arrays.sort(count);
        int res = word.length();
        int prefixSum = 0;
        for (int i = 0; i < 26; ++i) {
            int result = prefixSum;
            for (int j = i + 1; j < 26; ++j) {
                if (count[j] > count[i] + k) {
                    result += count[j] - count[i] - k;
                }
            }
            res = Math.min(res, result);
            prefixSum += count[i];
        }
        return res;
    }
}

100227. Minimum Moves to Pick K Ones

给你一个下标从 0 开始的二进制数组 nums，其长度为 n ；另给你一个 正整数 k 以及一个 非负整数 maxChanges 。

灵茶山艾府在玩一个游戏，游戏的目标是让灵茶山艾府使用 最少 数量的 行动 次数从 nums 中拾起 k 个 1 。游戏开始时，灵茶山艾府可以选择数组 [0, n - 1] 范围内的任何索引index 站立。如果 nums[index] == 1 ，灵茶山艾府就会拾起一个 1 ，并且 nums[index] 变成0（这 不算 作一次行动）。之后，灵茶山艾府可以执行 任意数量 的 行动（包括零次），在每次行动中灵茶山艾府必须 恰好 执行以下动作之一：

• 选择任意一个下标 j != index 且满足 nums[j] == 0 ，然后将 nums[j] 设置为 1 。这个动作最多可以执行 maxChanges 次。
• 选择任意两个相邻的下标 x 和 y（|x - y| == 1）且满足 nums[x] == 1, nums[y] == 0 ，然后交换它们的值（将 nums[y] = 1 和 nums[x] = 0）。如果 y == index，在这次行动后灵茶山艾府拾起一个 1 ，并且 nums[y] 变成 0 。

返回灵茶山艾府拾起 恰好 k 个 1 所需的 最少 行动次数。

测试样例：

输入：nums = [1,1,0,0,0,1,1,0,0,1], k = 3, maxChanges = 1

输出：3

解释：如果游戏开始时灵茶山艾府在 index == 1 的位置上，按照以下步骤执行每个动作，他可以利用 3 次行动拾取 3 个 1 ：

• 游戏开始时灵茶山艾府拾取了一个 1 ，nums[1] 变成了 0。此时 nums 变为 [1,0,0,0,0,1,1,0,0,1] 。
• 选择 j == 2 并执行第一种类型的动作。nums 变为 [1,0,1,0,0,1,1,0,0,1]
• 选择 x == 2 和 y == 1 ，并执行第二种类型的动作。nums 变为 [1,1,0,0,0,1,1,0,0,1] 。由于 y == index，灵茶山艾府拾取了一个 1 ，nums 变为 [1,0,0,0,0,1,1,0,0,1] 。
• 选择 x == 0 和 y == 1 ，并执行第二种类型的动作。nums 变为 [0,1,0,0,0,1,1,0,0,1] 。由于 y == index，灵茶山艾府拾取了一个 1 ，nums 变为 [0,0,0,0,0,1,1,0,0,1] 。

请注意，灵茶山艾府也可能执行其他的 3 次行动序列达成拾取 3 个 1 。

解答：这道题目难度有点大。有些特殊情况，我不知道怎么处理，代码里面就类似hard code了。特殊的情况指1,1,1这种，因为只要用操作2就能完成一次1获取，比直接线增加一个1，然后操作2获取更快。这种情况我就特殊处理了。

其他情况就比较简单的，我们只要寻找一个区间能够满足sum(i...j) + maxChanges >= k，然后取当中那个1出现的位置，计算操作数就行了。涉及到绝对值累和，可以利用前缀和来完成。

class Solution {
    public long minimumMoves(int[] nums, int k, int maxChanges) {
        int n = nums.length, maxC = maxContinue(nums);
        if (maxC == 0) {
            return 2L * k;
        } else if (maxC >= k) {
            return k - 1;
        } else if (maxChanges + maxC >= k) {
            return maxC - 1 + (k - maxC) * 2L;
        } else {
            List<Long> prefixSum = new ArrayList<>();
            List<Long> posMem = new ArrayList<>();
            prefixSum.add(0L);
            for (int i = 0; i < nums.length; ++i) {
                if (nums[i] == 1) {
                    posMem.add((long) i);
                    prefixSum.add(prefixSum.get(prefixSum.size() - 1) + i);
                }
            }
            int st = 0, ed = k - maxChanges - 1;
            long res = Long.MAX_VALUE;
            while (ed < posMem.size()) {
                int mid = (st + ed) / 2;
                long sumLeft = prefixSum.get(mid + 1) - prefixSum.get(st);
                long sumRight = prefixSum.get(ed + 1) - prefixSum.get(mid + 1);
                long result = (mid - st + 1L) * posMem.get(mid) - sumLeft + sumRight - (ed - mid) * posMem.get(mid);
                result += 2L * maxChanges;
                res = Math.min(res, result);
                ++st;
                ++ed;
            }
            return res;
        }
    }

    private int maxContinue(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; ++i) {
            int count = 0;
            if (nums[i] == 1) {
                ++count;
                if (i - 1 >= 0 && nums[i - 1] == 1) {
                    ++count;
                }
                if (i + 1 < nums.length && nums[i + 1] == 1) {
                    ++count;
                }
            }
            res = Math.max(res, count);
        }
        return res;
    }
}