ARST打卡第332周

Linmin.Shan included in ARST

2025-09-14 954 words 2 minutes

Contents

Algorithm

lc966_元音拼写检查器

思路:

直接模拟遍历，先找是否全匹配，再找是否大小写替换，最终再找是否元音替换。

会超时。O(n^2)不行。

优化思路：使用HashMap预处理所有匹配规则，将时间复杂度降低到O(n+m)。

具体优化方案：

使用HashSet存储原始单词，完全匹配时O(1)查找
使用HashMap将小写版本映射到第一个匹配的原始单词
使用HashMap将元音模式映射到第一个匹配的原始单词
元音模式：将所有元音(a,e,i,o,u)替换为通配符’*'

时间复杂度：O(n+m)，其中n是查询数量，m是单词列表长度空间复杂度：O(m)，用于存储预处理的映射表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60


use std::collections::{HashSet, HashMap};

impl Solution {
    pub fn spellchecker(wordlist: Vec<String>, queries: Vec<String>) -> Vec<String> {
        // 1. 完全匹配的HashSet - O(1)查找
        let word_set: HashSet<String> = wordlist.iter().cloned().collect();
        
        // 2. 大小写不敏感的HashMap - 映射小写版本到第一个原始单词
        let mut case_map: HashMap<String, String> = HashMap::new();
        
        // 3. 元音替换的HashMap - 映射元音替换版本到第一个原始单词
        let mut vowel_map: HashMap<String, String> = HashMap::new();
        
        // 预处理：构建映射表
        for word in &wordlist {
            let lower_word = word.to_lowercase();
            let vowel_word = Self::to_vowel_pattern(&lower_word);
            
            // 只保存第一个匹配的单词（保证优先级）
            case_map.entry(lower_word).or_insert(word.clone());
            vowel_map.entry(vowel_word).or_insert(word.clone());
        }
        
        // 处理查询
        let mut res = vec![];
        for query in queries {
            // 1. 完全匹配（区分大小写）
            if word_set.contains(&query) {
                res.push(query);
            }
            // 2. 大小写不匹配
            else if let Some(word) = case_map.get(&query.to_lowercase()) {
                res.push(word.clone());
            }
            // 3. 元音错误
            else if let Some(word) = vowel_map.get(&Self::to_vowel_pattern(&query.to_lowercase())) {
                res.push(word.clone());
            }
            // 4. 无匹配
            else {
                res.push(String::new());
            }
        }
        
        res
    }
    
    // 将单词转换为元音模式（所有元音替换为'*'）
    fn to_vowel_pattern(word: &str) -> String {
        word.chars()
            .map(|c| {
                if "aeiou".contains(c) {
                    '*'
                } else {
                    c
                }
            })
            .collect()
    }
}

Review

一天真的需要走一万步吗？【TED演讲】

只要每天增加步数，对身心健康都有好处。

Tip

检测大佬的hype持仓情况

Die With Zero阅读感悟

人生是时间，身心健康，金钱的集合，一辈子是人生体验的集合，所以应该在死前尽可能提高人生体验。
在上述目标下，应该在死前花光所有的钱，时间。
为了陷入不敢花钱全留着应对医疗的困境，可以买重疾险，应对死的早或者死的晚没钱花，可以买年金。
如果有孩子，提前把钱在孩子25-35之间给他们，剩下的自己的钱Die With Zero。
要了解自己的身心健康，金钱，时间的各阶段的平衡，尽量让自己能在健康的时候多花钱去创造好的体验。
多思考优化人生体验，而不是一直使用世俗给的缺省路径，处于一种别人怎么活我就怎么活的盲目auto pilot状态。

Contents

ARST打卡第332周

Algorithm

Review

Tip

Share