LeetCode：38

LeetCode38

因为快要临近找工作的原因，所以最近时不时地在LeetCode官网上刷题。实习学的是Java，故代码也用 Java 实现了。

因为原来很少接触代码刷题，所以LeetCode上有的题目都需要认真看几遍才能看懂- -。真的是很惭愧啊。

题目链接： Count and Say

乍一看这个题，我第一反应，这是个什么鬼，一堆数字，好像很复杂的样子。但仔细看一两遍，就能明白其中意思。

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

首先官网给了我们前五个数的示例，但是当时我看的可谓是一脸懵逼

1. 1

2. 11

3. 21

4. 1211

5. 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.

个人理解：

第一个数为1，第二个数要读出（输出）第一个数（1）中1的个数+数本身，也就是11（1个1） 2. 11

得到第二个数为11之后，第三个数要读出（输出）第二个数（11）中1的个数+数，也就是21（2个1） 3. 21

有了第三个数21，第四个数很容易得到了。读出（输出）第三个数中（21）中2的个数+数 以及1的个数+数 1211（1个2，1个1） 4. 1211

Given an integer n, 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   Then   Output: “1”

***在输入1，根据例子1，我们输出1。

Example 2:

Input: 4   Then   Output: “1211”

***也就是说，如果输入4的话，我们要输出前五个例子中的4：1211

思路整理

现在明白了题目的意思，我们就可以开始思考如何解这道题了。这个题的算法大致就是，将 前一个数 ，找出 连续相同元素 ，把这个元素 个数 和 该元素 存到新的string里，最后输出为字符串的形式。

代码实现

public String countAndSay(int n) {
	if(n<=0)
	return "";  //如果输入的n为0或负数，直接返回""
	StringBuilder say = new StringBuilder();
	say.append("1");  //将第一个数1，append到say中

	for(int i=1; i < n; i++){  //若n大于等于2，进入循环
		String str = say.toString();  //str用于存放上一个数
		say = new StringBuilder();   //更新当前数，用于say
		int count = 0;
		Character ch = str.charAt(0);
		for(Character c : str.toCharArray()) {  //开始整理计数相同元素的个数
			if(c == ch) {
				count++;
			} else {  //遇到不相同，即把原来统计到的个数以及元素，append到say中
				say.append(count);
				say.append(ch);

				ch = c;   //将不同的元素替换给ch，用于下一次循环
				count = 1;  //不同的元素已经出现过一次了，故记为1
			}
		}
		say.append(count);  //将最后相同元素个数以及元素append进say中，以防缺少最后元素。
		say.append(ch);
	}

	return say.toString();
	}

总结

查看过Disscussion，里面有利用到递归Recursive的思想。Recursive的方法相比于上面的方法，执行时间更短，（Recursive 2ms；本文方法 3ms）但是较难理解。后期有时间，会分析探讨一下。