Last Updated on 2021-02-21 by Clay
題目
The count-and-say sequence is a sequence of digit strings defined by the recursive formula:
- countAndSay(1) = "1"
- countAndSay(n) is the way you would "say" the digit string from countAndSay(n-1), which is then converted into a different digit string.
To determine how you "say" a digit string, split it into the minimal number of groups so that each group is a contiguous section all of the same character. Then for each group, say the number of characters, then say the character. To convert the saying into a digit string, replace the counts with a number and concatenate every saying.
Given a positive integer n, return the nth term of the count-and-say sequence.
Example:
Input: n = 1
Output: "1"
Explanation: This is the base case.
Input: n = 4
Output: "1211"
Explanation:
countAndSay(1) = "1"
countAndSay(2) = say "1" = one 1 = "11"
countAndSay(3) = say "11" = two 1's = "21"
countAndSay(4) = say "21" = one 2 + one 1 = "12" + "11" = "1211"
這個題目我反覆看了好幾遍,最後才總算弄明白題目的意思:題目給定要『展開的次數 n』,在 n = 1 時,最基本的案例為 “1“,這是一切的基礎。
n = 2 時,因為 “1” 只有 1 個,所以為我們稱其為 one 1,也就是 “11“。
n = 3 時,因為 “11” 有 2 個 1,所以稱其為 two 1,也就是 “21“。
n = 4 時,因為 “2” 以及 “1” 都各自只有 1 個,所以稱其為 one 2 one 1,也就是 “1211“。
以此類推,一直展開我們的字串。
解題思路
我的想法非常單純,使用陣列紀錄重複的字元、以及字元重複的次數,然後將其儲存成新的字串。接下來,就是看題目要我們迭代幾次,我們就展開多少次字串。
C++ 程式碼
class Solution { public: string countAndSay(int n) { // Init int times = 1; string s = "1"; // Unfold while (times < n) { ++times; char c = '0'; vector<char> vc; vector<int> vcn; // Count the numbers of repeat characters for (int i=0; i<s.size(); ++i) { if (s[i] != c) { c = s[i]; vc.push_back(s[i]); vcn.push_back(1); } else { ++vcn[vc.size()-1]; } } // Clear the current string s.clear(); // Create the new string for (int i=0; i<vc.size(); ++i) { s += to_string(vcn[i]); s += vc[i]; } } return s; } };
Python 程式碼
class Solution: def countAndSay(self, n: int) -> str: # Init times = 1 s = "1" # Unfold while times < n: times += 1 c = "0" vc = [] vcn = [] # Count the numbers of repeat characters for w in s: if w != c: c = w vc.append(w) vcn.append(1) else: vcn[-1] += 1 # Clear the current string s = "" # Create the new string for i in range(len(vc)): s += str(vcn[i]) + vc[i] return s;