CountAndSay [source code]
public class CountAndSay {
static
/******************************************************************************/
public class Solution {
public String countAndSay(int n) {
String[] memo = {"", "1", "11", "21", "1211", "111221"};
if (n <= 5) return memo[n < 0 ? 0 : n];
char[] chs = memo[5].toCharArray(), next = chs;
for (int i = 6; i <= n; i++) {
if (chs != next) chs = next;
int len = chs.length;
int count = 0;
for (int j = 1; j < len; j++) if (chs[j] != chs[j - 1]) count++;
next = new char[2 * (count + 1)];
count = 0;
int freq = 0;
for (int j = 1; j < len; j++) {
if (chs[j] != chs[j - 1]) {
next[0 + 2 * count] = (char) (freq + 1 + '0');
freq = 0;
next[1 + 2 * count] = chs[j - 1];
count++;
} else {
freq++;
}
}
next[0 + 2 * count] = (char) (freq + 1 + '0');
next[1 + 2 * count] = chs[len - 1];
}
return String.valueOf(next);
}
}
/******************************************************************************/
public static void main(String[] args) {
CountAndSay.Solution tester = new CountAndSay.Solution();
System.out.println(tester.countAndSay(Integer.parseInt(args[0])));
}
}
这个题目的意思真的是难以理解, Google 了一下别人的解释:
题目好难理解，要不是看了别人的题目解释我真心不知道要想多久才知道它的意思。一开始我以为来一个数，将它表示为后面的形式就可以了。所以就写了个来一个数转换为读出的形式。然后自然是错了。
题目的意思是按照一定的规则出现数字，以字符串的形式。规定第一个是1，接下去就是按照前一个数的读法记录，所以第二个就是1个1，记录为11，那第三个就是对11的读法就是2个1，记录为21，第四个就是对21的读法，一个2一个1，记录为1211，一次类推估计应该知道什么意思了吧。Facebook出这样的题果然思维略叼啊。
这个是一个 DP 的问题, 而且是一个好像 table 只要一维就可以解决的 DP 问题, 我模仿之前 PaintFence 那一题的思路, table 的初始化直接用 literal; 故意在前面加了一个, 这样就处理了这里的 argument 的 n 不是0-based 的问题;
另外1-based 的 index 要记得在循环的最后边界取等号, 这个还老生常谈了;
另外发现了一个我之前没有意识到的问题, 就是用 literal 初始化 table 是有局限性的, 这个局限性就是我们不需要维护整个 table, 只需要比如, 这里的维护几个 var 就行了; 如果需要维护整个表格, 这个做法是不行的, 还是得先 specify 维度初始化一个大表格, 然后把你想要手动初始化的几个 entry 先主动填上. 这个局限性的原因是因为你用 literal 初始化的表格一旦初始化完毕, size 就整个固定了;
这一题的话, 其实还是可以用这个办法的.
刚开始有一个地方用的是freq + 1 + '0'来完成一个 int 转 char, 但是这个一直报lossy, 后来就干脆直接用 cast 了; 注意 cast 的时候, (char) (freq + 1) 是不对的, 应该用(char) (freq + 1 + '0').
理解了题目的意思以后, 题目的核心算法其实是很简单的, 就是数 run, 这个是最常规的算法了;
但是这个算法在细节的处理上面比较麻烦, 尤其是每个 var 的 Corner Case. 如果自己想不清楚, 一个比较好的办法还是搞一个例子, 然后写 trace. 写 trace 的时候有一个技巧:
Variable Trace: Before iteration and After iteration
比如这个题目, 我用的例子是1 1 1 2 2 2 3 3
那么实际上的 trace 的形式可以是(freq):
Before iteration: 0 1 2 0 1 2 0
Iteration Entry: 1 1 1 2 2 2 3 3
After Iteration: 1 2 0 1 2 0 1
养成这样的一个习惯, 真正面试的时候如果紧张, 也能把 trace 写出来;
最后的速度是3ms (97%), 最优解;
如果 var 的更新上面感觉处理不习惯, 可以用类似prev的思路, 这样代码会容易理解很多, 不过这个题目就算是硬做也是可以的;
stream算法的尾巴处理
这个也是碰到过好几次了, 注意一下就行了;
discussion里面的解法基本都差不多;
discussion 里面有人提到, 你怎么保证 count 永远不会超过10? 这个其实不难证明, 直接 induction 证明就行了: 相邻的四位是: count_1 say_1 count_2 say_2. say_1 and say_2肯定不相等, 所以每相邻四位里面肯定有两位不相同, count 连4都不会超过;
另外我自己的做法是先过一遍找到 run 的个数, discussion 里面有一个更好的思路, 直接用 StringBuilder, 这样既可以有类似 list 的 append 的操作, 又不会导致 List 的 overhead;
Problem Description
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, 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"
The following are the terms from n=1 to n=10 of the count-and-say sequence:
- 1
- 11
- 21
- 1211
- 111221
- 312211
- 13112221
- 1113213211
- 31131211131221
- 13211311123113112211
Hide Hint 2
To generate the nth term, just count and say the n-1th term.
- 13211311123113112211
Difficulty:Easy
Category:Algorithms
Acceptance:34.21%
Contributor: LeetCode
Companies
facebook
Related Topics
string
Similar Questions
Encode and Decode Strings