前言
前文传送门:
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学习视频!