天津市中小企业局网站,企业推广策略,湖南网络工程职业学院,WordPress HTML标签验证前言前文传送门#xff1a;上篇文章中我们主要科普了刷 LeetCode 对大家的作用#xff0c;今天咱们就正式进行 LeetCode 算法题分析。很多人都知道计算机中有种思想叫 递归#xff0c;相应地也出现了很多算法。解决递归问题的要点有如下几个:找出递归的关系比如#xff0c;… 前言前文传送门上篇文章中我们主要科普了刷 LeetCode 对大家的作用今天咱们就正式进行 LeetCode 算法题分析。很多人都知道计算机中有种思想叫 递归相应地也出现了很多算法。解决递归问题的要点有如下几个:找出递归的关系比如给个数列 f(n)常见的递归关系是后面的项 f(n1)与前面几项之间的关系比如斐波那契数列的递归关系为: f(n1) 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. 1112211 被读作 one 1 ( 一个一) , 即 11。11 被读作 two 1s ( 两个一, 即 21。21 被读作 one 2, one1 一个二 , 一个一) , 即 1211。给定一个正整数 n1 ≤ n ≤ 30输出报数序列的第 n 项。注意整数顺序将表示为一个字符串。示例 1:输入: 1
输出: 1示例 2:输入: 4
输出: 1211贡献者: LeetCode题目难度: Easy通过率: 52.67%相关话题字符串https://leetcode.com/tag/string相似题目字符串的编码与解码https://leetcode-cn.com/problems/encode-and-decode-strings/难度: 中等压缩字符串https://leetcode-cn.com/problems/string-compression/ 难度:简单解题思路:首先这个题按题目描述来看并不是很容易理解。一句话解释清楚就是: 第 n1个字符串是第 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) { StringBuilder buffer new StringBuilder(); char currentChar default(char); int currentCharCount 0; currentChar res[0]; foreach (var ch in res) { if (ch currentChar) currentCharCount; else { buffer.Append(currentCharCount.ToString()).Append(currentChar); currentChar ch; currentCharCount 1; } } buffer.Append(currentCharCount.ToString()).Append(currentChar); res buffer.ToString(); } 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.htmlEnd你点的每一个在看我都当成了喜欢
