38. Count and Say
The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, …
1 is read off as “one 1” or 11.
11 is read off as “two 1s” or 21.
21 is read off as “one 2, then one 1” or 1211.
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.
题意:
计数和说序列是整数序列,如下所示: 1, 11, 21, 1211, 111221, …
也就是说:
n = 1<------------------>1
n = 2<------------------>11
n = 3<------------------>21
n = 4<------------------>1211
n = 5<------------------>111221
……………
每个n所对应的序列值,是通过n-1对应序列相同元素个数和此元素组合构成的。
思路:
如题意所述,n=1时输出字符串1;n=2时,数上次字符串中的数值个数,因为上次字符串有1个1,所以输出11;n=3时,由于上次字符是11,有2个1,所以输出21;n=4时,由于上次字符串是21,有1个2和1个1,所以输出1211。依次类推,可以直接递归实现。
1 | class Solution { |
非递归实现:
1 | class Solution { |
Java Code:
1 | class Solution { |