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)*

  • 進行遞歸調用

  • 把握好遞歸出口

但實際情況下,遞歸演算法的複雜度比較難用數學公式來描述,自由度太大,我們常常需要將遞歸演算法優化成迭代(非遞歸)的演算法。

今天我們來分析一個遞歸描述的字元串問題,後面我們會給出相應的 非遞歸 演算法。

img

今天要給大家分析的面試題是 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" ( "一個一") , 即 1111 被讀作 "two 1s" ( "兩個一"), 即 2121 被讀作 "one 2", " one1""一個二" , "一個一") , 即 1211

給定一個正整數 n(1 ≤ n ≤ 30),輸出報數序列的第 n 項。

注意:整數順序將表示為一個字元串。

示例 1:

輸入: 1  輸出: "1"

示例 2:

輸入: 4  輸出: "1211"
  • 貢獻者: LeetCode

  • 題目難度: Easy

  • 通過率: 52.67%

相關話題

相似題目

解題思路:

首先,這個題按題目描述來看並不是很容易理解。

一句話解釋清楚就是: 第 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;      }  }

img

運行結果:

執行用時 : 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技術交流群,在公眾號後台回復「加群」或者「學習」即可。

dotNET匠人 公眾號名片

文末彩蛋

微信後台回復「asp」,給你:一份全網最強的ASP.NET學習路線圖。

回復「cs」,給你:一整套 C# 和 WPF 學習資源!

回復「core」,給你:2019年dotConf大會上發布的.NET core 3.0學習影片!