周赛354（模拟、差分、排序+双指针、枚举）

周赛354

2778. 特殊元素平方和

难度简单1

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

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

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

示例 1：

输入：nums = [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 。  

示例 2：

输入：nums = [2,7,1,19,18,3]
输出：63
解释：nums 中共有 4 个特殊元素：nums[1] ，因为 6 被 1 整除；nums[2] ，因为 6 被 2 整除；nums[3] ，因为 6 被 3 整除；以及 nums[6] ，因为 6 被 6 整除。 
因此，nums 中所有元素的平方和等于 nums[1] * nums[1] + nums[2] * nums[2] + nums[3] * nums[3] + nums[6] * nums[6] = 2 * 2 + 7 * 7 + 1 * 1 + 3 * 3 = 63 。 

提示：

• 1 <= nums.length == n <= 50
• 1 <= nums[i] <= 50

模拟

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

python

class Solution:
    def sumOfSquares(self, nums: List[int]) -> int:
        ans, n = 0, len(nums)
        for i, v in enumerate(nums):
            if n % (i+1) == 0:
                ans += v * v
        return ans

2779. 数组的最大美丽值

难度中等9

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

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

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

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

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

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

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

示例 1：

输入：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 是我们可以得到的由相等元素组成的最长子序列长度。

示例 2：

输入：nums = [1,1,1,1], k = 10
输出：4
解释：在这个示例中，我们无需执行任何操作。
数组 nums 的美丽值是 4（整个数组）。

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i], k <= 105

排序 + 双指针

https://leetcode.cn/problems/maximum-beauty-of-an-array-after-applying-operation/solution/pai-xu-shuang-zhi-zhen-by-endlesscheng-hbqx/

由于选的是子序列，且子序列的元素都相等，所以元素顺序对答案没有影响，可以先对数组排序。

由于替换操作替换的是一个连续范围内的数，所以排序后，选出的子序列必然也是一段连续子数组。

那么问题变成：「找最长的连续子数组，其最大值减最小值不超过 2k」，只要子数组满足这个要求，其中的元素都可以变成同一个数。

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        if(nums.length == 1) return 1;
        Arrays.sort(nums);
        int ans = 0, left = 0;
        for(int right = 1; right < nums.length; right++){
            while(nums[right] - nums[left] > 2*k)
                left++;
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

差分

https://leetcode.cn/problems/maximum-beauty-of-an-array-after-applying-operation/solution/python3javac-er-fen-hua-dong-chuang-kou-rdkls/

对于某个位置i,元素x = nums[i],由于每个数字的操作可以在[x - k, x + k]内变动。我们可以理解为x可以变为其中的任意一个数，即：[x - k, x + k]区间内的数字出现次数都增加1。可以使用差分数组记录区间内的修改情况。

最后只需要对差分数组求前缀和，得到的即为每个元素的出现频率。记录频率最大值作为答案即可。

差分数组的大小与值域有关。

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        int n = nums.length;
        int[] d = new int[100005];
        for(int i = 0; i < n; i++){
            int x = nums[i];
            int l = Math.max(x - k, 0);
            int r = Math.min(x + k, 100000);
            d[l] += 1;
            d[r+1] -= 1;
        }
        int res = 0;
        for(int i = 1; i < d.length; i++){
            d[i] += d[i-1];
            res = Math.max(res, d[i]);
        }
        return res;
    }
}

离散差分

朴素差分中，差分数组大小随着值域的增大而增大。可以采用字典（哈希表）进行离散化差分。优化空间复杂度（对时间也有优化，求差分数组的时候只需要求离散的点）。

为何能用离散化差分？

个人的理解： 连续的差分数组求前缀和之后的形式诸如：

• 1111110000011111222223333

其中可以看到其实差分数组是分为一段一段的（每个加黑的数字为段的开始，到下一个加黑数字为止）。而离散化的差分可以理解为只处理这些加黑的值（只存储发生突变的位置），即

• 1 0 1 2 3

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        Map<Integer, Integer> d = new TreeMap<>();
        for(int i = 0; i < nums.length; i++){
            int x = nums[i];
            int l = Math.max(x - k, 0);
            int r = Math.min(x + k, 100000);
            d.merge(l, 1, Integer::sum);
            d.merge(r+1, -1, Integer::sum);
        }
        int res = 0, sum_d = 0;
        for(Map.Entry<Integer, Integer> entry : d.entrySet()){
            sum_d += entry.getValue();
            res = Math.max(res, sum_d);
        }
        return res;
    }
}

2780. 合法分割的最小下标

难度中等5

如果元素 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 。

示例 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 是合法分割中的最小下标。

示例 2：

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

