企业官网建设流程全解析

• 科学计算

本篇技术指南围绕 codeforces-go 仓库中 双周赛 109 第 B 题题解文档 展开，系统拆解 LeetCode「Sort Vowels in a String（排序字符串中的元音）」一题的三种解法：收集排序填空、位掩码0x208222优化、以及线性复杂度的计数排序，并对照仓库内的 Go 实现、测试文件 与 测试数据 验证每行代码的真实出处。读完本文，你既能掌握这道题从O(n log n)到O(n)的完整优化路径，也能学会「集合论到位运算」这一可迁移的元音/字母集合判定技巧。

一、问题回顾：规则与关键例子的手推过程

题目要求：给定字符串s，将其中的**元音字母（a/e/i/o/u，大小写均可）**单独提取出来按ASCII 升序排序，再按原顺序填回原字符串中元音所在的空位，非元音字符位置保持不变。

原文档给出了示例 1 的完整推演：s = "lEetcOde"，其中元音字母为E、e、O、e，排序后为EOee（大写字母排前，因为大写字母的 ASCII 值更小）。把原串中的元音位置视作空位，得到l__tc_d_（共 4 个空位），依次填入EOee后得到答案lEOtcede。

仓库中的 测试数据 恰好收录了两个用例，可直接对照验证：

"lEetcOde" "lEOtcede" "lYmpH" "lYmpH"

第二个用例"lYmpH"中不含任何元音字母，因此输出与原串完全一致——这是对「非元音位置不动」规则的最简回归用例。

二、写法一：提取 → 排序 → 填空（O(n log n)）

思路最直观：第一遍扫描把元音收集到数组中；排序数组；第二遍扫描，遇到元音就按序「填空」。

原文档给出了 Python3 / Java / C++ / C / Go / JavaScript / Rust 共 7 种语言的完整实现，核心逻辑完全同构，这里完整列出：

class Solution: def sortVowels(self, s: str) -> str: vowels = sorted(ch for ch in s if ch in "AEIOUaeiou") t = list(s) # str 无法修改，转成 list j = 0 for i, ch in enumerate(t): if ch in "AEIOUaeiou": t[i] = vowels[j] # 填空 j += 1 return ''.join(t)

class Solution { public String sortVowels(String S) { StringBuilder vowels = new StringBuilder(); char[] s = S.toCharArray(); for (char ch : s) { char c = Character.toLowerCase(ch); if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') { vowels.append(ch); } } char[] sortedVowels = vowels.toString().toCharArray(); Arrays.sort(sortedVowels); int j = 0; for (int i = 0; i < s.length; i++) { char c = Character.toLowerCase(s[i]); if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') { s[i] = sortedVowels[j++]; } } return new String(s); } }

class Solution { public: string sortVowels(string s) { string vowels; for (char ch : s) { char c = tolower(ch); if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') { vowels += ch; } } ranges::sort(vowels); int j = 0; for (char& ch : s) { char c = tolower(ch); if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') { ch = vowels[j++]; } } return s; } };

#define VOWEL_MASK 0x208222 int cmp(const void* a, const void* b) { return *(char*)a - *(char*)b; } char* sortVowels(char* s) { int n = strlen(s); char* vowels = malloc(n * sizeof(char)); int k = 0; for (int i = 0; i < n; i++) { char c = tolower(s[i]); if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') { vowels[k++] = s[i]; } } qsort(vowels, k, sizeof(char), cmp); k = 0; for (int i = 0; i < n; i++) { char c = tolower(s[i]); if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') { s[i] = vowels[k++]; } } free(vowels); return s; }

func sortVowels(s string) string { vowels := []byte{} for _, ch := range s { c := unicode.ToLower(ch) if strings.ContainsRune("aeiou", c) { vowels = append(vowels, byte(ch)) } } slices.Sort(vowels) t := []byte(s) j := 0 for i, ch := range t { c := unicode.ToLower(rune(ch)) if strings.ContainsRune("aeiou", c) { t[i] = vowels[j] j++ } } return string(t) }

var sortVowels = function(s) { const vowels = []; for (const ch of s) { if ("AEIOUaeiou".includes(ch)) { vowels.push(ch); } } vowels.sort(); let j = 0; const t = s.split(''); for (let i = 0; i < t.length; i++) { if ("AEIOUaeiou".includes(t[i])) { t[i] = vowels[j++]; } } return t.join(''); };

