Contents

ARST打卡第316周

Algorithm

lc2131_连接两字母单词得到的最长回文串

思路:

其实是个思维题,只要找到一对ab,ba,其他的aa都可以加入长度,否则就是只有一个aa.

所以思路就是先hashmap统计计数,然后直接遍历一次hashmap,如果是ab,则查找ba,如果存在,则加入成对的长度值。

并且设置 aa 对的长度是可以直接加入 ans 的。

也就是一个 hashmap, 一个 vis 数组,一个 ans 变量,一个 aa_ans 变量, 然后一个 bool 变量确定 aa 是否能加入(判断依据就是有ab 和 ba 这种pair)。

翻车了一次,因为aa如果超过两次,也算一对ab,ba,所以需要判断一下。

又翻车一次: 注意aa版本奇偶数的区别,所有的aa只能有一个当奇数的中间值,不能所有的奇数都放在回文正中间。

 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
61
62
63
64
65
66
impl Solution {
    pub fn longest_palindrome(words: Vec<String>) -> i32 {
        let mut map = std::collections::HashMap::new();
        let mut ans = 0;
        let mut aa_ans = 0;
        let mut has_pair = false;
        let mut has_odd_aa = false;

        // 统计每个单词出现次数
        for word in words.iter() {
            *map.entry(word.clone()).or_insert(0) += 1;
        }

        let mut vis = std::collections::HashMap::new();
        // 遍历map中的每一对键值
        for (word, count) in map.iter() {
            if vis.contains_key(word) {
                continue;
            }
            vis.insert(word.clone(), true);

            let first_char = word.chars().nth(0).unwrap();
            let second_char = word.chars().nth(1).unwrap();
            
            if first_char == second_char {
                // 处理aa类型单词
                if *count % 2 == 0 {
                    // 偶数个aa,全部可以配对
                    aa_ans += 2 * count;
                } else {
                    // 奇数个aa,先处理偶数部分
                    aa_ans += 2 * (*count - 1);
                    // 如果还没有奇数aa放在中间,就把这个放在中间
                    if !has_odd_aa {
                        aa_ans += 2;
                        has_odd_aa = true;
                    }
                }
                if *count > 1 {
                    has_pair = true;
                }
            } else {
                // 处理ab类型单词
                // 查找是否存在ba类型单词
                let rev_word = format!("{}{}", second_char, first_char);
                
                if let Some(rev_count) = map.get(&rev_word) {
                    // 找到了ba,成对处理,每对贡献4个字符
                    vis.insert(rev_word.clone(), true);
                    ans += 4 * std::cmp::min(*count, *rev_count);
                    has_pair = true;
                }
            }
        }

        // 如果有一对ab-ba,那么所有aa都可以加入
        if has_pair {
            ans += aa_ans;
        } else if aa_ans > 0 {
            // 如果没有ab-ba对,但有aa,则选择一个aa
            ans += 2;
        }

        ans
    }
}

题解更精炼,学习:

 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
use std::collections::HashMap;
use std::cmp::{min, max};

impl Solution {
    pub fn longest_palindrome(words: Vec<String>) -> i32 {
        let mut freq = HashMap::new();
        for word in &words {
            *freq.entry(word.clone()).or_insert(0) += 1;
        }
        let mut res = 0;
        let mut mid = false;
        for (word, cnt) in &freq {
            let rev = format!("{}{}", word.chars().nth(1).unwrap(), word.chars().nth(0).unwrap());
            if *word == rev {
                if cnt % 2 == 1 {
                    mid = true;
                }
                res += 2 * (cnt / 2 * 2);
            } else if *word > rev {
                res += 4 * min(*cnt, *freq.get(&rev).unwrap_or(&0));
            }
        }
        if mid {
            res += 2;
        }
        res
    }
}

Review

【TED演讲】我们为什么工作(思考工作的方式)

不是我们很无聊,所以做无聊的工作,而是因为工作形式导致了无聊,需要设计新的工作方式,设计出新的人性思考。

Tips

solana-web3js

这个文档可以2小时快速上手solana-web3js,非常直接。

Share

拆解 Adrena Protocol