每天一题LeetCode【第28天】

T38. Count and Say【Easy】

题目

count-and-say 队列是一个整数队列，它是这样开始的：

1，11，21，1211，111221，...
1 可以读为 "one 1" 或者 11
11 可以读为 "two 1s" 或者 21
21 可以读为 "one 2" ，然后是 "one 1" 或者 1211

给出一个n, 求出第 n 个队列是什么。

注意：整数序列将表示为字符串。

思路

首先，看讨论说这题题意不清楚，有的人还是弄错题意，于是咱们把例子再举得长一点，据说这样比较不容易误解：

 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221 
 6.     312211
 7.     13112221
 8.     1113213211
 9.     31131211131221
 10.    13211311123113112211

总的来说就是从左往右数数呗，碰到重复的就说几个啥啥啥这样。比如4->5,读出来是"1个1，1个2，2个1"，提取其中的数字就是 111221 。

代码主要分成两部分：

① 数数的方法

② n次迭代的方法

具体看代码以及注释~

代码

代码取自 Top Solution，稍作注释

public String countAndSay(int n) {
        //当是 1 的时候，则直接返回 1
        if(n == 1){
            return "1";
        }
        //为了str末尾的标记，方便后面循环读数
        String str = countAndSay(n-1) + "*";
        //转化成char数组
        char[] c = str.toCharArray();
        int count = 1;
        String s = "";
        for(int i = 0; i < c.length - 1;i++){
          //上面的*标记这里方便统一处理（最后一个不用特殊处理了）
            if(c[i] == c[i+1]){
            //计数增加，算重复
                count++;
            }else{
               //添加字符串并把count置1
                s = s + count + c[i];
                count = 1;//初始化
            }
        }
        return s;

补充

① 对字符串处理时用 toCharArray() 把它先转化成 char 数组是一种常用方法

② 对于首尾字符串的处理还有添加一些无关字符串这样的做法