impl Solution { pub fn sort_vowels(s: String) -> String { let mut vowels = s.bytes() .filter(|&ch| "AEIOUaeiou".contains(ch as char)) .collect::<Vec<_>>(); vowels.sort_unstable(); let mut s = s.into_bytes(); let mut j = 0; for ch in s.iter_mut() { if "AEIOUaeiou".contains(*ch as char) { *ch = vowels[j]; j += 1; } } unsafe { String::from_utf8_unchecked(s) } } }

注意各语言的一个共同细节：第二遍填空必须只修改元音位置，且填入的是已排序元音数组中依次推进的下一个元素——指针j单调递增，天然保证「小的元音先被填走」。

三、写法二：位掩码 0x208222 优化（核心技巧）

3.1 原理：ch & 31统一大小写规则

原文档给出了一条重要的 ASCII 观察：A到Z的 ASCII 码二进制低 5 位恰好是 1 到 26，a到z的 ASCII 码二进制低 5 位同样也是 1 到 26。因此ch & 31可以把任意大小写字母映射到 1..26，规则完全统一，无需再调用tolower/unicode.ToLower。

元音字母a、e、i、o、u分别是字母表中的第 1、5、9、15、21 个字母。依据「从集合论到位运算」的通用套路，可以把元音集合编码为一个整数：

2^1 + 2^5 + 2^9 + 2^15 + 2^21 = 2130466 = 0x208222

于是「判断某字符是否元音」变成一次纯位运算：

is_vowel(ch) = (VOWEL_MASK >> (ch & 31)) & 1

ch & 31得到字母序号后右移掩码，最低位若为 1 即说明该序号对应的字母在元音集合中。相比逐字符c == 'a' || ... || c == 'u'的判断链，这种方式更紧凑，也更适合在循环中被编译器优化。

3.2 完整代码（7 语言）

class Solution: def sortVowels(self, s: str) -> str: VOWEL_MASK = 0x208222 is_vowel = lambda ch: VOWEL_MASK >> (ord(ch) & 31) & 1 vowels = sorted(filter(is_vowel, s)) t = list(s) # str 无法修改，转成 list j = 0 for i, ch in enumerate(t): if is_vowel(ch): t[i] = vowels[j] # 填空 j += 1 return ''.join(t)

