题目描述（简单难度）

难在了题目是什么意思呢？

初始值第一行是 1。

第二行读第一行，1 个 1，去掉个字，所以第二行就是 11。

第三行读第二行，2 个 1，去掉个字，所以第三行就是 21。

第四行读第三行，1 个 2，1 个 1，去掉所有个字，所以第四行就是 1211。

第五行读第四行，1 个 1，1 个 2，2 个 1，去掉所有个字，所以第五航就是 111221。

然后题目要求输入 1 - 30 的任意行数，输出该行是啥。

解法一 递归

可以看出来，我们只要知道了 n - 1 行，就可以写出第 n 行了，首先想到的就是递归。

第五行是 111221，求第六行的话，我们只需要知道每个字符重复的次数加上当前字符就行啦。

1 重复 3 次，就是 31，2 重复 2 次就是 22，1 重复 1 次 就是 11，所以最终结果就是 312211。

时间复杂度：

空间复杂度：O（1）。

解法二 迭代

  2.     String res = "1";
  3.     //从第一行开始，一行一行产生
  4.     while (n > 1) {
  5.         String temp = "";
  6.         for (int i = 0; i < res.length(); i++) {
  7.             int num = getRepeatNum(res.substring(i));
  8.             //跳过重复的字符
  9.             i = i + num - 1;
  11.         n--;
  12.         //更新
  13.         res = temp;
  14.     }
  15.     return res;
  17. }
  18. private int getRepeatNum(String string) {
  20.     char same = string.charAt(0);
  21.     for (int i = 1; i < string.length(); i++) {
  22.         if (same == string.charAt(i)) {
  23.             count++;
  24.         } else {
  25.             break;
  26.         }
  27.     }

时间复杂度：

空间复杂度：O（1）。

总

递归里边又用了一个递归，我觉得这点有点意思。

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^