LeetCode Contest 390

100245. 每个字符最多出现两次的最长子字符串

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的 最大 长度。

测试样例：

输入：s = "bcbbbcba"

输出：4

解释：以下子字符串长度为 4，并且每个字符最多出现两次："bcbbbcba"。

解答：s.length <= 100, 直接无脑暴力。

class Solution {
    public int maximumLengthSubstring(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); ++i) {
            for (int j = i; j < s.length(); ++j) {
                if (isValid(s, i, j)) {
                    res = Math.max(res, j - i + 1);
                }
            }
        }
        return res;
    }

    private boolean isValid(String s, int st, int ed) {
        int[] count = new int[256];
        for (int i = st; i <= ed; ++i) {
            char c = s.charAt(i);
            count[c] += 1;
            if (count[c] > 2) {
                return false;
            }
        }
        return true;
    }
}

100228. 执行操作使数据元素之和大于等于 K

给你一个正整数 k 。最初，你有一个数组 nums = [1] 。

你可以对数组执行以下 任意 操作 任意 次数（可能为零）：

• 选择数组中的任何一个元素，然后将它的值 增加 1 。
• 复制数组中的任何一个元素，然后将它附加到数组的末尾。

返回使得最终数组元素之 和 大于或等于 k 所需的 最少 操作次数。

测试样例：

输入：k = 11

输出：5

解释：可以对数组 nums = [1] 执行以下操作：

• 将元素的值增加 1 三次。结果数组为 nums = [4] 。
• 复制元素两次。结果数组为 nums = [4,4,4] 。

最终数组的和为 4 + 4 + 4 = 12 ，大于等于 k = 11 。执行的总操作次数为 3 + 2 = 5 。

解答：最优的方案一定是先进行一定数量的操作1，然后进行操作2（如果不是先1后2，那么将操作2放在操作1之后，总和必然大于混合的操作）。这样，直接枚举一定数量的次数即可。

class Solution {
    public int minOperations(int k) {
        int min = k - 1;
        for (int i = 1; i < k; ++i) {
            int num = i + 1;
            int time = k / num + (k % num == 0 ? 0 : 1) - 1;
            min = Math.min(i + time, min);
        }
        return min;
    }
}

100258. 最高频率的 ID

你需要在一个集合里动态记录 ID 的出现频率。给你两个长度都为 n 的整数数组 nums 和 freq ，nums 中每一个元素表示一个 ID ，对应的 freq 中的元素表示这个 ID 在集合中此次操作后需要增加或者减少的数目。

• 增加 ID 的数目：如果 freq[i] 是正数，那么 freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会添加到集合中。
• 减少 ID 的数目：如果 freq[i] 是负数，那么 -freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会从集合中删除。

请你返回一个长度为 n 的数组 ans ，其中 ans[i] 表示第 i 步操作后出现频率最高的 ID 数目 ，如果在某次操作后集合为空，那么 ans[i] 为 0 。

测试样例：

输入：nums = [2,3,2,1], freq = [3,2,-3,1]

输出：[3,3,2,2]

解释：

• 第 0 步操作后，有 3 个 ID 为 2 的元素，所以 ans[0] = 3 。
• 第 1 步操作后，有 3 个 ID 为 2 的元素和 2 个 ID 为 3 的元素，所以 ans[1] = 3 。
• 第 2 步操作后，有 2 个 ID 为 3 的元素，所以 ans[2] = 2 。
• 第 3 步操作后，有 2 个 ID 为 3 的元素和 1 个 ID 为 1 的元素，所以 ans[3] = 2 。

解答：对频率用TreeMap计数，每次读取最高频次的数。

class Solution {
    public long[] mostFrequentIDs(int[] nums, int[] freq) {
        int len = nums.length;
        Map<Integer, Long> countMap = new HashMap<>();
        TreeMap<Long, Integer> freqMap = new TreeMap<>();
        freqMap.put(0L, 0);
        long[] res = new long[len];
        for (int i = 0; i < len; ++i) {
            int n = nums[i], f = freq[i];
            long oldFreq = countMap.getOrDefault(n, 0L);
            if (oldFreq != 0) {
                int ct = freqMap.get(oldFreq);
                if (ct == 1) {
                    freqMap.remove(oldFreq);
                } else {
                    freqMap.put(oldFreq, ct - 1);
                }
            }
            oldFreq += f;
            countMap.put(n, oldFreq);
            freqMap.put(oldFreq, freqMap.getOrDefault(oldFreq, 0) + 1);
            res[i] = freqMap.lastKey();
        }
        return res;
    }
}

