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