#38_报数

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

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"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-and-say
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 先理解一下题意吧
  题目的意思是,后一个数将前一个数从左往右用阿拉伯数字读出来,例如第一个数是 1 ,那么第二个数应该就是: 因为第一个数是1,所以是 1 个 1, 所以第二个数是 11 , 第三个数就是 2 个 1 ,第三个数就是 21, 第四个数就是 1个 2, 1个 1,那么第四个数就是 1211,第五个数就是1个1,1个2,2个1,那么第五个数就是 111221

明白题目问的是什么了,那么就开始说一下解题的思路,我是看了题解(作者：heator
* 链接：https://leetcode-cn.com/problems/two-sum/solution/javahe-cwei-di-gui-0ms-by-heator/)才学会了.

思路:
理解了题意,就可以将自然语言转换为机器语言,用的是递归法,
第一步:是递归出口n==1就直接返回题解str
第二步:外while循环,主要用于判断数字是否相同,不相同则开始下一次循环,用一个count变量来计数有多少个相同的数字
第三步:内while循环,主要用于判断下标没有超出str的长度,并且判断是否同一个数字,如果是同一个数字则count++,然后index指针指向下一个下标来判断是否相等.
第四步:当相邻的两个数不相等,用StringBuilder记录起来,再开始下一次循环,count就重置为1 了,
第五步:递归调用,因为参数n代表的是第几个人报数,直到每个人都报完数了,n == 1,就停止递归了,返回最后的报数 str

---

  //created by Fivezm on 2019.7.20
 public static String countAndSay(int n) {
        return countHelper("1", n);
    }

    public static String countHelper(String str, int n) {
        if (n == 1) return str; //递归出口
        int len = str.length();
        int index = 0;
        StringBuilder sb = new StringBuilder();
        while (index < len) {
            int count = 1; // count 计数
            while (index + 1 < len && str.charAt(index) == str.charAt(index + 1)) { // 如果一直是同一个数
                count++;
                index++;
            }
            //当相邻的两个数不相等,用sb记录起来,再开始下一次循环,count就重置为1 了,
            sb.append("" + count + str.charAt(index));
            index++;
        }
        return countHelper(sb.toString(), n - 1);
    }