周赛354
半个小时过了前三题，第四题超时看了好久，没看到限制字符串的长度最大只有10
特殊元素平方和【LC2778】
给你一个下标从 1 开始、长度为 n 的整数数组 nums 。
对 nums 中的元素 nums[i] 而言，如果 n 能够被 i 整除，即 n % i == 0 ，则认为 num[i] 是一个 特殊元素 。
返回 nums 中所有 特殊元素 的 平方和 。
- 思路
简单模拟 - 实现
class Solution { public int sumOfSquares(int[] nums) { int n = nums.length; int res = 0; for (int i = 0; i < n; i++){ if (n % (i + 1) == 0){ res += nums[i] * nums[i]; } } return res; } }
数组的最大美丽值【LC2779】
给你一个下标从 0 开始的整数数组
nums和一个 非负 整数k。在一步操作中，你可以执行下述指令：
- 在范围
[0, nums.length - 1]中选择一个 此前没有选过 的下标i。- 将
nums[i]替换为范围[nums[i] - k, nums[i] + k]内的任一整数。数组的 美丽值 定义为数组中由相等元素组成的最长子序列的长度。
对数组
nums执行上述操作任意次后，返回数组可能取得的 最大 美丽值。**注意：**你 只 能对每个下标执行 一次 此操作。
数组的 子序列 定义是：经由原数组删除一些元素（也可能不删除）得到的一个新数组，且在此过程中剩余元素的顺序不发生改变。
- 思路：差分+前缀和
每个nums[i]可以替换为范围[nums[i] - k, nums[i] + k]内的任一整数，因此可以使用差分数组记录能被修改至每个区间的整数个数，最后将其累加，求出能修改至某个值的最大个数返回即可 - 实现
class Solution { public int maximumBeauty(int[] nums, int k) { // 每个数组能改变的范围[nums[i]-k, nums[i] + k]->差分统计->前缀和还原 求最大值 int mn = Integer.MAX_VALUE, mx = Integer.MIN_VALUE; int n = nums.length; for (int i = 0; i < n; i++){ mn = Math.min(mn, nums[i] - k); mx = Math.max(mx, nums[i] + k); } // mn负数-mn mx -= mn; int[] d = new int[mx + 2];//[0, mx] [mn, mx]->[0, mx-mn] for (int num : nums){ int l = num - k - mn, r = num + k - mn; d[l] += 1; d[r + 1] -= 1; } int res = 0, sum = 0; for (int i = 0; i <= mx; i++){ sum += d[i]; res = Math.max(res, sum); } return res; } }
合法分割的最小下标【LC2780】
如果元素
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 。
- 思路
- 分割数组后，分割后的数组的支配元素仍和原数组相等。
- 先遍历数组，找到数组的支配元素及其出现次数
- 然后枚举分割位置，记录分割数组中支配元素的次数，如果分割后的数组合法，那么返回当前分割点
- 实现
class Solution { public int minimumIndex(List<Integer> nums) { // 分割数组使分割后数组的支配元素和原数组相等 Map<Integer,Integer> map = new HashMap<>(); int val = -1, mx = -1; int n = nums.size(); for (int i = 0; i < n; i++){ int num = nums.get(i); map.put(num, map.getOrDefault(num, 0) + 1); if (map.get(num) > mx){ val = num; mx = map.get(num); } } mx = map.get(val); int l = 0, r = mx; for (int i = 0; i < n - 1; i++){ if (nums.get(i) == val){// [0, i][i + 1, n - 1] l++; r--; } if (l * 2 > (i + 1) && r * 2 > (n - i - 1)){ return i; } } return -1; } }
最长合法子字符串的长度【LC2781】
给你一个字符串
word和一个字符串数组forbidden。如果一个字符串不包含
forbidden中的任何字符串，我们称这个字符串是 合法 的。
请你返回字符串 word 的一个 最长合法子字符串 的长度。
子字符串 指的是一个字符串中一段连续的字符，它可以为空。
区间dp+字符串哈希[TLE]
我就是个努力优化的小废物hhh 刚开始写思路的时候，想到了用双指针找，最后直接用区间dp了
class Solution { int base = 7; public int longestValidSubstring(String word, List<String> forbidden) { // 字符串哈希 + 区间dp // dp[i][j]:字符串s[i, j]是否是合法字符串 // 使用字符串哈希求出forbidden中的值，并快速求出子字符串的哈希值，快速判断是否存在子字符串 // 使用双指针求出最长长度 int n = word.length(); long[] h = new long[n + 1]; long[] p = new long[n + 1]; p[0] = 1L; for (int i = 1; i <= n; i++){ h[i] = h[i - 1] * base + word.charAt(i - 1); p[i] = p[i - 1] * base; } Set<Long> ff = new HashSet<>(); for (String s : forbidden){ ff.add(hash(s)); } boolean[][] dp = new boolean[n][n]; int res = 0; for (int len = 1; len <= n; len++){ for (int l = 0; l + len - 1 < n; l++){ int r = l + len - 1; dp[l][r] |= r - 1 >= 0 ? dp[l][r - 1] : false; dp[l][r] |= l + 1 < n ? dp[l + 1][r] : false; if (ff.contains(hash(l, r, h, p))){ dp[l][r] = true;// 包含 } if (!dp[l][r]){ res = len; } if (res == n){ return res; } } } return res; } private long hash(int l , int r, long[] h, long[] p){ return h[r + 1] - h[l] * p[r - l + 1]; } private long hash(String s){ int n = s.length(); long res = 0L; for (int i = 0; i < n; i++){ res = res * base + s.charAt(i); } return res; } }
哈希表+同向双指针
- 思路：哈希表+同向双指针
- 合法字符串：字符串中不含有forbidden中的任一字符串
- 双指针：固定左端点，枚举右端点，判断是否存在以右端点为结尾的子字符串出现在forbidden中，如果存在，那么右移左指针至不存在的位置。
class Solution { public int longestValidSubstring(String word, List<String> forbidden) { var fb = new HashSet<String>(); fb.addAll(forbidden); int ans = 0, left = 0, n = word.length(); for (int right = 0; right < n; right++) { for (int i = right; i >= left && i > right - 10; i--) { if (fb.contains(word.substring(i, right + 1))) { left = i + 1; // 当子串右端点 >= right 时，合法子串一定不能包含 word[i] break; } } ans = Math.max(ans, right - left + 1); } return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/length-of-the-longest-valid-substring/solutions/2345796/ha-xi-biao-shuang-zhi-zhen-pythonjavacgo-bcez/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
