欢迎大家加QQ群：623375442，可以方便群里面交流。
100284. Valid Word
有效单词 需要满足以下几个条件：
- 至少 包含 3 个字符。
- 由数字 0-9 和英文大小写字母组成。（不必包含所有这类字符。）
- 至少 包含一个 元音字母 。
- 至少 包含一个 辅音字母 。
给你一个字符串 word 。如果 word 是一个有效单词，则返回 true ，否则返回 false 。
注意：
- 'a'、'e'、'i'、'o'、'u' 及其大写形式都属于 元音字母 。
- 英文中的 辅音字母 是指那些除元音字母之外的字母。
测试样例：
输入：word = "234Adas"
输出：true
解释：这个单词满足所有条件。
解答：按照题意分部判断条件是否满足。
class Solution {
private static final char[] vowels = {'a','e','i','o','u'};
public boolean isValid(String word) {
// 长度大于3
if (word.length() < 3) {
return false;
}
boolean hasVowel = false, hasConsonant = false;
for (int i = 0; i < word.length(); ++i) {
char c = word.charAt(i);
// 只能是数字或者英语大小写
if (c >= '0' && c <= '9') {
continue;
} else if (isEnglish(c)) {
// 记录元音字母 和 辅音字母情况
if (isVowel(c)) {
hasVowel = true;
} else {
hasConsonant = true;
}
} else {
return false;
}
}
// 判断同时存在元音字母 和 辅音字母
return hasVowel && hasConsonant;
}
private boolean isVowel(char c) {
for (char t : vowels) {
if (c == t || c == (t - 'a' + 'A')) {
return true;
}
}
return false;
}
private boolean isEnglish(char c) {
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}
}100275. Minimum Number of Operations to Make Word K-Periodic
给你一个长度为 n 的字符串 word 和一个整数 k ，其中 k 是 n 的因数。
在一次操作中，你可以选择任意两个下标 i 和 j，其中 0 <= i, j < n ，且这两个下标都可以被 k 整除，然后用从 j 开始的长度为 k 的子串替换从 i 开始的长度为 k 的子串。也就是说，将子串 word[i..i + k - 1] 替换为子串 word[j..j + k - 1] 。
返回使 word 成为 K 周期字符串 所需的 最少 操作次数。
如果存在某个长度为 k 的字符串 s，使得 word 可以表示为任意次数连接 s ，则称字符串 word 是 K 周期字符串 。例如，如果 word == "ababab"，那么 word 就是 s = "ab" 时的 2 周期字符串 。
测试样例：
输入：word = "leetcodeleet", k = 4
输出：1
解释：可以选择 i = 4 和 j = 0 获得一个 4 周期字符串。这次操作后，word 变为 "leetleetleet" 。
解答：利用哈希表储存一下所有可能位置的出现次数，挑选出现次数最高的子字符串。
class Solution {
public int minimumOperationsToMakeKPeriodic(String word, int k) {
HashMap<String, Integer> count = new HashMap<>();
int max = 0;
for (int i = 0; i < word.length(); i = i + k) {
String sub = word.substring(i, i + k);
int tmp = count.getOrDefault(sub, 0) + 1;
max = Math.max(max, tmp);
count.put(sub, tmp);
}
return word.length() / k - max;
}
}100283. Minimum Length of Anagram Concatenation
给你一个字符串 s ，它由某个字符串 t 和它的 同位字符串 连接而成。
请你返回字符串 t 的 最小 可能长度。
同位字符串 指的是重新排列一个单词得到的另外一个字符串，原来字符串中的每个字符在新字符串中都恰好只使用一次。
测试样例：
输入：s = "abba"
输出：2
解释：一个可能的字符串 t 为 "ba" 。
解答：稍微有点脑经急转弯。查询所有出现的字母中的最大公约数，这样就能把所有字母按照要求的频次，平均分配到t中。注意英语的原文是a concatenation of anagrams of some string t。所以是先concatenation之后，再anagrams。中文翻译有点垃圾。
补充一下GCD不太够，可能会有aabb这种情况。所以增加一个前缀和数组，配合mod来判断是否真正可以完成计算。
class Solution {
public int minAnagramLength(String s) {
int[][] count = new int[s.length() + 1][26];
for (int i = 0; i < s.length(); ++i) {
for (int j = 0; j < 26; ++j) {
count[i + 1][j] = count[i][j];
}
count[i + 1][s.charAt(i) - 'a'] += 1;
}
int max = -1;
for (int n : count[s.length()]) {
if (n > 0) {
if (max == -1) {
max = n;
} else {
max = gcd(max, n);
}
}
}
if (max == 1) {
return s.length();
}
int realMax = s.length();
for (int i = 1; i * i <= max; ++i) {
if (max % i == 0) {
int x1 = max / i, x2 = i;
if (isValid(count, s.length() / x1, x1)) {
realMax = Math.min(realMax, s.length() / x1);
}
if (isValid(count, s.length() / x2, x2)) {
realMax = Math.min(realMax, s.length() / x2);
}
}
}
return realMax;
}
private int gcd(int x, int y) {
while (y != 0) {
int tmp = x % y;
x = y;
y = tmp;
}
return x;
}
private boolean isValid(int[][] count, int x, int y) {
for (int i = x; i < count.length; i = i + x) {
for (int j = 0; j < 26; ++j) {
if (count[i][j] - count[i - x][j] != count[count.length - 1][j] / y) {
return false;
}
}
}
return true;
}
}100288. Minimum Cost to Equalize Array
给你一个整数数组 nums 和两个整数 cost1 和 cost2 。你可以执行以下 任一 操作 任意 次：
- 从 nums 中选择下标 i 并且将 nums[i] 增加 1 ，开销为 cost1。
- 选择 nums 中两个 不同 下标 i 和 j ，并且将 nums[1] 和 nums[2] 都 增加 1 ，开销为 cost2 。
你的目标是使数组中所有元素都 相等 ，请你返回需要的 最小开销 之和。
由于答案可能会很大，请你将它对 10^9 + 7 取余 后返回。
测试样例：
输入：nums = [4,1], cost1 = 5, cost2 = 2
输出：15
解释：执行以下操作可以使数组中所有元素相等：
- 将 nums[1] 增加 1 ，开销为 5 ，nums 变为 [4,2] 。
- 将 nums[1] 增加 1 ，开销为 5 ，nums 变为 [4,3] 。
- 将 nums[1] 增加 1 ，开销为 5 ，nums 变为 [4,4] 。
总开销为 15 。
解答：这题需要注意一个case。nums = [1,3,3], cost1 = 1000000, cost2 = 1。这种情况下，把所有数字调整成[5,5,5]是最合理的。没想到什么好的数学解法，我用的是暴力。2 * max - 1一定可以满足要求。暴力枚举所有可能，幸好1 <= nums[i] <= 10^6。这个范围也不大，计算一下耗时不长。
有更好的数学解法我再更新吧。
class Solution {
private static final int mod = 1_000_000_007;
public int minCostToEqualizeArray(int[] nums, int cost1, int cost2) {
// 寻找最大值和最小值
long max = 0, min = Integer.MAX_VALUE;
for (int n : nums) {
max = Math.max(max, n);
min = Math.min(min, n);
}
// 如果cost1 * 2 <= cost2, 就没必要用任何优化，直接暴力将所有数字提升到max一致
if (2 * cost1 <= cost2) {
int res = 0;
for (int n : nums) {
long tmp = max - n;
tmp *= cost1;
res = (int) ((res + tmp) % mod);
}
return res;
}
long sum = 0;
for (int n : nums) {
sum += max - n;
}
long res = Long.MAX_VALUE;
// 没想到什么好办法，就直接暴力枚举所有可能性了
for (long i = 0; i <= Math.max(max, nums.length); ++i) {
long cur = i * nums.length + sum;
long maxDiff = max - min + i;
long remain = cur - maxDiff;
// 最大化的利用cost2的方案，但是最小值和最大值差距过大的话，还是有部分数字需要利用cost1提升
if (maxDiff <= remain) {
res = Math.min(res, (cur % 2 == 1 ? cost1 : 0) + cur / 2 * cost2);
} else {
res = Math.min(res, cost2 * remain + cost1 * (maxDiff - remain));
}
}
return (int)(res % mod);
}
}