LeetCode：Count and Say（数数并说）

2023-12-25 06:58

本文主要是介绍LeetCode：Count and Say（数数并说），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     1112211
2
3
4
5

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 term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"1
2

Example 2:

Input: 4
Output: "1211"1
2

思路

难点在于看懂题意。count-and-say sequence的后一组数实际就是数前一列数中连续数字的个数。比如第四组1211，第一个数为1，后面没有连续出现1，因此对应第五组中会出现11（一个1）；第二个数为2，没有连续2，对应为12；第三和第四个数为1，连续两个1，对应为21。因此第五组数为11 12 21。

要生成这样的数组，由于输入只有组号n，考虑使用递归的方式，输入前一组数统计连续数，得到下一组数。

#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;class Solution {
/*
//递归
public:string countAndSay(int n) {return countAndSay("1", 1, n);}
private:string countAndSay(string s, int n, int depth) {if (depth == n) return s;string ans;int cnt = 1;for (int i = 0; i < s.length(); i++){if (s[i] == s[i + 1]){cnt++;}else{ans += cnt + '0';ans += s[i];cnt = 1;}}return countAndSay(ans, n + 1, depth);}*/
//非递归
public:string countAndSay(int n) {string tmp = "1";string ans;int cnt = 1;for (int i = 2; i <= n; i++){for (int j = 0; j < tmp.length(); j++){if (tmp[j] == tmp[j + 1]){cnt++;}else {ans += cnt + '0';ans += tmp[j];cnt = 1;}}tmp = ans;ans = "";}return tmp;}
};int main()
{Solution s;int n;cin >> n;cout << s.countAndSay(n);
}

这篇关于LeetCode：Count and Say（数数并说）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！