Count and Say

2018-06-12

数数并说

报数序列是指一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", “one 1" （"一个二" , "一个一") , 即 1211。

给定一个正整数 n ，输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

示例 1:

1 2	输入: 1 输出: "1"

示例 2:

1 2	输入: 4 输出: "1211"

思路：屎一样的题干描述，看了好几遍都不理解题意，去看了英文原版的leetcode题目，发现英文的描述也是too weak。好在国外的leetcode网站可以查看每道题的discuss，终于在一个https://www.geeksforgeeks.org/look-and-say-sequence/ 这样的链接下找出了这道题到底想要说个啥。下面主要解释下题意：

　　首先，给了第一个字符串：”1”，我们可以读做”一个1”，转换成数字就是11，然后这个”11”就被当做了第二个字符串，这样第三个字符串就是去读这个”11”,读作”两个1“，即”21”。然后再读这个”21”为”一个2一个1”，用数字表示就是”1211”，依此类推就可以得到第n个字符串是什么了。

　　理解题意以后，这道题就不难解了。题目是给定了n去求第n个，因为有规律，且第n个字符串是什么取决于第n-1个字符串，所以想到了递归。

代码如下:

public class CountAndSay {
	 /**
	  * 找到规律后就是很简单的递归了，每一个字符串只和前一个字符串有关
	  * @param n
	  * @return
	  */
	 public static String countAndSay(int n) {
	        if(n==1){
	            return "1";
	        }
	        String previous="";
	        if(n>1){
	            previous=new String(countAndSay(n-1));
	        }
	        return helper(previous);
	        
	    }
	 /**
	  * 通过已有的字符串确定下一个字符串的方法，这里也用到了递归
	  * @param s
	  * @return
	  */
	 public static String helper(String s){
	        
		 	int len=s.length();
	        if(len==0){
	            return "";
	        }
	        //如果只剩一个字符，就数一个+字符
	        if(len==1) {
	        	return "1"+s.charAt(0);
	        }
	        char a=s.charAt(0);
	        int count=0;
	        int i=0;
	        while(s.charAt(i)==a){
	            i++;
	            if(i==len) {
	            	break;
	            }
	        }
	        count=i;
	        String cs=String.valueOf(count);
	        String temp=new String(s.substring(i,len));
	        return cs+a+helper(temp);
	    }
	    public static void main(String[] args) {
			String s="1122";
			System.out.println(helper(s));
			int n=3;
			System.out.println(countAndSay(n));
		}
}