外观数列

针对外观数列问题，主要需要解决其中的每个字符串出现的次数如何统计。

第一种:直接循环构建

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
impl Solution {
    pub fn count_and_say(n: i32) -> String {
        let mut a = Vec::with_capacity(1 << 12);
        let mut b = Vec::with_capacity(1 << 12);
        a.push('1');
        for _ in 1..n {
            b.clear();
            let mut lst = '\0'; //上一个字符
            let mut cnt = 0; //连续相同字符的数量
            for &c in a.iter() {
                if lst != c {
                    if cnt > 0 {
                        b.extend(cnt.to_string().chars());
                        b.push(lst);
                    }
                    lst = c;
                    cnt = 1;
                } else {cnt += 1}
            }
            b.extend(cnt.to_string().chars());
            b.push(lst);
            let t = a;
            a = b;
            b = t;
        }
        a.into_iter().collect()
    }
}

第二种：递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
    pub fn count_and_say(n: i32) -> String {
        if n == 1 {
            return "1".to_string();
        }
        let prev = Solution::count_and_say(n - 1);
        let mut result = String::new();
        let mut count = 1;
        let chars: Vec<char> = prev.chars().collect();
        for i in 1..chars.len() {
            if chars[i] == chars[i - 1] {
                count += 1;
            } else {
                result.push_str(&count.to_string());
                result.push(chars[i - 1]);
                count = 1;
            }
        }
        result.push_str(&count.to_string());
        result.push(chars[chars.len() - 1]);
        result
    }
}