题目描述（简单难度）

难在了题目是什么意思呢？ 初始值第一行是 1。 第二行读第一行，1 个 1，去掉个字，所以第二行就是 11。 第三行读第二行，2 个 1，去掉个字，所以第三行就是 21。 第四行读第三行，1 个 2，1 个 1，去掉所有个字，所以第四行就是 1211。 第五行读第四行，1 个 1，1 个 2，2 个 1，去掉所有个字，所以第五航就是 111221。 第六行读第五行，3 个 1，2 个 2，1 个 1，去掉所以个字，所以第六行就是 312211。 然后题目要求输入 1 - 30 的任意行数，输出该行是啥。

解法一 递归

可以看出来，我们只要知道了 n - 1 行，就可以写出第 n 行了，首先想到的就是递归。 第五行是 111221，求第六行的话，我们只需要知道每个字符重复的次数加上当前字符就行啦。 1 重复 3 次，就是 31，2 重复 2 次就是 22，1 重复 1 次 就是 11，所以最终结果就是 312211。 1. public String countAndSay(int n) { 2. //第一行就直接输出 3. if (n == 1) { 4. return "1"; 5. } 6. //得到上一行的字符串 7. String last = countAndSay(n - 1); 8. //输出当前行的字符串 9. return getNextString(last); 10. 11. } 12. 13. private String getNextString(String last) { 14. //长度为 0 就返回空字符串 15. if (last.length() == 0) { 16. return ""; 17. } 18. //得到第 1 个字符重复的次数 19. int num = getRepeatNum(last); 20. // 次数 + 当前字符 + 其余的字符串的情况 21. return num + "" + last.charAt(0) + getNextString(last.substring(num)); 22. } 23. 24. //得到字符 string[0] 的重复个数，例如 "111221" 返回 3 25. private int getRepeatNum(String string) { 26. int count = 1; 27. char same = string.charAt(0); 28. for (int i = 1; i < string.length(); i++) { 29. if (same == string.charAt(i)) { 30. count++; 31. } else { 32. break; 33. } 34. } 35. return count; 36. }

时间复杂度： 空间复杂度：O（1）。

解法二 迭代

既然有递归，那就一定可以写出它的迭代形式。 1. public String countAndSay(int n) { 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. temp = temp + num + "" + res.charAt(i); 9. //跳过重复的字符 10. i = i + num - 1; 11. } 12. n--; 13. //更新 14. res = temp; 15. } 16. return res; 17. 18. } 19. //得到字符 string[0] 的重复个数，例如 "111221" 返回 3 20. private int getRepeatNum(String string) { 21. int count = 1; 22. char same = string.charAt(0); 23. for (int i = 1; i < string.length(); i++) { 24. if (same == string.charAt(i)) { 25. count++; 26. } else { 27. break; 28. } 29. } 30. return count; 31. }

时间复杂度： 空间复杂度：O（1）。

总

递归里边又用了一个递归，我觉得这点有点意思。 添加好友一起进步~ 如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^ 如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情