天天演算法 | Easy | 11. 計數和描述：Count and Say

每天來一道，面試不卡殼，今天是天天演算法陪你成長的第11天

本題可在LeetCode上OJ，鏈接： Count and Say

題目描述：

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

1. 1n2. 11n3. 21n4. 1211n5. 111221n

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: 1nOutput: "1"n

Example 2:

Input: 4nOutput: "1211"n

題目翻譯

「計數與描述」序列如下所示：

1. 1n2. 11n3. 21n4. 1211n5. 111221n

1被讀取為"1個1"或11。 11被讀取為"2個1"或21。 21被讀取"1個2，然後1個1"或1211。 給定一個整數n，生成count-and-say序列的第n個項。

注意：整數序列中的每個項將被表示為一個字元串。

示例1：

輸入： 1n輸出： 「1」n

示例2：

輸入： 4n輸出： 「1211」n

解題方案：

標籤： String

思路：

• 使用遞歸實現，遞歸表達式如下
• 當 n == 1 時，返回"1"
• 當 n != 1 時，返回n-1時的結果，返回後對其進行描述解析

• 描述解析過程如下
• 遍歷字元串
• 當前字元與前一個字元相同時，長度+1
• 字元不同時，將該描述記錄下來
• 返回解析好的字元串

代碼：

class Solution {n public String countAndSay(int n) {n if(n == 1)n return "1";n else{n String str = countAndSay(n-1);n String res="";n int len = 1;n int i = 1;n while(i<str.length()){n if(str.charAt(i) == str.charAt(i-1)){n len++;n }else{n res+=String.valueOf(len) + String.valueOf(str.charAt(i-1));n len = 1;n }n i++;n }n res+=String.valueOf(len) + String.valueOf(str.charAt(i-1));n return res;n }n }n}n

參考資料：

algorithm.books.mafengshe.com...

歡迎加入碼蜂社演算法交流群：天天一道演算法題

掃描下方二維碼或搜素「碼蜂社」公眾號，不怕錯過好文章：