leetcode-38.报数
题意
报数序列是一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:
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(1 ≤ n ≤ 30),输出报数序列的第 n 项。
注意:整数顺序将表示为一个字符串。
示例 1:
输入: 1 输出: "1"示例 2:
输入: 4 输出: "1211"
这题......有点不好理解。
解释下题意,可能有同学看不懂。
题意true
下一个字符串由上一个字符串来决定 。
比如
上一个是1,下一个就是1个1,即 "11";
上一个是21,下一个就是 1个2,1个1,即"1211";
上一个是111221,下一个就是3个1,2个2,1个1,即"312211"。
算法
- 定义string raw, ans(raw为最终输出结果, ans为存储中间结果的临时字符串)
- 根据输入整数确定更新次数
- 每次遍历原始字符串(初始为"1",每次循环结束后更新)
- 对重复出现的字符予以计数,计数完毕后将出现的次数和字符添加在ans末尾
- 将ans赋给raw, ans置空,继续。
- 返回raw
code
1 class Solution { 2 public: 3 string countAndSay(int n) { 4 if(n == 1) 5 return "1"; 6 string raw = "1"; 7 string ans = ""; 8 n--; 9 while(n--) 10 { 11 for(int i=0; i<raw.length();) 12 { 13 int begin = i; 14 while(raw[i] == raw[begin]) 15 { 16 i++; 17 } 18 char c = i-begin + '0'; 19 ans = ans + c + raw[begin]; 20 } 21 raw = ans; 22 ans = ""; 23 } 24 25 return raw; 26 } 27 };
附上1:10 的测试样例
The following are the terms from n=1 to n=10 of the count-and-say sequence:
1. 1 2. 11 3. 21 4. 1211 5. 111221 6. 312211 7. 13112221 8. 1113213211 9. 31131211131221 10. 13211311123113112211