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;
}
}