文章目录
- 竞赛链接
- Q1：2946. 循环移位后的矩阵相似检查
- 竞赛时代码——模拟
- 2947. 统计美丽子字符串 I
- 竞赛时代码——前缀和+暴力枚举
- Q3：2948. 交换得到字典序最小的数组
- 竞赛时代码——排序后判断
- 相似题目——1202. 交换字符串中的元素（使用并查集 哈希表 复原）🐂
- Q4：2949. 统计美丽子字符串 II⭐⭐⭐⭐⭐🚹🐂
- 解法——分解质因子+前缀和+哈希表
- 相似题目列表（前缀和 + 哈希表）
- 560. 和为 K 的子数组
- 974. 和可被 K 整除的子数组
- 1590. 使数组和能被 P 整除
- 523. 连续的子数组和
- 525. 连续数组
- 面试题 17.05. 字母与数字
- 1915. 最美子字符串的数目
- 930. 和相同的二元子数组
- 1371. 每个元音包含偶数次的最长子字符串
- 1542. 找出最长的超赞子字符串
- 成绩记录
竞赛链接
https://leetcode.cn/contest/weekly-contest-373/
Q1：2946. 循环移位后的矩阵相似检查
https://leetcode.cn/problems/matrix-similarity-after-cyclic-shifts/description/
提示：
1 <= mat.length <= 25
1 <= mat[i].length <= 25
1 <= mat[i][j] <= 25
1 <= k <= 50
竞赛时代码——模拟
class Solution {
public boolean areSimilar(int[][] mat, int k) {
int m = mat.length, n = mat[0].length;
for (int i = 0; i < m; ++i) {
if (i % 2 == 1) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] != mat[i][(j + k) % n]) return false;
}
} else {
for (int j = 0; j < n; ++j) {
if (mat[i][j] != mat[i][(j - k + 50 * n) % n]) return false;
}
}
}
return true;
}
}
2947. 统计美丽子字符串 I
https://leetcode.cn/problems/count-beautiful-substrings-i/description/
提示：
1 <= s.length <= 1000
1 <= k <= 1000
s 仅由小写英文字母组成。
竞赛时代码——前缀和+暴力枚举
class Solution {
public int beautifulSubstrings(String s, int k) {
int n = s.length();
Set<Character> set = Set.of('a', 'e', 'i', 'o', 'u');
int[] v = new int[n + 1], c = new int[n + 1];
for (int i = 0; i < n; ++i) {
v[i + 1] = v[i];
c[i + 1] = c[i];
if (set.contains(s.charAt(i))) v[i + 1]++;
else c[i + 1]++;
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
int vc = v[i + 1] - v[j], cc = c[i + 1] - c[j];
if (vc == cc && (vc * cc % k == 0)) ++ans;
}
}
return ans;
}
}0
Q3：2948. 交换得到字典序最小的数组
https://leetcode.cn/problems/make-lexicographically-smallest-array-by-swapping-elements/description/
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= limit <= 10^9
竞赛时代码——排序后判断
排序之后，可能可以交换的都在一起了，更方便判断。
如果a和b可以交换，b和c可以交换，那么a，b，c的顺序是任意的。
class Solution {
public int[] lexicographicallySmallestArray(int[] nums, int limit) {
int n = nums.length;
// 排序
Integer[] idx = new Integer[n];
Arrays.setAll(idx, e -> e);
Arrays.sort(idx, (x, y) -> nums[x] - nums[y]);
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
// 记录可以相互交换位置的一组
List<Integer> ls = new ArrayList<>();
ls.add(idx[i]);
int j = i + 1;
for (; j < n; ++j) {
if (nums[idx[j]] <= nums[idx[j - 1]] + limit) {
ls.add(idx[j]);
} else break;
}
// 交换这一组所有数字的位置，从小到大排列
List<Integer> ls2 = new ArrayList<>(ls);
Collections.sort(ls2);
for (int k = 0; k < ls.size(); ++k) {
ans[ls2.get(k)] = nums[ls.get(k)];
}
i = j - 1;
}
return ans;
}
}
相似题目——1202. 交换字符串中的元素（使用并查集 哈希表 复原）🐂
提示：
1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s 中只含有小写英文字母
class Solution {
int[] p;
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int n = s.length();
p = new int[n];
Arrays.setAll(p, e -> e);
// 1.输入并查集
for (List<Integer> pair: pairs) {
p[find(pair.get(0))] = find(pair.get(1));
}
// 2.利用并查集构建哈希映射
Map<Integer, PriorityQueue<Character>> m = new HashMap<>();
for (int i = 0; i < n; ++i) {
int r = find(i);
m.computeIfAbsent(r, key -> new PriorityQueue<Character>()).offer(s.charAt(i));
}
// 3.利用并查集和哈希映射复原结果字符串
StringBuilder ans = new StringBuilder();
for (int i = 0; i < n; ++i) {
int r = find(i);
ans.append(m.get(r).poll());
}
return ans.toString();
}
public int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
}
Q4：2949. 统计美丽子字符串 II⭐⭐⭐⭐⭐🚹🐂
https://leetcode.cn/problems/count-beautiful-substrings-ii/description/
提示：
1 <= s.length <= 5 * 10^4
1 <= k <= 1000
s 仅由小写英文字母组成。
解法——分解质因子+前缀和+哈希表
https://leetcode.cn/problems/count-beautiful-substrings-ii/solutions/2542274/fen-jie-zhi-yin-zi-qian-zhui-he-ha-xi-bi-ceil/
class Solution {
private static final int AEIOU_MASK = 1065233;
public long beautifulSubstrings(String s, int k) {
k = pSqrt(k * 4);
Map<Integer, Integer> cnt = new HashMap<>();
int n = s.length();
int sum = n; // 保证非负
cnt.put((k - 1) << 17 | sum, 1); // 添加 (k-1, sum)
long ans = 0;
for (int i = 0; i < n; i++) {
int bit = (AEIOU_MASK >> (s.charAt(i) - 'a')) & 1;
sum += bit * 2 - 1; // 1 -> 1 0 -> -1
ans += cnt.merge((i % k) << 17 | sum, 1, Integer::sum) - 1; // ans += cnt[(i%k,sum)]++
}
return ans;
}
private int pSqrt(int n) {
int res = 1;
for (int i = 2; i * i <= n; i++) {
int i2 = i * i; // 因为次数向上取整
while (n % i2 == 0) {
res *= i;
n /= i2;
}
if (n % i == 0) {
res *= i;
n /= i;
}
}
if (n > 1) {
res *= n;
}
return res;
}
}
(i % k) << 17 | sum 是为了把一个 pair 压缩成一个整数。
sum 刚开始设置成 n，其实是 0，为了防止成为负数整体偏移了数组的长度。
相似题目列表（前缀和 + 哈希表）
560. 和为 K 的子数组
https://leetcode.cn/problems/subarray-sum-equals-k/description/
记得在最开始放入一个和为0的前缀和。
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> m = new HashMap<>();
m.put(0, 1);
int s = 0, ans = 0;
for (int num: nums) {
s += num;
ans += m.getOrDefault(s - k, 0);
m.merge(s, 1, Integer::sum);
}
return ans;
}
}
974. 和可被 K 整除的子数组
https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/
提示:
1 <= nums.length <= 3 * 10^4
-104 <= nums[i] <= 10^4
2 <= k <= 10^4
为了元素之和可被 k 整除，将哈希表的键设置为 s % k，注意不能为负。
class Solution {
public int subarraysDivByK(int[] nums, int k) {
Map<Integer, Integer> m = new HashMap<>();
m.put(0, 1);
int s = 0, ans = 0;
for (int num: nums) {
s = ((s + num) % k + k) % k;
ans += m.getOrDefault(s, 0);
m.merge(s, 1, Integer::sum);
}
return ans;
}
}
1590. 使数组和能被 P 整除
https://leetcode.cn/problems/make-sum-divisible-by-p/description/
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= p <= 10^9
要使得剩余数字之和能被 p 整除，就需要所有数字之和-删去的数字之和能被p整除，即两者%p的结果相等。
为了求最短的子数组，每次存的 key 是最近的下标。
class Solution {
public int minSubarray(int[] nums, int p) {
int t = 0, s = 0, n = nums.length;
for (int x: nums) {
t = (t + x) % p;
}
if (t == 0) return 0;
Map<Integer, Integer> m = new HashMap<>();
m.put(0, -1);
int ans = n;
for (int i = 0; i < n; ++i) {
s = (s + nums[i]) % p;
int tt = ((s - t) % p + p) % p;
if (m.containsKey(tt)) ans = Math.min(ans, i - m.get(tt));
m.put(s, i);
}
if (ans >= n) return -1;
return ans;
}
}
523. 连续的子数组和
https://leetcode.cn/problems/continuous-subarray-sum/description/
提示：
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
0 <= sum(nums[i]) <= 2^31 - 1
1 <= k <= 2^31 - 1
存下 s % k 的第一个出现的下标即可，每次检查相同 s % k 的上一个出现位置是否满足子数组大小至少为 2 的条件。
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int n = nums.length;
Map<Integer, Integer> m = new HashMap<>();
m.put(0, -1);
int s = 0;
for (int i = 0; i < n; ++i) {
s = (s + nums[i]) % k;
if (m.containsKey(s)) {
if (i > m.get(s) + 1) return true;
} else m.put(s, i);
}
return false;
}
}
525. 连续数组
https://leetcode.cn/problems/contiguous-array/description/
记录的 value 是 1 和 0 的差的前缀和。
class Solution {
public int findMaxLength(int[] nums) {
int n = nums.length;
Map<Integer, Integer> m = new HashMap<>();
m.put(0, -1);
int d = 0, ans = 0;
for (int i = 0; i < n; ++i) {
d += nums[i] * 2 - 1;
if (m.containsKey(d)) ans = Math.max(ans, i - m.get(d));
else m.put(d, i);
}
return ans;
}
}
面试题 17.05. 字母与数字
https://leetcode.cn/problems/find-longest-subarray-lcci/description/
跟上面的题类似，记录的 value 是字母和数字数量的差。
class Solution {
public String[] findLongestSubarray(String[] array) {
int st = 0, ml = 0; // 记录起始点和最大长度
int n = array.length, d = 0;
Map<Integer, Integer> m = new HashMap<>();
m.put(0, 0);
for (int i = 0; i < n; ++i) {
char ch = array[i].charAt(0);
if (ch >= '0' && ch <= '9') d++;
else d--;
if (m.containsKey(d)) {
int j = m.get(d);
if (i - j + 1 > ml) {
st = j;
ml = i - j + 1;
}
} else m.put(d, i + 1);
}
String[] ans = new String[ml];
System.arraycopy(array, st, ans, 0, ml);
return ans;
}
}
1915. 最美子字符串的数目
https://leetcode.cn/problems/number-of-wonderful-substrings/description/
提示：
1 <= word.length <= 10^5
word 由从 'a' 到 'j' 的小写英文字母组成
奇偶性可以用异或来表示。
结果可以是：1.没有出现奇数次的；2.枚举每种出现奇数次的字母。
（注意：题目中给出字符的范围是 ‘a’ ~ ‘j’）。
用数组会比用哈希表快很多。
class Solution {
public long wonderfulSubstrings(String word) {
long ans = 0;
int[] cnt = new int[1024];
cnt[0] = 1;
int s = 0;
for (char ch: word.toCharArray()) {
s ^= 1 << (ch - 'a');
ans += cnt[s]; // 可以一个都没有
for (int i = 0; i <= 'j' - 'a'; ++i) { // 枚举出现奇数次的字符
ans += cnt[s ^ (1 << i)];
}
++cnt[s];
}
return ans;
}
}
930. 和相同的二元子数组
https://leetcode.cn/problems/binary-subarrays-with-sum/description/
提示：
1 <= nums.length <= 3 * 10^4
nums[i] 不是 0 就是 1
0 <= goal <= nums.length
class Solution {
public int numSubarraysWithSum(int[] nums, int goal) {
int n = nums.length;
int[] cnt = new int[n + 1];
cnt[0] = 1;
int s = 0, ans = 0;
for (int i = 0; i < n; ++i) {
s += nums[i];
if (s >= goal) ans += cnt[s - goal];
cnt[s]++;
}
return ans;
}
}
1371. 每个元音包含偶数次的最长子字符串
https://leetcode.cn/problems/find-the-longest-substring-containing-vowels-in-even-counts/
提示：
1 <= s.length <= 5 x 10^5
s 只包含小写英文字母。
状态压缩。
奇偶性用异或来表示，记录每种状态第一次出现的位置。
class Solution {
public int findTheLongestSubstring(String s) {
Map<Integer, Integer> cnt = new HashMap<>();
cnt.put(0, -1);
int t = 0, ans = 0, mask = 1065233;
for (int i = 0; i < s.length(); ++i) {
char ch = s.charAt(i);
if ((mask & (1 << (ch - 'a'))) != 0) t ^= 1 << (ch - 'a');
if (cnt.containsKey(t)) ans = Math.max(ans, i - cnt.get(t));
else cnt.put(t, i);
}
return ans;
}
}
1542. 找出最长的超赞子字符串
https://leetcode.cn/problems/find-longest-awesome-substring/description/
提示：
1 <= s.length <= 10^5
s 仅由数字组成
等价转换。
class Solution {
public int longestAwesome(String s) {
// 等价于至多有一种字符出现奇数次
int[] pos = new int[1 << 10];
Arrays.fill(pos, Integer.MAX_VALUE);
pos[0] = -1;
int t = 0, ans = 0;
for (int i = 0; i < s.length(); ++i) {
t ^= 1 << (s.charAt(i) - '0');
if (pos[t] != Integer.MAX_VALUE) ans = Math.max(ans, i - pos[t]);
else pos[t] = i;
for (int j = 0; j <= 9; ++j) {
int x = t ^ (1 << j);
if (pos[x] != Integer.MAX_VALUE) ans = Math.max(ans, i - pos[x]);
}
}
return ans;
}
}
成绩记录
T3 脑子抽了其实很简单。
T4 想不到。
