25 – 09 – 11 (补于 25 – 09 – 15)
思想上水题，行动上并非(
今日份题面：
给你一个下标从 0 开始的字符串
s，将s中的元素重新 排列 得到新的字符串t，它满足：
- 所有辅音字母都在原来的位置上。更正式的，如果满足
0 <= i < s.length的下标i处的s[i]是个辅音字母，那么t[i] = s[i]。- 元音字母都必须以他们的 ASCII 值按 非递减 顺序排列。更正式的，对于满足
0 <= i < j < s.length的下标i和j，如果s[i]和s[j]都是元音字母，那么t[i]的 ASCII 值不能大于t[j]的 ASCII 值。请你返回结果字母串。
元音字母为
'a'，'e'，'i'，'o'和'u'，它们可能是小写字母也可能是大写字母，辅音字母是除了这 5 个字母以外的所有字母。
想起来很简单，扫一遍把 Vowels 都拎出来排个序按位置塞回去就行
所以很直接的：
class Solution {
final static HashSet<Character> VOWELS = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
public String sortVowels(String s) {
PriorityQueue<Character> containsVowels = new PriorityQueue<>(); // 最小堆偷懒
int i = 0, l = s.length();
int [] locs = new int [l]; // 元音位置数组
char [] s2c = s.toCharArray();
for(int j = 0; j < l; ++j){
if(VOWELS.contains(s2c[j])){ // 当前为元音直接记录
locs[i++] = j;
containsVowels.add(s2c[j]);
}
}
i = 0;
while(!containsVowels.isEmpty()){
s2c[locs[i++]] = containsVowels.poll();
}
return new String(s2c);
}
}
当然这是直接实现，实际上开最小堆是极其浪费空间的，而且每次储存的时间都是 $O(\log(n))$
所以做出第一个优化——
class Solution {
// 定义元音字母集合（大小写）
final static HashSet<Character> VOWELS = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
public String sortVowels(String s) {
// 收集所有元音字母
List<Character> vowelsList = new ArrayList<>();
for (char c : s.toCharArray()) {
if (VOWELS.contains(c)) {
vowelsList.add(c);
}
}
// 对元音字母列表进行排序（按字母顺序）
Collections.sort(vowelsList);
// 将字符串转换为字符数组以便修改
char[] chars = s.toCharArray();
int index = 0; // 用于遍历排序后的元音列表的索引
// 遍历字符数组，替换元音字母
for (int i = 0; i < chars.length; i++) {
if (VOWELS.contains(chars[i])) {
chars[i] = vowelsList.get(index++);
}
}
但实际上开出复杂结构的时间复杂度八成不会是最优，灵神在这给出了位运算进行优化：
class Solution {
public String sortVowels(String S) {
// 位掩码 0x208222 的二进制位在位置1、5、9、15、21处为1，对应元音字母的 low 5 bits
final int VOWEL_MASK = 0x208222;
char[] s = S.toCharArray();
// 计数数组，大小设置为 'u' + 1 以覆盖所有元音字母（A-Za-z 中的元音）
int[] cnt = new int['u' + 1];
for (char ch : s) {
// 检查字符是否为元音：使用掩码右移 (ch & 31) 位后检查最低位
if ((VOWEL_MASK >> (ch & 31) & 1) > 0) {
cnt[ch]++; // 统计元音出现次数
}
}
int j = 'A'; // 从最小的元音字母 'A' 开始
for (int i = 0; i < s.length; i++) {
// 跳过非元音字母
if ((VOWEL_MASK >> (s[i] & 31) & 1) == 0) {
continue;
}
// 找到下一个有剩余次数的元音字母（按ASCII顺序）
while (cnt[j] == 0) {
j = j == 'Z' ? 'a' : j + 1; // 从 'Z' 后跳到 'a'
}
s[i] = (char) j; // 替换元音字母
cnt[j]--; // 减少计数
}
return new String(s);
}
}
这相当于将字母表映射到 一个 26 位的二进制数上进行操作，时间成本直接跌到 $O(n)$.
25 – 09 – 12 (补于 25 – 09 – 16)
水题
今日份题面
小红和小明在玩一个字符串元音游戏。
给你一个字符串
s，小红和小明将轮流参与游戏，小红 先 开始：
- 在小红的回合，她必须移除
s中包含 奇数 个元音的任意 非空 子字符串。- 在小明的回合，他必须移除
s中包含 偶数 个元音的任意 非空 子字符串。第一个无法在其回合内进行移除操作的玩家输掉游戏。假设小红和小明都采取 最优策略 。
如果小红赢得游戏，返回
true，否则返回false。英文元音字母包括：
a,e,i,o, 和u。
开始看到题，我以为是取硬币这种博弈论题面，但是后来发现，只要字符串含元音字母小红必赢
- 奇数个元音一把移掉就行
- 偶数个元音先移任一奇数个转换成奇数串，因为小明的操作影响不了奇偶性，所以无论怎样最后都必定剩余 $n(n\geq 1)$ 个元音
class Solution {
public boolean doesAliceWin(String s) {
for (char c : s.toCharArray()) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
return true;
}
}
return false;
}
}
以上
25 – 09 – 13 (补于 25 – 09 – 17)
水题 X 2
今日份题面
给你一个由小写英文字母（
'a'到'z'）组成的字符串s。你的任务是找出出现频率 最高 的元音（'a'、'e'、'i'、'o'、'u'中的一个）和出现频率最高的辅音（除元音以外的所有字母），并返回这两个频数之和。注意：如果有多个元音或辅音具有相同的最高频率，可以任选其中一个。如果字符串中没有元音或没有辅音，则其频率视为 0。一个字母
x的 频率 是它在字符串中出现的次数。
桶排计数，维护一个元音的 HashSet 用于 O(1) 比较是否为目标以及两个最大值，通过一个 if 分别记录元音和辅音的最大值最后相加就行。
class Solution {
final static HashSet<Integer> vowelsLoc =new HashSet<>(Arrays.asList(0, 'e' - 'a','i' - 'a', 'o' - 'a', 'u' - 'a'));
public int maxFreqSum(String s) {
int maxFreqVowel = 0, maxFreqConsonant = 0;
int [] countAlphas = new int [26];
for(char c:s.toCharArray()){
int loc = c - 'a';
++countAlphas[loc];
if(vowelsLoc.contains(loc)){
maxFreqVowel = Math.max(maxFreqVowel, countAlphas[loc]);
}else{
maxFreqConsonant = Math.max(maxFreqConsonant, countAlphas[loc]);
}
}
return maxFreqConsonant + maxFreqVowel;
}
}
当然也可以位运算优化，思路与昨天的一致。
以上
25 – 09 – 124(补于 25 – 09 – 18)
今日份题面：
在给定单词列表
wordlist的情况下，我们希望实现一个拼写检查器，将查询单词转换为正确的单词。对于给定的查询单词
query，拼写检查器将会处理两类拼写错误：
- 大小写：如果查询匹配单词列表中的某个单词（不区分大小写），则返回的正确单词与单词列表中的大小写相同。
- 例如：
wordlist = ["yellow"],query = "YellOw":correct = "yellow"- 例如：
wordlist = ["Yellow"],query = "yellow":correct = "Yellow"- 例如：
wordlist = ["yellow"],query = "yellow":correct = "yellow"- 元音错误：如果在将查询单词中的元音
('a', 'e', 'i', 'o', 'u')分别替换为任何元音后，能与单词列表中的单词匹配（不区分大小写），则返回的正确单词与单词列表中的匹配项大小写相同。
- 例如：
wordlist = ["YellOw"],query = "yollow":correct = "YellOw"- 例如：
wordlist = ["YellOw"],query = "yeellow":correct = ""（无匹配项）- 例如：
wordlist = ["YellOw"],query = "yllw":correct = ""（无匹配项）此外，拼写检查器还按照以下优先级规则操作：
- 当查询完全匹配单词列表中的某个单词（区分大小写）时，应返回相同的单词。
- 当查询匹配到大小写问题的单词时，您应该返回单词列表中的第一个这样的匹配项。
- 当查询匹配到元音错误的单词时，您应该返回单词列表中的第一个这样的匹配项。
- 如果该查询在单词列表中没有匹配项，则应返回空字符串。
给出一些查询
queries，返回一个单词列表answer，其中answer[i]是由查询query = queries[i]得到的正确单词。
噼里啪啦一大堆梳理下来其实就三个操作：
- 忽略大小写
- 元音可平替
- 优先返回最相近的
所以我们可以维护三个 Hash 结构，具体而言
- 一模一样的 HashSet
- 大小写不同的 HashMap
- 平替的 HashMap
所以实现为：
class Solution {
public String[] spellchecker(String[] wordlist, String[] queries) {
int n = wordlist.length;
Set<String> origin = new HashSet<>(Arrays.asList(wordlist));
Map<String, String> lowerToOrigin = new HashMap<>(n); // 预分配空间
Map<String, String> vowelToOrigin = new HashMap<>(n);
for (int i = n - 1; i >= 0; i--) {
String s = wordlist[i];
String lower = s.toLowerCase();
lowerToOrigin.put(lower, s);
vowelToOrigin.put(replaceVowels(lower), s);
}
for (int i = 0; i < queries.length; i++) {
String q = queries[i];
if (origin.contains(q)) { // 完全匹配
continue;
}
String lower = q.toLowerCase();
if (lowerToOrigin.containsKey(lower)) { // 不区分大小写的匹配
queries[i] = lowerToOrigin.get(lower);
} else { // 不区分大小写+元音模糊匹配
queries[i] = vowelToOrigin.getOrDefault(replaceVowels(lower), "");
}
}
return queries;
}
private String replaceVowels(String str) {
char[] s = str.toCharArray();
for (int i = 0; i < s.length; ++i) {
char c = s[i];
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
s[i] = '?';
}
}
return new String(s);
}
}
以上
发表回复