欢迎大家加QQ群：623375442，可以方便群里面交流。没想到啥好办法，一堆二分查找，把我查找麻了。这周题目本质就2题。
100424. Count of Substrings Containing Every Vowel and K Consonants II
给你一个字符串 word 和一个 非负 整数 k。
返回 word 的 子字符串 中，每个元音字母（'a'、'e'、'i'、'o'、'u'）至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。
测试样例：
输入：word = "aeioqq", k = 1
输出：0
解释：不存在包含所有元音字母的子字符串。
解答：估计有双指针的做法，但是竞赛的时候实在是想不到了。直接3次二分查找
class Solution {
private static final char[] vowels = {'a', 'e', 'i', 'o', 'u'};
public long countOfSubstrings(String word, int k) {
int[][] counts = new int[word.length() + 1][vowels.length + 1];
for (int i = 0; i < word.length(); ++i) {
for (int j = 0; j <= vowels.length; ++j) {
counts[i + 1][j] = counts[i][j];
}
counts[i + 1][findOffset(word.charAt(i))] += 1;
}
long res = 0;
for (int i = 0; i < word.length(); ++i) {
// 满足元音字母都出现一次
int s1 = binarySearch(counts, i,i, word.length() - 1, k, 0);
if (s1 < word.length()) {
// 满足k个辅音字母
int s2 = binarySearch(counts, i, s1, word.length() - 1, k, 1);
if (s2 < word.length()) {
// 超过k个辅音字母
int s3 = binarySearch(counts, i, s2, word.length() - 1, k, 2);
res += (s3 - s2);
}
}
}
return res;
}
private int findOffset(char c) {
for (int i = 0; i < vowels.length; ++i) {
if (c == vowels[i]) {
return i;
}
}
return vowels.length;
}
private int binarySearch(int[][] counts, int left, int st, int ed, int k, int offset) {
while (st < ed) {
int mid = (st + ed) / 2;
boolean response = isValid(counts, left, mid, k, offset);
if (!response) {
st = mid + 1;
} else {
ed = mid;
}
}
return isValid(counts, left, st, k, offset) ? st : counts.length - 1;
}
private boolean isValid(int[][] counts, int st, int ed, int k, int offset) {
return switch (offset) {
case 0 -> isValid1(counts, st, ed);
case 1 -> isValid2(counts, st, ed, k);
case 2 -> isValid3(counts, st, ed, k);
default -> false;
};
}
private boolean isValid1(int[][] counts, int st, int ed) {
for (int i = 0; i < vowels.length; ++i) {
if (counts[ed + 1][i] - counts[st][i] == 0) {
return false;
}
}
return true;
}
private boolean isValid2(int[][] counts, int st, int ed, int k) {
return counts[ed + 1][5] - counts[st][5] >= k;
}
private boolean isValid3(int[][] counts, int st, int ed, int k) {
return counts[ed + 1][5] - counts[st][5] > k;
}
}100447. Find the K-th Character in String Game II
Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = "a"。
给定一个正整数 k 和一个整数数组 operations，其中 operations[i] 表示第 i 次操作的类型。
现在 Bob 将要求 Alice 按顺序执行 所有 操作：
- 如果 operations[i] == 0，将 word 的一份 副本追加 到它自身。
- 如果 operations[i] == 1，将 word 中的每个字符 更改 为英文字母表中的 下一个 字符来生成一个新字符串，并将其 追加 到原始的 word。例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。
在执行所有操作后，返回 word 中第 k 个字符的值。
注意，在第二种类型的操作中，字符 'z' 可以变成 'a'。
测试样例：
输入：k = 10, operations = [0,1,0,1]
输出："b"
解释：最初，word == "a"。Alice 按以下方式执行四次操作：
- 将 "a" 附加到 "a"，word 变为 "aa"。
- 将 "bb" 附加到 "aa"，word 变为 "aabb"。
- 将 "aabb" 附加到 "aabb"，word 变为 "aabbaabb"。
- 将 "bbccbbcc" 附加到 "aabbaabb"，word 变为 "aabbaabbbbccbbcc"。
解答：这题也是类似折半搜索的味道。一个例子就是样例中的情况，可以发现10号位置被2号位置决定，2号位置又被1号位置决定。每个操作之后，都能使得整个字符串长度*2。
class Solution {
private static final long[] jump = {1L,2L,4L,8L,16L,32L,64L,128L,256L,512L,1024L,2048L,4096L,8192L,16384L,32768L,65536L,131072L,262144L,524288L,1048576L,2097152L,4194304L,8388608L,16777216L,33554432L,67108864L,134217728L,268435456L,536870912L,1073741824L,2147483648L,4294967296L,8589934592L,17179869184L,34359738368L,68719476736L,137438953472L,274877906944L,549755813888L,1099511627776L,2199023255552L,4398046511104L,8796093022208L,17592186044416L,35184372088832L,70368744177664L};
public char kthCharacter(long k, int[] operations) {
if (k == 1) {
return 'a';
}
List<Long> targetPos = new ArrayList<>();
targetPos.add(k);
// 寻找历史关系
for (int pos = jump.length - 1; pos >= 0; --pos) {
if (k > jump[pos]) {
k -= jump[pos];
targetPos.add(k);
}
}
long max = 1;
int pos = targetPos.size() - 2;
int c = 0;
// 根据operation计算历史位置情况
for (int op : operations) {
max *= 2;
if (max >= targetPos.get(pos)) {
if (op == 1) {
c = (c + 1) % 26;
}
--pos;
if (pos == -1) {
break;
}
}
}
return (char) (c + 'a');
}
}