算法

leetcode [#38]

目录

题目

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …

1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.
Given an integer n, generate the nth sequence.

Note:
The sequence of integers will be represented as a string.

解决方案

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
public class Solution {
    public String countAndSay(int n) {
        int flag = 0;
        String str = "1";
        StringBuilder temp = new StringBuilder();
        temp.append("1");
        while (flag < n-1){
            int i = 0;
            StringBuilder builder = new StringBuilder();
            while (i < temp.length()){
                if(temp.charAt(i) == '1'){
                    if(i == temp.length() - 1){
                        builder.append("11");
                        i += 1;
                        continue;
                    } else if(i == temp.length() - 2){
                        if(temp.charAt(i+1) == '1'){
                            builder.append("21");
                        } else if(temp.charAt(i+1) == '2'){
                            builder.append("1112");
                        } else {
                            builder.append("1113");
                        }
                        i += 2;
                        continue;
                    } else {
                        if(temp.charAt(i+1) == '1'){
                            if(temp.charAt(i+2) == '1'){
                                builder.append("31");
                                i += 3;
                                continue;
                            } else {
                                builder.append("21");
                                i += 2;
                                continue;
                            }
                        } else if(temp.charAt(i+1) == '2'){
                            if(temp.charAt(i+2) == '2'){
                                builder.append("11");
                                i += 1;
                            } else {
                                builder.append("1112");
                                i += 2;
                            }
                            continue;
                        } else {
                            if(temp.charAt(i+2) == '3'){
                                builder.append("11");
                                i += 1;
                            } else {
                                builder.append("1113");
                                i += 2;
                            }
                            continue;
                        }
                    }
                } else if(temp.charAt(i) == '2'){
                    if(i == temp.length() - 1){
                        builder.append("12");
                        i += 1;
                        continue;
                    } else if(i == temp.length() - 2){
                        if(temp.charAt(i+1) == '2'){
                            builder.append("22");
                            i += 2;
                            continue;
                        } else {
                            builder.append("12");
                            i += 1;
                            continue;
                        }
                    } else {
                        if(temp.charAt(i+1) == '2'){
                            if(temp.charAt(i+2) == '2'){
                                builder.append("32");
                                i += 3;
                                continue;
                            } else {
                                builder.append("22");
                                i += 2;
                                continue;
                            }
                        } else {
                            builder.append("12");
                            i += 1;
                            continue;
                        }
                    }
                } else {
                    if(i == temp.length() - 1){
                        builder.append("13");
                        i += 1;
                        continue;
                    } else if(i == temp.length() - 2){
                        if(temp.charAt(i+1) == '3'){
                            builder.append("23");
                            i += 2;
                        } else {
                            builder.append("13");
                            i += 1;
                        }
                        continue;
                    } else {
                        if(temp.charAt(i+1) == '3'){
                            if(temp.charAt(i+2) == '3'){
                                builder.append("33");
                                i += 3;
                            } else {
                                builder.append("23");
                                i += 2;
                            }
                            continue;
                        } else {
                            builder.append("13");
                            i += 1;
                            continue;
                        }
                    }
                }
            }
            temp = builder;
            flag++;
        }
        return temp.toString();
    }
}

注意事项

  1. 本题重在找到数字序列的变化规律。第n代的结果一定是偶数个元素，因为每个数字都会被表示成“几个几”的形式。结果序列是由一系列1,2,3构成的。
  2. 状态转移图如下：

      1 -> 11
      2 -> 12
      3 -> 13
     11 -> 21
     12 -> 1112
     13 -> 1113
     22 -> 22
     33 -> 23
    111 -> 31
    222 -> 32
    333 -> 33

  3. 根据上述状态转移图，遍历每次生成的字符串（此处是StringBuilder），决定下一次输出的是什么。
分享到： QQ空间 新浪微博 腾讯微博 微信 更多