模拟。有个性质，如果左移 \(k\) 位之后相等，则右移 \(k\) 位也必定相等。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean areSimilar(int[][] mat, int k) {
int m = mat.length, n = mat[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (mat[i][j] != mat[i][((j + (i % 2 == 0 ? 1 : -1) * k) % n + n) % n]) {
return false;
}
}
}
return true;
}
}
|
将元音字母看作 \(1\)，非元音字母看作 \(-1\)，使用前缀和 + 哈希表的技巧，可以得到若干个分组，每组中任意两个下标构成的子数组都满足条件一。然后我们可以暴力判断所有满足条件一的子数组的长度是否满足条件二，时间复杂度为 \(O(n^{2})\)。（补充：可以纯暴力做，不需要分组。）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int beautifulSubstrings(String s, int k) {
int n = s.length(), sum = 0;
Set<Character> set = Set.of('a', 'e', 'i', 'o', 'u');
Map<Integer, List<Integer>> map = new HashMap<>();
map.computeIfAbsent(0, t -> new ArrayList<>()).add(-1);
for (int i = 0; i < n; i++) {
sum += set.contains(s.charAt(i)) ? 1 : -1;
map.computeIfAbsent(sum, t -> new ArrayList<>()).add(i);
}
int ans = 0;
for (var list : map.values()) {
for (int j = 0; j < list.size() ; j++) {
for (int i = 0; i < j; i++) {
int len = (list.get(j) - list.get(i)) / 2;
if (len * len % k == 0) {
ans++;
}
}
}
}
return ans;
}
}
|
如果 \(|nums[i]-nums[j]|<=limit\)，那么就可以交换 \(nums[i]\) 和 \(nums[j]\)，该交换的性质具有传递性，所以我们可以对原数组进行排序，只要相邻元素的差值小于等于 \(limit\)，它们就在同一个可交换集合中。这样可以将原数组划分为若干可交换集合，然后对每个集合排序，从小到大排列即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public int[] lexicographicallySmallestArray(int[] nums, int limit) {
int n = nums.length;
var aux = new Integer[n];
for (int i = 0; i < n; i++) {
aux[i] = i;
}
Arrays.sort(aux, (i, j) -> nums[i] - nums[j]);
int pre = -limit;
List<List<Integer>> buckets = new ArrayList<>();
for (int i : aux) {
if (nums[i] - pre > limit) {
buckets.add(new ArrayList<>());
}
buckets.get(buckets.size() - 1).add(i);
pre = nums[i];
}
int[] ans = new int[n];
for (var bucket : buckets) {
List<Integer> pos = new ArrayList<>();
pos.addAll(bucket);
Collections.sort(pos);
for (int i = 0; i < pos.size(); i++) {
ans[pos.get(i)] = nums[bucket.get(i)];
}
}
return ans;
}
}
|
朴素做法的瓶颈在 \((\frac{L}{2})^{2}\bmod{k}=0\) 的判断上，可以通过将条件二变换为 \(L\bmod{k^{\prime}}=0\)，然后使用前缀和以及下标模 \(k^{\prime}\) 的值来分组，这样同组内的下标两两组合得到的必定是满足两个条件的子数组。灵神题解，时间复杂度 \(O(n+\sqrt{k})\)。还有另一种枚举的做法，题解。