LeetCode-38 报数

深藏阁楼爱情的钟 2022-03-30 13:50 212阅读 0赞

### 文章目录 ###

*   *   *  题目描述
         *  我的解法
         *  其他思路
         *  总结
         *  Github

### 题目描述 ###

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

> 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 项。

注意：整数顺序将表示为一个字符串。

示例 1:

> 输入: 1  
> 输出: “1”

示例 2:

> 输入: 4  
> 输出: “1211”

--------------------

### 我的解法 ###

public String countAndSay(int n) { 
    
            StringBuilder initString = new StringBuilder("1");//初始化的字符串,注：已经初始化，代表第一步已经完成,之后遍历到n-1即可
            char[] initStringCharArray = null;
            int count = 1;
    
    
            for(int i=0; i<n-1; i++){ 
                initStringCharArray = initString.toString().toCharArray();
                StringBuilder resultString = new StringBuilder();//接受改变之后的结果的字符串
                for(int j=0; j<initStringCharArray.length; j++){ //选择分情况讨论的方法
                    if(j<initStringCharArray.length-1 && initStringCharArray[j] == initStringCharArray[j+1]){ 
                        count++;
                    }else{ 
                        resultString.append(count).append(initStringCharArray[j]);
                        count = 1;//每次遍历完将count置为初始值
                    }
                }
                initString = resultString;
            }
    
            return initString.toString();
        }

用时：3 ms  
击败：93.95%

--------------------

### 其他思路 ###

提供一个LeetCode上跑分2ms的，思路差不多，没有让人眼前一亮的感觉，而且调用了其他函数增加了系统栈开销。我本机是跑出了5ms，所以仅供参考。

public String countAndSay1(int n) { 
            String a="1";
            for (int i = 1; i < n; i++) { 
                a=changString(a);
            }
            return a;
        }
    
        private String changString(String a) { 
            char[] chars=a.toCharArray();
            char cur=' ';
    
            StringBuilder builder=new StringBuilder();
            int num=0;
            for (int i = 0; i < chars.length; i++) { 
                if(cur==chars[i]){ 
                    num++;
                }else { 
                    if (num!=0){ 
                        builder.append(num);
                        builder.append(cur);
                    }
                    num=1;
                    cur=chars[i];
                }
            }
            builder.append(num);
            builder.append(cur);
            return builder.toString();
        }

--------------------

### 总结 ###

1.  一定要明确自己程序取值的边界（区间开闭），以及循环的次数
2.  本题目不难，值得一说的是在于审题审半天，一定读明白了再编程

--------------------

### Github ###

[LeetCode刷题笔记][LeetCode]

[LeetCode]: https://github.com/Meidanlong/LeetCode