leetcode38. 外观数列-蒲公英云

leetcode38. 外观数列

短命女 2023-07-23 10:00 103阅读 0赞

题目描述：

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", “one 1" （"一个二" , "一个一") , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。

注意：整数序列中的每一项将表示为一个字符串。

思路：

思路不难，实现起来稍微复杂。就是按照你在纸上求解的思路，进行实现。遍历的时候计数，碰到不同的数字就把前面记录的写下来。当遍历到最后也到再添加记录。整体的思路比较明确，但是实现的方式还是复杂很多。可以用其他的容器来消除冗余代码。

class Solution {
    public String countAndSay(int n) {
        // 添加原始数据1
        List<Character> original = new ArrayList<Character>();
        original.add('1');
        if(n == 1)
            return "1"; // 基础样例
        List<Character> replace; // 替换数组
        int i, j, count = 0;
        char temp;
        for(j = 1; j < n; j++) {
            count = 0;
            temp = original.get(0);
            replace = new ArrayList<Character>();
            for(i = 0; i < original.size(); i++) {            
                if(original.get(i) == temp) { // 找个数
                    count++;
                }
                if(original.get(i) != temp) { // 碰到不同就add
                    replace.add(String.valueOf(count).charAt(0)); // 这里添加int类型的数字要转型
                    replace.add(temp);
                    temp = original.get(i);
                    count = 1;
                }
                if(i == original.size() - 1) { // 遍历到最后再add一次
                    replace.add(String.valueOf(count).charAt(0));
                    replace.add(temp);
                    original = replace;
                    break;
                }        
            }
        }    
        StringBuilder sBuilder = new StringBuilder(); // 最后把数组转为字符串
        for(char x : original)
            sBuilder.append(x);
        return sBuilder.toString();
    }
}