首页 > 代码库 > 【Leetcode】【Easy】Count and Say
【Leetcode】【Easy】Count and Say
The count-and-say sequence is the sequence of integers beginning as follows: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 sequence.
Note: The sequence of integers will be represented as a string.
解题思路:
第一个string为1,从第二个string开始,对前一个string的每一位进行操作,一位一位遍历,前后位相同,则记录当前数字数量,遇到前后不同,则对新的string进行写入。循环n-1次。
注意:
1、C++中string类型的正确操作;
2、C++中string和char*的区别和转换;
3、数字和字符Ascii码的转换方法;
特别注意:
代码中使用 n(int) + ‘0‘ 来表示‘n‘,当且仅当n(int)<10时有效,因此如果sameDigCount超过10,也就是连续出现10个相同数字时,程序失败。不过可以轻松证明(证明略),连续出现的数字最多3个,也就是string串中最大的数字是3,不会超过4。因此代码是没有问题的。
1 class Solution { 2 public: 3 string countAndSay(int n) { 4 string currentStr = "1"; 5 6 if (n<=0) 7 return ""; 8 9 while (--n) {10 string nextStr = "";11 int sameDigCount = 1;12 int strlen = currentStr.length();13 char preDigital = currentStr[0];14 15 for (int i=1; i<strlen; ++i) {16 if (currentStr[i] == preDigital) {17 ++sameDigCount;18 } else {19 nextStr.push_back(sameDigCount+‘0‘);20 nextStr.push_back(preDigital);21 preDigital = currentStr[i];22 sameDigCount = 1;23 }24 }25 26 nextStr.push_back(sameDigCount+‘0‘);27 nextStr.push_back(preDigital);28 currentStr = nextStr;29 }30 31 return currentStr;32 }33 };
【Leetcode】【Easy】Count and Say
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。