首页 > 代码库 > Leetcode 模拟 Count and Say
Leetcode 模拟 Count and Say
Count and Say
Total Accepted: 14508 Total Submissions: 53213My SubmissionsThe 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.
题意:有一个整数序列 1,11,21,1211,111221,...
它是这样产生的:
1读作 ‘one 1’,即 11
11读作 ‘two 1s‘,即 21
21读作 ‘one 2 one 1‘,即1211
...
给定整数 n,返回该序列的第 n 个数
思路:模拟
复杂度:时间O(n),空间O(1)
//一般写法 string countAndSay(int n){ string last = "1"; while(--n){ int count = 1; char c = last[0]; string cur; for(int i = 1; i <= last.size(); ++i){ if(i < last.size() && last[i] == c) count++; else{ cur += count + '0'; cur += c; if(i < last.size()){ count = 1; c = last[i]; } } } last = cur; } return last; } //使用stl string countAndSay(int n){ string past = "1"; while(--n){ string cur; for(auto iter = past.begin(); iter != past.end();){ auto iter2 = find_if(iter, past.end(), bind1st(not_equal_to<char>(), *iter)); cur += distance(iter, iter2) + '0'; cur += *iter; iter = iter2; } past = cur; } return past; }
Leetcode 模拟 Count and Say
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。