示例 3：

输入：nums = [3,3,3,3,7,2,2]
输出：-1
解释：没有合法分割。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• nums 有且只有一个支配元素。

枚举

https://leetcode.cn/problems/minimum-index-of-a-valid-split/solution/jie-lun-zheng-ming-mei-ju-by-endlesschen-w156/

结论：分割出的两个数组的支配元素就是原数组的支配元素。

class Solution {
    public int minimumIndex(List<Integer> nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        // 求出众数more 和 出现次数total
        int more = 0, total = 0;
        for(int x : nums){
            map.put(x, map.getOrDefault(x, 0) + 1);
            if(map.get(x) * 2 > nums.size()){
                more = x;
                total = map.get(x);
            }
        }
        int cnt = 0;
        for(int i = 0; i < nums.size(); i++){
            if(nums.get(i) == more) cnt++;
            if(cnt * 2 > i+1 && (total - cnt) * 2 > nums.size() - i - 1)
                return i;
        }
        return -1;
    }
}

2781. 最长合法子字符串的长度

难度困难7

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

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

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

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

示例 1：

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

示例 2：

输入：word = "leetcode", forbidden = ["de","le","e"]
输出：4
解释：总共有 11 个合法子字符串："l" ，"t" ，"c" ，"o" ，"d" ，"tc" ，"co" ，"od" ，"tco" ，"cod" 和 "tcod" 。最长合法子字符串的长度为 4 。
所有其他子字符串都至少包含 "de" ，"le" 和 "e" 之一。

提示：

• 1 <= word.length <= 105
• word 只包含小写英文字母。
• 1 <= forbidden.length <= 105
• 1 <= forbidden[i].length <= 10
• forbidden[i] 只包含小写英文字母。

字典树 + 双指针

考虑到答案要求子字符串的长度，可使用双指针来枚举子串右端点。

考虑到要检查以 i 为右端点的字串是否包含非法字符串，考虑使用字典树倒序保存所有forbidden禁止词，然后检查以 i 为右端点的字串是否以禁止词为开头

class Solution {
    public int longestValidSubstring(String word, List<String> forbidden) {
        Trie trie = new Trie();
        for(String f : forbidden)
            // 将禁止词forbidden倒序插入字典树
            trie.insert(new StringBuilder(f).reverse().toString());
        int left = 0, ans = 0;
        for(int right = 0; right < word.length(); right++){
            if(trie.search(word.substring(right, right+1))){
                left = right + 1;
                continue;
            }
            while(trie.startsWith(word.substring(left, right+1))){
                left += 1;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

class Trie {
    class TrieNode{//字典树的结点数据结构
		boolean end;//是否是单词末尾的标识
		int pass; // 经过这个结点的次数（根据需要设置这个变量）
		TrieNode[] child; //26个小写字母的拖尾
		public TrieNode(){
			end = false;
			pass = 0;
			child = new TrieNode[26];
		}
	}

	TrieNode root;//字典树的根节点。
	
    public Trie() {
        root = new TrieNode();
    }

    public void insert(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
			//若当前结点下没有找到要的字母，则新开结点继续插入
            if (p.child[u] == null) p.child[u] = new TrieNode();
            p = p.child[u]; 
            p.pass++;
        }
        p.end = true;
    }

    public boolean search(String s) {
        TrieNode p = root;
        for(int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.child[u] == null) return false;//变化点（根据题意）
            p = p.child[u]; 
        }
        return p.end;
    }

    public boolean startsWith(String s) {
        TrieNode p = root;
        // 倒序检查，即s[left: right] 从right开始检查
        for(int i = s.length()-1; i >= 0; i--) {
            int u = s.charAt(i) - 'a';
            if (p.child[u] == null) return false;
            // 检查是否以禁止词为前缀，若存在以禁止词为前缀，则非法
            if(p.child[u].end == true) return true;
            p = p.child[u]; 
        }
        return false;
    }
}

哈希表 + 双指针

由于forbidden[i] 的长度不超过 10。

直接枚举 区间[left, right]中以 [right-10, right]为起点，right为终点的字串是否为禁止词就可以了文章来源地址https://www.toymoban.com/news/detail-574689.html

class Solution {
    public int longestValidSubstring(String word, List<String> forbidden) {
        Set<String> fb = new HashSet<>();
        fb.addAll(forbidden);
        int left = 0, ans = 0;
        for(int right = 0; right < word.length(); right++){
            for(int i = right; i >= left && i > right - 10; i--){
                if(fb.contains(word.substring(i, right + 1))){
                    left = i+1;
                    break;
                }
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

到了这里，关于周赛354（模拟、差分、排序+双指针、枚举）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！