LeetCodeアルゴリズム——外観数列(ループプッシュ)

タイトル:正の整数n(1≦n≦30)を与え、外観数列のn番目の項目を出力する.
注:整数シーケンスの各項目は文字列として表示されます.
「外観数列」は整数のシーケンスで、数値1からシーケンスの各項目が前の項目について説明されます.最初の5つは次のとおりです.

1

11

21

1211

111221

1つ目は数字1です
前項を記述し、この数は1である「1つの1」であり、11と記す.
前の項を説明して、この数は11つまり“2つの1”で、21と書きます
前項について説明するが、この数は21である「1つ2つ1つ」であり、1211と記す.
前項について説明するが、この数は1211、すなわち「1個1個2個1」であり、111221と記す
例1:
入力:1出力:1説明:これは基本的なサンプルです.例2:
入力:4出力:“1211”解釈:n=3の時、シーケンスは“21”で、その中で私達は“2”と“1”の2組があって、“2”は“12”と読むことができて、つまり出現頻度=1で値=2;「1」のように「11」と読むことができます.だから答えは「12」と「11」を組み合わせて、つまり「1211」です.
コードは次のとおりです.

#include 
#include 
#include 

using namespace std;

class Solution {
public:

	vector<string> vec;

	string countAndSay(int n) {
		vec.push_back("1");
		vec.push_back("11");
		vec.push_back("21");
		vec.push_back("1211");
		vec.push_back("111221");

		if (n <= 5) return vec[n - 1];

		for (size_t i = 5; i <= n - 1; i++)
		{
			vec.push_back(RetCurrNumber(i));
		}

		return vec[n - 1];
	}

private:
	string RetCurrNumber(int n) {
		string tmp = vec[n - 1];
		string retStr = "";
		int tmpCount = 1;
		int i;

		//  33366678
		// 111221
		for (i = 1; i < tmp.size(); i++)
		{
			if (tmp[i] == tmp[i - 1]) ++tmpCount;
			else {
				retStr += (char)(tmpCount + 48);
				retStr += tmp[i - 1];
				tmpCount = 1;
			}
		}

		retStr += (char)(tmpCount + 48);
		retStr += tmp[i - 1];

		return retStr;
	}
};

int main() {

	cout << (new Solution())->countAndSay(7) << endl;

	return 0;
}