100139. Matrix Similarity After Cyclic Shifts
给你一个大小为 m x n 的整数矩阵 mat 和一个整数 k 。请你将矩阵中的 奇数 行循环 右 移 k 次，偶数 行循环 左 移 k 次。
如果初始矩阵和最终矩阵完全相同，则返回 true ，否则返回 false 。
测试样例：
输入：mat = [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k = 2
输出：true
解释：
由于矩阵中的所有值都相等，即使进行循环移位，矩阵仍然保持不变。因此，返回 true 。
解答：这道题目范围不大，直接暴力位移然后对比一下。
class Solution {
public boolean areSimilar(int[][] mat, int k) {
int m = mat.length, n = mat[0].length;
int[][] next = new int[m][n];
for (int i = 0; i < m; ++i) {
if (i % 2 == 0) {
for (int j = 0; j < n; ++j) {
next[i][j] = mat[i][((j - k) % n + n) % n];
}
} else {
for (int j = 0; j < n; ++j) {
next[i][j] = mat[i][(j + k) % n];
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (mat[i][j] != next[i][j]) {
return false;
}
}
}
return true;
}
}100134. Count Beautiful Substrings I
给你一个字符串 s 和一个正整数 k 。
用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。
如果某个字符串满足以下条件，则称其为 美丽字符串 ：
- vowels == consonants，即元音字母和辅音字母的数量相等。
- (vowels * consonants) % k == 0，即元音字母和辅音字母的数量的乘积能被 k 整除。
返回字符串 s 中 非空美丽子字符串 的数量。
子字符串是字符串中的一个连续字符序列。
英语中的 元音字母 为 'a'、'e'、'i'、'o' 和 'u' 。
英语中的 辅音字母 为除了元音字母之外的所有字母。
测试样例：
输入：s = "baeyh", k = 2
输出：2
解释：
字符串 s 中有 2 个美丽子字符串。
- 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["y","h"]）。
可以看出字符串 "aeyh" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。
- 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["b","y"]）。
可以看出字符串 "baey" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。可以证明字符串 s 中只有 2 个美丽子字符串。
解答：这题和第四题的区别是范围，第四题一开始没啥思路。这题就用了前缀和计算元音和辅音的diff情况，然后暴力寻找符合第二个条件的位置。
class Solution {
private static final char[] vowels = {'a', 'e', 'i', 'o','u'};
public int beautifulSubstrings(String s, int k) {
int sum = 0;
HashMap<Integer, List<Integer>> map = new HashMap<>();
map.put(0, new ArrayList<>());
map.get(0).add(-1);
int res = 0;
for (int i = 0; i < s.length(); ++i) {
sum += isVowels(s.charAt(i)) ? 1 : -1;
if (!map.containsKey(sum)) {
map.put(sum, new ArrayList<>());
}
for (long n : map.get(sum)) {
if ((i - n) % 2 == 0 && (i - n) * (i - n) / 4 % k == 0) {
++res;
}
}
map.get(sum).add(i);
}
return res;
}
private boolean isVowels(char c) {
for (char v : vowels) {
if (v == c) return true;
}
return false;
}
}100142. Make Lexicographically Smallest Array by Swapping Elements
给你一个下标从 0 开始的 正整数 数组 nums 和一个 正整数 limit 。
在一次操作中，你可以选择任意两个下标 i 和 j，如果 满足 |nums[i] - nums[j]| <= limit ，则交换 nums[i] 和 nums[j] 。
返回执行任意次操作后能得到的 字典序最小的数组 。
如果在数组 a 和数组 b 第一个不同的位置上，数组 a 中的对应字符比数组 b 中的对应字符的字典序更小，则认为数组 a 就比数组 b 字典序更小。例如，数组 [2,10,3] 比数组 [10,2,3] 字典序更小，下标 0 处是两个数组第一个不同的位置，且 2 < 10 。
测试样例：
输入：nums = [1,5,3,9,8], limit = 2
输出：[1,3,5,8,9]
解释：
执行 2 次操作：
- 交换 nums[1] 和 nums[2] 。数组变为 [1,3,5,9,8] 。
- 交换 nums[3] 和 nums[4] 。数组变为 [1,3,5,8,9] 。
即便执行更多次操作，也无法得到字典序更小的数组。注意，执行不同的操作也可能会得到相同的结果。
解答：需要注意，交换次数可以无限多。所以首先利用并查集，寻找到所有可以相互交换的数组块（union条件寻找任意一个数，可以使得abs(xi - n) <= limit，可以利用红黑树加快搜索）。接下来利用贪婪算法完成数组交换（index越小，就放数组块里面可以拿到的最小值）。
class Solution {
class DSU{
private HashMap<Integer, Integer> parent;
public DSU() {
parent = new HashMap<>();
}
public int find(int x) {
if (parent.containsKey(x) && parent.get(x) != x) {
parent.put(x, find(parent.get(x)));
}
return parent.getOrDefault(x, x);
}
public void union(int x, int y) {
parent.put(find(x), find(y));
}
}
public int[] lexicographicallySmallestArray(int[] nums, int limit) {
TreeSet<Integer> set = new TreeSet<>();
for (int n : nums) {
set.add(n);
}
DSU uf = new DSU();
for (int n : nums) {
int tmp = set.ceiling(n - limit);
uf.union(tmp, n);
}
HashMap<Integer, PriorityQueue<Integer>> mem = new HashMap<>();
for (int n : nums) {
int p = uf.find(n);
if (!mem.containsKey(p)) {
mem.put(p, new PriorityQueue<>());
}
mem.get(p).add(n);
}
for (int i = 0; i < nums.length; ++i) {
int p = uf.find(nums[i]);
nums[i] = mem.get(p).poll();
}
return nums;
}
}100132. Count Beautiful Substrings II
给你一个字符串 s 和一个正整数 k 。
用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。
如果某个字符串满足以下条件，则称其为 美丽字符串 ：
- vowels == consonants，即元音字母和辅音字母的数量相等。
- (vowels * consonants) % k == 0，即元音字母和辅音字母的数量的乘积能被 k 整除。
返回字符串 s 中 非空美丽子字符串 的数量。
子字符串是字符串中的一个连续字符序列。
英语中的 元音字母 为 'a'、'e'、'i'、'o' 和 'u' 。
英语中的 辅音字母 为除了元音字母之外的所有字母。
测试样例：
输入：s = "baeyh", k = 2
输出：2
解释：
字符串 s 中有 2 个美丽子字符串。
- 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["y","h"]）。
可以看出字符串 "aeyh" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。
- 子字符串 "baeyh"，vowels = 2（["a","e"]），consonants = 2（["b","y"]）。
可以看出字符串 "baey" 是美丽字符串，因为 vowels == consonants 且 vowels * consonants % k == 0 。可以证明字符串 s 中只有 2 个美丽子字符串。
解答：这题做的稍微有点泪目。其实挺简单的，因为vowels == consonants且 vowels * consonants % k == 0，所以位置之差可以有一定条件。我们首先将k进行质因数分解。如果vowels % a == 0，那么
consonants % a == 0。我们将k的质因数分为偶数个部分和奇数个部分，偶数个部分可以给vowels和consonants平分(square)，奇数部分则需要double之后再平分(k / square / square)。这样，我们就能知道vowels和consonants需要满足vowels % ((k / square / square) square) == 0和consonants % ((k / square / square) square) == 0。这块如果可以理解之后，剩余就是利用前缀和，并利用mod条件，用HashMap快速搜索了。
class Solution {
private static final char[] vowels = {'a', 'e', 'i', 'o','u'};
public long beautifulSubstrings(String s, int k) {
int square = 1, tmp = k;
for (int i = 2; i * i <= tmp; ++i) {
if (tmp % i == 0) {
int c = 0;
while (tmp % i == 0) {
++c;
tmp /= i;
}
for (int j = 0; j < c / 2; ++j) {
square *= i;
}
}
}
int best = (k / square / square) * square;
HashMap<Integer, HashMap<Integer, Integer>>[] mem = new HashMap[2];
for (int i = 0; i < 2; ++i) {
mem[i] = new HashMap<>();
}
long res = 0;
int sum = 0;
for (int i = 0; i < s.length(); ++i) {
int offset = i % 2;
sum += isVowels(s.charAt(i)) ? 1 : -1;
if (offset == 1 && sum == 0 && (i + 1L) * (i + 1L) / 4 % k == 0) {
++res;
}
HashMap<Integer, HashMap<Integer, Integer>> cur = mem[offset];
if (!cur.containsKey(sum)) {
cur.put(sum, new HashMap<>());
}
int remain = ((i - offset) / 2) % best, add = cur.get(sum).getOrDefault(remain, 0);
res += add;
cur.get(sum).put(remain, add + 1);
}
return res;
}
private boolean isVowels(char c) {
for (char v : vowels) {
if (v == c) return true;
}
return false;
}
}