100268. 最长公共后缀查询

给你两个字符串数组 wordsContainer 和 wordsQuery 。

对于每个 wordsQuery[i] ，你需要从 wordsContainer 中找到一个与 wordsQuery[i] 有 最长公共后缀 的字符串。如果 wordsContainer 中有两个或者更多字符串有最长公共后缀，那么答案为长度 最短 的。如果有超过两个字符串有 相同 最短长度，那么答案为它们在 wordsContainer 中出现 更早 的一个。

请你返回一个整数数组 ans ，其中 ans[i]是 wordsContainer中与 wordsQuery[i] 有 最长公共后缀 字符串的下标。

测试样例：

输入：wordsContainer = ["abcd","bcd","xbcd"], wordsQuery = ["cd","bcd","xyz"]

输出：[1,1,1]

解释：我们分别来看每一个 wordsQuery[i] ：

• 对于 wordsQuery[0] = "cd" ，wordsContainer 中有最长公共后缀 "cd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
• 对于 wordsQuery[1] = "bcd" ，wordsContainer 中有最长公共后缀 "bcd" 的字符串下标分别为 0 ，1 和 2 。这些字符串中，答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。
• 对于 wordsQuery[2] = "xyz" ，wordsContainer 中没有字符串跟它有公共后缀，所以最长公共后缀为 "" ，下标为 0 ，1 和 2 的字符串都得到这一公共后缀。这些字符串中， 答案是下标为 1 的字符串，因为它的长度为 3 ，是最短的字符串。

解答：这周手速场了，利用TrieTree可以快速搜索最长后缀和。唯一对TrieTree唯一需要修改的，就是记录一下当前后缀，符合最短字符串（或者最短的情况下，最早出现的序号）。

class Solution {
    private class TrieNode {
        HashMap<Character, TrieNode> next;
        Comparator<Integer> comparator;
        int best;

        public TrieNode(Comparator<Integer> compare) {
            next = new HashMap<>();
            best = -1;
            this.comparator = compare;
        }

        public void updateBest(int val) {
            if (best == -1 || comparator.compare(best, val) > 0) {
                best = val;
            }
        }
    }

    private class IntegerCompare implements Comparator<Integer> {
        private String[] wordsContainer;

        public IntegerCompare(String[] wordsContainer) {
            this.wordsContainer = wordsContainer;
        }

        @Override
        public int compare(Integer o1, Integer o2) {
            if (wordsContainer[o1].length() != wordsContainer[o2].length()) {
                return Integer.compare(wordsContainer[o1].length(), wordsContainer[o2].length());
            } else {
                return o1.compareTo(o2);
            }
        }
    }

    public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
        IntegerCompare compare = new IntegerCompare(wordsContainer);
        TrieNode root = new TrieNode(compare);
        for (int i = 0; i < wordsContainer.length; ++i) {
            TrieNode tmp = root;
            root.updateBest(i);
            for (int j = wordsContainer[i].length() - 1; j >= 0; --j) {
                char c = wordsContainer[i].charAt(j);
                if (!tmp.next.containsKey(c)) {
                    tmp.next.put(c, new TrieNode(compare));
                }
                tmp = tmp.next.get(c);
                tmp.updateBest(i);
            }
        }

        int[] res = new int[wordsQuery.length];
        for (int i = 0; i < wordsQuery.length; ++i) {
            String w = wordsQuery[i];
            TrieNode tmp = root;
            res[i] = tmp.best;
            for (int j = w.length() - 1; j >= 0; --j) {
                char c = w.charAt(j);
                if (tmp.next.containsKey(c)) {
                    tmp = tmp.next.get(c);
                    res[i] = tmp.best;
                } else {
                    break;
                }
            }
        }
        return res;
    }
}