Leetcode-Count and Say

Nov 23, 2013

题目描述

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

题意

n=1时输出字符串1；n=2时，数上次字符串中的数值个数，因为上次字符串有1个1，所以输出11；n=3时，由于上次字符是11，有2个1，所以输出21；n=4时，由于上次字符串是21，有1个2和1个1，所以输出1211。依次类推.

思路

1. Base case: n = 0 print “1”
2. for n = 1, look at previous string and write number of times a digit is seen and the digit itself. In this case, digit 1 is seen 1 time in a row… so print “1 1”
3. for n = 2, digit 1 is seen two times in a row, so print “2 1”
4. for n = 3, digit 2 is seen 1 time and then digit 1 is seen 1 so print “1 2 1 1”
5. for n = 4 you will print “1 1 1 2 2 1”
6. Consider the numbers as integers for simplicity. e.g. if previous string is “10 1” then the next will be “1 10 1 1” and the next one will be “1 1 1 10 2 1”

AC代码

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;

string countAndSay(int n)
{
    	string s = "1";
    	string next;
    	if(n == 1)
    		return s;
    
    	for(int i = 1; i <n; i++)
    	{
    		int j = 0;
    		while(j < s.size())
    		{
    			int k = j + 1;
    			while(k < s.size() && s[k] == s[j])
    				k++;
    			next += (k - j + '0');
    			next += s[j];
    			j = k;
    		}
    		s = next;
    		next = "";
    	}
    	return s;
}

int main()
{
    	int n;
    
    #ifndef cout
    	freopen("in3.in", "r", stdin);
    	freopen("std3.out","w",stdout);
    #endif
    
    	while(cin>>n)
    		cout<<countAndSay(n)<<endl;
    
    #ifndef cout
    	fclose(stdin);
    	fclose(stdout);
    #endif
    
    	return 0;
}