LeetCodeT38CountandSay

题目地址

中文&＃xff1a;https://leetcode-cn.com/problems/count-and-say/
英文&＃xff1a;https://leetcode.com/problems/count-and-say/

题目描述

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

• countAndSay(1) &＃61; “1”
• countAndSay(n) is the way you would “say” the digit string from countAndSay(n-1), which is then converted into a different digit string.
  To determine how you “say” a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.

For example, the saying and conversion for digit string “3322251”:

Given a positive integer n, return the nth term of the count-and-say sequence.

Example 1:

Input: n &＃61; 1
Output: "1"
Explanation: This is the base case.


Example 2:

Input: n &＃61; 4
Output: "1211"
Explanation:
countAndSay(1) &＃61; "1"
countAndSay(2) &＃61; say "1" &＃61; one 1 &＃61; "11"
countAndSay(3) &＃61; say "11" &＃61; two 1&＃39;s &＃61; "21"
countAndSay(4) &＃61; say "21" &＃61; one 2 &＃43; one 1 &＃61; "12" &＃43; "11" &＃61; "1211"


Constraints:

1 <&＃61; n <&＃61; 30

思路

题目的定义就是递归定义的&＃xff0c;所以用递归解题~

题解

class Solution {public String countAndSay(int n) {if(n&＃61;&＃61;1) return "1";else {String s &＃61; countAndSay(n-1);String str &＃61; "";int len &＃61; s.length();int i &＃61; len-1;while(i>&＃61;0){int cnt &＃61; 0;char a &＃61; s.charAt(i);while(i>&＃61;0&&s.charAt(i)&＃61;&＃61;a){cnt&＃43;&＃43;;i--;}str &＃61;cnt&＃43;""&＃43;a&＃43;str;cnt &＃61; 0;}return str;}}
}