LeetCode Contest 354

6889. Sum of Squares of Special Elements

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

对 nums 中的元素 nums[i] 而言，如果 n 能够被 i 整除，即 n % i == 0 ，则认为 num[i] 是一个 特殊元素 。

返回 nums 中所有 特殊元素 的 平方和 。

测试样例：

输入：num = [1,2,3,4]

输出：21

解释：
nums 中共有 3 个特殊元素：nums[1] ，因为 4 被 1 整除；nums[2] ，因为 4 被 2 整除；以及 nums[4] ，因为 4 被 4 整除。 因此，nums 中所有元素的平方和等于 nums[1] nums[1] + nums[2] nums[2] + nums[4] nums[4] = 1 1 + 2 2 + 4 4 = 21 。

解答：按照题意暴力运算就行了

class Solution {
    public int sumOfSquares(int[] nums) {
        int res = 0, n = nums.length;
        for (int i = 0; i < nums.length; ++i) {
            if (n % (i + 1) == 0) {
                res += (nums[i] * nums[i]);
            }
        }
        return res;
    }
}

6929. Maximum Beauty of an Array After Applying Operation

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

在一步操作中，你可以执行下述指令：

• 在范围 [0, nums.length - 1] 中选择一个 此前没有选过 的下标 i 。
• 将 nums[i] 替换为范围 [nums[i] - k, nums[i] + k] 内的任一整数。

数组的 美丽值 定义为数组中由相等元素组成的最长子序列的长度。

对数组 nums 执行上述操作任意次后，返回数组可能取得的 最大 美丽值。

注意：你 只 能对每个下标执行 一次 此操作。

数组的 子序列 定义是：经由原数组删除一些元素（也可能不删除）得到的一个新数组，且在此过程中剩余元素的顺序不发生改变。

测试样例：

输入：nums = [4,6,1,2], k = 2

输出：3

解释：
在这个示例中，我们执行下述操作：

• 选择下标 1 ，将其替换为 4（从范围 [4,8] 中选出），此时 nums = [4,4,1,2] 。
• 选择下标 3 ，将其替换为 4（从范围 [0,4] 中选出），此时 nums = [4,4,1,4] 。

执行上述操作后，数组的美丽值是 3（子序列由下标 0 、1 、3 对应的元素组成）。可以证明 3 是我们可以得到的由相等元素组成的最长子序列长度。

解答：排序后，可以利用双指针来判断某个数最大的覆盖范围。

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        Arrays.sort(nums);
        int st = 0, ed = 0, res = 0;
        while (ed < nums.length) {
            while (ed < nums.length && nums[ed] - nums[st] <= 2 * k) {
                ++ed;
            }
            res = Math.max(res, ed - st);
            ++st;
        }
        return res;
    }
}

6927. Minimum Index of a Valid Split

如果元素 x 在长度为 m 的整数数组 arr 中满足 freq(x) * 2 > m ，那么我们称 x 是 支配元素 。其中 freq(x) 是 x 在数组 arr 中出现的次数。注意，根据这个定义，数组 arr 最多 只会有 一个 支配元素。

给你一个下标从 0 开始长度为 n 的整数数组 nums ，数据保证它含有一个支配元素。

你需要在下标 i 处将 nums 分割成两个数组 nums[0, ..., i] 和 nums[i + 1, ..., n - 1] ，如果一个分割满足以下条件，我们称它是 合法 的：

• 0 <= i < n - 1
• nums[0, ..., i] 和 nums[i + 1, ..., n - 1] 的支配元素相同。

这里， nums[i, ..., j] 表示 nums 的一个子数组，它开始于下标 i ，结束于下标 j ，两个端点都包含在子数组内。特别地，如果 j < i ，那么 nums[i, ..., j] 表示一个空数组。

请你返回一个 合法分割 的 最小 下标。如果合法分割不存在，返回 -1 。

测试样例

输入：nums = [1,2,2,2]

输出：2

