C#刷遍Leetcode面試題系列連載(2): No.38 – 報數
- 2019 年 10 月 10 日
- 筆記
前言
前文傳送門:
C# 刷遍 Leetcode 面試題系列連載(1) – 入門與工具簡介
上篇文章中我們主要科普了刷 LeetCode 對大家的作用,今天咱們就正式進行 LeetCode 演算法題分析。很多人都知道電腦中有種思想叫 遞歸,相應地也出現了很多演算法。解決遞歸問題的要點有如下幾個:
-
找出遞歸的關係
比如,給個數列 *f(n),常見的遞歸關係是後面的項 *f(n+1)與前面幾項之間的關係,比如斐波那契數列的遞歸關係為: *f(n+1)* = f(n-1) + *f(n)*
-
進行遞歸調用
-
把握好遞歸出口
但實際情況下,遞歸演算法的複雜度比較難用數學公式來描述,自由度太大,我們常常需要將遞歸演算法優化成迭代(非遞歸)的演算法。
今天我們來分析一個遞歸描述的字元串問題,後面我們會給出相應的 非遞歸
演算法。
今天要給大家分析的面試題是 LeetCode 上第 38 號問題,
LeetCode – 38. 報數
https://leetcode-cn.com/problems/count-and-say/
題目描述
報數序列是一個整數序列,按照其中的整數的順序進行報數,得到下一個數。其前五項如下:
1. 1 2. 11 3. 21 4. 1211 5. 111221
1
被讀作 "one 1"
( "一個一"
) , 即 11
。11
被讀作 "two 1s"
( "兩個一"
), 即 21
。21
被讀作 "one 2"
, " one1"
( "一個二"
, "一個一"
) , 即 1211
。
給定一個正整數 n(1 ≤ n ≤ 30),輸出報數序列的第 n 項。
注意:整數順序將表示為一個字元串。
示例 1:
輸入: 1 輸出: "1"
示例 2:
輸入: 4 輸出: "1211"
-
貢獻者: LeetCode
-
題目難度: Easy
-
通過率:
52.67%
相關話題
相似題目
-
字元串的編碼與解碼
https://leetcode-cn.com/problems/encode-and-decode-strings/
難度: 中等
-
壓縮字元串
https://leetcode-cn.com/problems/string-compression/
難度:簡單
解題思路:
首先,這個題按題目描述來看並不是很容易理解。
一句話解釋清楚就是: 第 n+1
個字元串是第 n
個字元串的讀法,所以這個數列的每一項可列舉如下:
① 1
② 11
③ 21
④ 1211
⑤ 111221
⑥ 312211
…
而讀上一個字元串也是有要求的,就是統計連續出現的字元數量,一旦出現新字元就重新開始統計。
於是最後的結果為: count1 digit1 count2 digit2 … count n digit n (去掉其中的空格)
接下來,我們該考慮下程式碼該怎麼寫了。我們在文章開頭提到了下面會才有非遞歸的思路來做,具體可以這麼做:
- 首先我們有個基準,就是第一項 f(n) = 1
- 有了第1項,後面每一項只與它之前的項滿足明確的關係,於是想推算出第n項目,我們需要迭代 n-1 次
- 想辦法獲得每一段 count i digit i 拼接串,從左向右順序掃描之即可,遇到相同的數字計數器+1,遇到不同的置為1重新累加
- 拼接每一段 count i digit i 字元串,作為輸入進行下一輪迭代
已 AC
的程式碼為:
public class Solution { public string CountAndSay(int n) { if (n == 1) return "1"; string res = "1"; for (int i = 0; i < n - 1; i++) // 只需迭代n-1次是因為數列第一個數f(1)已知為 1 { StringBuilder buffer = new StringBuilder(); char currentChar = default(char); int currentCharCount = 0; currentChar = res[0]; foreach (var ch in res) // res用作pre(數列前一項) { if (ch == currentChar) currentCharCount++; else { buffer.Append(currentCharCount.ToString()).Append(currentChar); /* 一旦遇到不同的數字,就追加到拼接字元串 */ currentChar = ch; currentCharCount = 1; } } buffer.Append(currentCharCount.ToString()).Append(currentChar); /* 把最後一個數字及它的數量加上 */ res = buffer.ToString(); // 更新res,用作post(數列後一項) } return res; } }
運行結果:
執行用時 : 100ms
, 在所有 C# 提交中擊敗了 97.58%
的用戶
程式碼要點:
- 字元串比較常見的拼接方式是使用
+
,但頻繁拼接會降低運行速度,比較快的方式是使用StringBuilder
進行拼接,最後用個ToString()
函數即可 - 注意最後要將最後一個數字及它的數量加上
相應的,如需測試,本地可執行的程式碼為:
using System; using System.Text; namespace leetcode38 { public class Solution { public string CountAndSay(int n) { if (n == 1) return "1"; string res = "1"; for (int i = 0; i < n - 1; i++) // 只需迭代n-1次是因為數列第一個數f(1)已知為 1 { StringBuilder buffer = new StringBuilder(); char currentChar = default(char); int currentCharCount = 0; currentChar = res[0]; foreach (var ch in res) // res用作pre(數列前一項) { if (ch == currentChar) currentCharCount++; else { buffer.Append(currentCharCount.ToString()).Append(currentChar); /* 一旦遇到不同的數字,就追加到拼接字元串 */ currentChar = ch; currentCharCount = 1; } } buffer.Append(currentCharCount.ToString()).Append(currentChar); /* 把最後一個數字及它的數量加上 */ res = buffer.ToString(); // 更新res,用作post(數列後一項) } return res; } public static void Main() { var sol = new Solution(); Console.WriteLine(sol.CountAndSay(8)); } } }
相應程式碼已經上傳到github:
https://github.com/yanglr/Leetcode-CSharp/tree/master/leetcode38
參考資料:
https://www.cnblogs.com/TenosDoIt/p/3776356.html
作者簡介:Bravo Yeung,電腦碩士,知乎乾貨答主(獲73K 贊同, 34K 感謝, 210K 收藏)。曾在中國 Top3互聯網影片直播公司短暫工作過,後加入一家外企做軟體開發至今。
如需轉載,請加微信 iMath7 申請開白!
歡迎在留言區留下你的觀點,一起討論提高。如果今天的文章讓你有新的啟發,學習能力的提升上有新的認識,歡迎轉發分享給更多人。
歡迎各位讀者加入 .NET技術交流群,在公眾號後台回復「加群」或者「學習」即可。
文末彩蛋
微信後台回復「asp」,給你:一份全網最強的ASP.NET學習路線圖。
回復「cs」,給你:一整套 C# 和 WPF 學習資源!
回復「core」,給你:2019年dotConf大會上發布的.NET core 3.0學習影片!