38. Count and Say

38. Count and Say

The count-and-say sequence is the sequence of integers with the first five terms as following:

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 where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1: Input: 1 Output: “1”

Example 2: Input: 4 Output: “1211”

题意理解

这道题根据给的5个例子可以知道它是在计数，从第一个序列1开始，后面的每一个序列就是在对前面一个数列进行计数，1是1个1所以是11（n=2时)，11是2个1所以是21(n=3),21是1个2和1个1所以是1211…以此类推,遇到不同的数出现就要重新计数，数量在前具体数字在后

纯String解法

需要用到string的charAt(int index)方法，可以返回指定索引处的 char 值， 用到两个String pre和res来传递上一个string和正在计算的string

class Solution { public String countAndSay(int n) { if(n==0) return null; String res="1"; for(int i=1;i<n;i++){ String pre=res; res=""; int cnt=1; char num=pre.charAt(0); for(int j=1;j<pre.length();j++) { if(pre.charAt(j)==num){ cnt++; } else{ res=res+cnt+num; num=pre.charAt(j); cnt=1; } } res=res+cnt+num; } return res; } }

改写为stringbuilder

class Solution { public String countAndSay(int n) { if(n==0) return null; StringBuilder res=new StringBuilder("1"); for(int i=1;i<n;i++){ StringBuilder pre=res; res=new StringBuilder(); int cnt=1; char num=pre.charAt(0); for(int j=1;j<pre.length();j++) { if(pre.charAt(j)==num){ cnt++; } else{ res=res.append(cnt).append(num); num=pre.charAt(j); cnt=1; } } res.append(cnt).append(num); } return res.toString(); } }