class Solution { public String sortVowels(String S) { final int VOWEL_MASK = 0x208222; char[] s = S.toCharArray(); byte[] vowels = new byte[s.length]; // 比 StringBuilder 快 int k = 0; for (char ch : s) { if ((VOWEL_MASK >> (ch & 31) & 1) > 0) { vowels[k++] = (byte) ch; } } Arrays.sort(vowels, 0, k); k = 0; for (int i = 0; i < s.length; i++) { if ((VOWEL_MASK >> (s[i] & 31) & 1) > 0) { s[i] = (char) vowels[k++]; } } return new String(s); } }

class Solution { public: string sortVowels(string s) { const int VOWEL_MASK = 0x208222; string vowels; for (char ch : s) { if (VOWEL_MASK >> (ch & 31) & 1) { // ch 是元音 vowels += ch; } } ranges::sort(vowels); int j = 0; for (char& ch : s) { if (VOWEL_MASK >> (ch & 31) & 1) { // ch 是元音 ch = vowels[j++]; } } return s; } };

#define VOWEL_MASK 0x208222 int cmp(const void* a, const void* b) { return *(char*)a - *(char*)b; } char* sortVowels(char* s) { int n = strlen(s); char* vowels = malloc(n * sizeof(char)); int k = 0; for (int i = 0; i < n; i++) { if (VOWEL_MASK >> (s[i] & 31) & 1) { vowels[k++] = s[i]; } } qsort(vowels, k, sizeof(char), cmp); k = 0; for (int i = 0; i < n; i++) { if (VOWEL_MASK >> (s[i] & 31) & 1) { s[i] = vowels[k++]; } } free(vowels); return s; }

func sortVowels(s string) string { const vowelMask = 0x208222 vowels := []byte{} for _, ch := range s { if vowelMask>>(ch&31)&1 > 0 { // ch 是元音 vowels = append(vowels, byte(ch)) } } slices.Sort(vowels) t := []byte(s) j := 0 for i, ch := range t { if vowelMask>>(ch&31)&1 > 0 { // ch 是元音 t[i] = vowels[j] j++ } } return string(t) }

var sortVowels = function(s) { const VOWEL_MASK = 0x208222; const vowels = []; for (const ch of s) { if (VOWEL_MASK >> (ch.charCodeAt(0) & 31) & 1) { vowels.push(ch); } } vowels.sort(); const t = s.split(''); let j = 0; for (let i = 0; i < t.length; i++) { if (VOWEL_MASK >> (t[i].charCodeAt(0) & 31) & 1) { t[i] = vowels[j++]; } } return t.join(''); };

impl Solution { pub fn sort_vowels(s: String) -> String { const VOWEL_MASK: u32 = 0x208222; let mut vowels = s.bytes() .filter(|&ch| VOWEL_MASK >> (ch & 31) & 1 > 0) .collect::<Vec<_>>(); vowels.sort_unstable(); let mut s = s.into_bytes(); let mut j = 0; for ch in s.iter_mut() { if VOWEL_MASK >> (*ch & 31) & 1 > 0 { *ch = vowels[j]; j += 1; } } unsafe { String::from_utf8_unchecked(s) } } }

仓库中的 b.go 第 33-52 行即为sortVowels2的 Go 实现，与上文 Go 代码完全一致（仅将常量名改为小写vowelMask）。

四、写法三：计数排序，优化到 O(n)

更进一步：元音字符集合很小（最多 10 个），完全不必排序整个数组，只需统计每个元音字符的出现次数，再按 ASCII 顺序依次「消耗」次数即可。这是原文档推荐的最终写法。

核心技巧在于用一个从'A'出发的游标j：当cnt[j] == 0时向后推进（到大写'Z'后折回小写'a'），找到下一个仍有剩余次数的元音，填入当前空位并cnt[j]--。

class Solution: def sortVowels(self, s: str) -> str: VOWELS = "AEIOUaeiou" cnt = Counter(ch for ch in s if ch in VOWELS) it = iter(VOWELS) cur = next(it) t = list(s) # str 无法修改，转成 list for i, ch in enumerate(t): if ch in VOWELS: if cnt[cur] == 0: # 找下一个出现次数大于 0 的元音字母 cur = next(c for c in it if cnt[c]) t[i] = cur cnt[cur] -= 1 return ''.join(t)

class Solution { public String sortVowels(String S) { final int VOWEL_MASK = 0x208222; char[] s = S.toCharArray(); int[] cnt = new int['u' + 1]; for (char ch : s) { if ((VOWEL_MASK >> (ch & 31) & 1) > 0) { cnt[ch]++; } } int j = 'A'; for (int i = 0; i < s.length; i++) { if ((VOWEL_MASK >> (s[i] & 31) & 1) == 0) { continue; } // 找下一个出现次数大于 0 的元音字母 while (cnt[j] == 0) { j = j == 'Z' ? 'a' : j + 1; } s[i] = (char) j; cnt[j]--; } return new String(s); } }

class Solution { public: string sortVowels(string s) { const int VOWEL_MASK = 0x208222; int cnt['u' + 1]{}; for (char ch : s) { if (VOWEL_MASK >> (ch & 31) & 1) { cnt[ch]++; } } char j = 'A'; for (char& ch : s) { if ((VOWEL_MASK >> (ch & 31) & 1) == 0) { continue; } // 找下一个出现次数大于 0 的元音字母 while (cnt[j] == 0) { j = j == 'Z' ? 'a' : j + 1; } ch = j; cnt[j]--; } return s; } };

#define VOWEL_MASK 0x208222 char* sortVowels(char* s) { int cnt['z' + 1] = {}; for (int i = 0; s[i]; i++) { if (VOWEL_MASK >> (s[i] & 31) & 1) { cnt[s[i]]++; } } char j = 'A'; for (int i = 0; s[i]; i++) { if ((VOWEL_MASK >> (s[i] & 31) & 1) == 0) { continue; } // 找下一个出现次数大于 0 的元音字母 while (cnt[j] == 0) { j = j == 'Z' ? 'a' : j + 1; } s[i] = j; cnt[j]--; } return s; }

func sortVowels(s string) string { const vowelMask = 0x208222 cnt := ['u' + 1]int{} for _, ch := range s { if vowelMask>>(ch&31)&1 > 0 { cnt[ch]++ } } t := []byte(s) j := byte('A') for i, ch := range t { if vowelMask>>(ch&31)&1 == 0 { continue } // 找下一个出现次数大于 0 的元音字母 for cnt[j] == 0 { if j == 'Z' { j = 'a' } else { j++ } } t[i] = j cnt[j]-- } return string(t) }

var sortVowels = function(s) { const VOWEL_MASK = 0x208222; const cnt = Array('u'.charCodeAt(0) + 1).fill(0); for (const ch of s) { const c = ch.charCodeAt(0); if (VOWEL_MASK >> (c & 31) & 1) { cnt[c]++; } } const t = s.split(''); const ordZ = 'Z'.charCodeAt(0); let j = 'A'.charCodeAt(0); for (let i = 0; i < t.length; i++) { if ((VOWEL_MASK >> (t[i].charCodeAt(0) & 31) & 1) === 0) { continue; } // 找下一个出现次数大于 0 的元音字母 while (cnt[j] === 0) { j = j == ordZ ? 'a'.charCodeAt(0) : j + 1; } t[i] = String.fromCharCode(j); cnt[j]--; } return t.join(''); };

impl Solution { pub fn sort_vowels(s: String) -> String { const VOWEL_MASK: u32 = 0x208222; let mut cnt = [0; 'z' as usize + 1]; for ch in s.bytes() { if (VOWEL_MASK >> (ch & 31)) & 1 > 0 { cnt[ch as usize] += 1; } } let mut s = s.into_bytes(); let mut j = 0; for ch in s.iter_mut() { if VOWEL_MASK >> (*ch & 31) & 1 == 0 { continue; } // 找下一个出现次数大于 0 的元音字母 while cnt[j as usize] == 0 { if j == b'Z' { j = b'a'; } else { j += 1; } } *ch = j; cnt[j as usize] -= 1; } unsafe { String::from_utf8_unchecked(s) } } }

该写法即仓库 b.go 中第 54-81 行的最终版sortVowels（测试实际调用的正是这一版）。

五、三种写法复杂度对比

其中写法三的时间复杂度中n是s的长度，Σ = 10 或 52 或 128是字符集合的大小；空间复杂度 O(Σ) 仅与统计数组大小有关，与输入长度无关。

六、仓库配套：源码、测试数据与自动化验证

这道题在仓库中的完整配套体现了 codeforces-go 项目「题解 + 可运行实现 + 自动化测试」的标准组织方式：

• 题解文档：leetcode/biweekly/109/b/README.md，即本文主体来源；
• Go 实现：leetcode/biweekly/109/b/b.go，包含sortVowels1（写法一）、sortVowels2（写法二）与最终版sortVowels（写法三）三个函数；
• 测试数据：leetcode/biweekly/109/b/b.txt，每两行一组「输入/期望输出」，覆盖普通用例与无元音用例；
• 测试文件：leetcode/biweekly/109/b/b_test.go，调用testutil.RunLeetCodeFuncWithFile从b.txt读取用例驱动sortVowels进行断言比对；
• 测试驱动：leetcode/testutil/leetcode.go 中的RunLeetCodeFuncWithFile负责按函数入参/返回值个数切分数据行、反射调用被测函数并逐用例断言，还支持「无尽对拍」与 TLE 检测等调试能力；
• 用例生成器：copypasta/template/leetcode/generator.go 会从力扣比赛页面自动抓取题目、默认代码与样例，生成x.go/x_test.go/x.txt三件套（其入口测试见 copypasta/template/leetcode/generator_test.go）。

本地运行验证方式

仓库为只读研究用途，你可以在本地git clone后，进入对应目录执行：

cd leetcode/biweekly/109/b go test -run Test_b -v

测试会遍历b.txt中的每个用例，将sortVowels的实际输出与期望输出比对（含超时检测逻辑，见 leetcode.go 的isTLE实现）。若把b_test.go中的targetCaseNum改为-1，则只跑最后一个用例，方便单步调试。

七、技巧迁移与总结

本题的价值不止于 AC 本身，更在于两个可复用技巧：

1. ch & 31大小写统一映射：利用 ASCII 码低 5 位与字母序号的对应关系，把「字符属于某集合」的判断统一到 1..26 的数字域，消除大小写分支；
2. 集合的整数编码（位掩码）：把小集合编码为2^1 + 2^5 + 2^9 + 2^15 + 2^21这样的整数，用(mask >> k) & 1实现 O(1) 集合成员判定。该套路在字符分类、状态压缩、子集枚举等场景同样适用。

从工程视角看，本题的三种写法恰好构成一条完整的优化链条：先保证正确（写法一），再用位运算简化热路径（写法二），最后利用字符集小的特性把排序降为计数（写法三），复杂度从O(n log n)降到O(n + Σ)。配合仓库中自动生成的测试用例与测试框架，每一种写法都能被立即验证——这正是算法题解从「思路」落地为「可信代码」的完整范式。

• 科学计算