解释：
我们将数组在下标 2 处分割，得到 [1,2,2] 和 [2] 。数组 [1,2,2] 中，元素 2 是支配元素，因为它在数组中出现了 2 次，且 2 2 > 3 。数组 [2] 中，元素 2 是支配元素，因为它在数组中出现了 1 次，且 1 2 > 1 。两个数组 [1,2,2] 和 [2] 都有与 nums 一样的支配元素，所以这是一个合法分割。下标 2 是合法分割中的最小下标。

解答：利用HashMap，可以快速计算出前缀和后缀的众数。然后遍历前缀和后缀的众数数组，最小左右众数一致的位置就是答案

class Solution {
    public int minimumIndex(List<Integer> nums) {
        int[] arr = new int[nums.size()];
        int offset = 0, len = arr.length;
        for (int n : nums) {
            arr[offset++] = n;
        }

        int[] backward = new int[arr.length];
        HashMap<Integer, Integer> map = new HashMap<>();
        int max = 0, num = -1;
        for (int i = len - 1; i >= 0; --i) {
            int tmp = map.getOrDefault(arr[i], 0) + 1;
            map.put(arr[i], tmp);
            if (tmp > max) {
                max = tmp;
                num = arr[i];
            }
            if (max * 2 > len - i) {
                backward[i] = num;
            }
        }

        map = new HashMap<>();
        max = 0; num = -1;
        for (int i = 0; i < len - 1; ++i) {
            int tmp = map.getOrDefault(arr[i], 0) + 1;
            map.put(arr[i], tmp);
            if (tmp > max) {
                max = tmp;
                num = arr[i];
            }
            if (max * 2 > i + 1 && num == backward[i + 1]) {
                return i;
            }
        }
        return -1;
    }
}

6924. Length of the Longest Valid Substring

给你一个字符串 word 和一个字符串数组 forbidden 。

如果一个字符串不包含 forbidden 中的任何字符串，我们称这个字符串是 合法 的。

请你返回字符串 word 的一个 最长合法子字符串 的长度。

子字符串 指的是一个字符串中一段连续的字符，它可以为空。

测试样例

输入：word = "cbaaaabc", forbidden = ["aaa","cb"]

4

解释：总共有 9 个合法子字符串："c" ，"b" ，"a" ，"ba" ，"aa" ，"bc" ，"baa" ，"aab" 和 "aabc" 。最长合法子字符串的长度为 4 。
其他子字符串都要么包含 "aaa" ，要么包含 "cb" 。

解答：这道题目有一个很重要的提示：1 <= forbidden[i].length <= 10。所以每个位置最多向下遍历10个字符就能判断当前位置开始，是否可以寻找到非法字符串，利用数组保存当前位置开始，可以寻找到的非法字符串长度。利用Trie Tree可以加速寻找。

最后我们从后至前遍历整个数组，并且记录最大的位置与最长长度。

class Solution {
    private class TrieNode{
        boolean isEnd;
        TrieNode[] next;

        public TrieNode(){
            isEnd = false;
            next = new TrieNode[26];
        }
    }

    public void insert(String s, TrieNode root) {
        TrieNode temp = root;
        for (int i = 0; i < s.length(); ++i) {
            int c = s.charAt(i) - 'a';
            if (temp.next[c] == null) {
                temp.next[c] = new TrieNode();
            }
            temp = temp.next[c];
        }
        temp.isEnd = true;
    }

    public int longestValidSubstring(String word, List<String> forbidden) {
        int max = 0;
        TrieNode root = new TrieNode();
        for (String w : forbidden) {
            max = Math.max(w.length(), max);
            insert(w, root);
        }

        int len = word.length();
        int[] foundLength = new int[len];
        Arrays.fill(foundLength, -1);
        for (int i = 0; i < len; ++i) {
            TrieNode tmp = root;
            for (int j = 0; j < max && i + j < len; ++j) {
                int c = word.charAt(i + j) - 'a';
                if (tmp.next[c] != null) {
                    tmp = tmp.next[c];
                } else {
                    break;
                }
                if (tmp.isEnd) {
                    foundLength[i] = j;
                    break;
                }
            }
        }

        int res = 0, last = len;
        for (int i = len - 1; i >= 0; --i) {
            if (foundLength[i] != -1) {
                last = Math.min(last, i + foundLength[i]);
            }
            res = Math.max(res, last - i);
        }
        return res;
    }
}