leetcode算法想不出来怎么办,leetcode怎么写代码

首页 > 机动车 > 作者:YD1662023-11-03 11:15:13

leetcode算法想不出来怎么办,leetcode怎么写代码(9)

leetcode算法想不出来怎么办,leetcode怎么写代码(10)

这里针对length=2的情况,还要再区分出中间不拆分这种情况,所以设计了doDecodeNums2()和doDecodeNums2v() 这2个函数。这道题目确实比较琐碎。

5. 初步解决

到这里,我们有了length=1和length=2这两种最简单情况的解法。我们通过手工计算、分析,对问题的理解又深入了一层。现在是时候研究这个问题的一般情况了。那么这个问题的一般情况,例如length=n,它的解法要怎么才能得到呢?

针对这个,我们可以思考一下,简单情况与一般情况之间的区别和联系在哪里?想明白它们之间的区别以及联系,那么我们就很容易找到一条从简单情况推广到一般情况的路径。

对于Decode Ways II这道题,我们知道它唯一的输入数据就是一个字符串string s。它的简单情况就是s.length() == 1或s.length() == 2;而一般情况就是 s.length() == n。区别仅仅在于输入字符串s的长度不同。那么它们之间的联系呢?

要弄明白简单情况与一般情况之间的联系,我们要把问题表示出来,建立一个模型,这样就容易看出它们之间的联系。例如,我们用一个函数f(n)来表示长度为n的数字串对应的字母串的个数。那么,s.length()==1或s.length()==2的情况就可以分别用f(1) 或f(2)来表示,一般情况就用f(n)来表示。那f(n)怎么关联到f(1)或f(2)呢,很显然,这要用递推或归纳法的思想。

我们根据题目的映射规则知道,一个字母对应的数字串,长度要么是1,要么是2。因此,f(n) 只有可能与 f(n-1) 和 f(n-2) 有关系。因此,我们最终知道问题f(n) 与f(n-1) 和 f(n-2)之间存在关联,f(n-1)和f(n-2)再继续往前递推,这样最终就到达f(1)和f(2),问题解决了。

f(n)与f(n-1)和f(n-2)之间究竟是什么关系呢?f(n)相当于是f(n-1)加上s[n]这个字符的对应个数,加上,f(n-2)加s[n-1]s[n]这个长度为2的子串的个数。可以用一个抽象公式表示:

f(n) = s[n] * f(n – 1) s[n-1, n] * f(n – 2)

6. 给出直观解法

分析出以上结论,我们已经可以写出第一个直观的解法了。可以按照前面的递推公式,结合在最简单情况中分析得出的结果,直接用递归设计出一个算法。

leetcode算法想不出来怎么办,leetcode怎么写代码(11)

第一个版本的算法往往都对应着暴力破解,、表扫描、线性搜索之类的关键词。这个算法虽然性能不符合要求,可能是O(n^2)的,但是起码它计算出的结果是正确的,至少是把问题给解出来了的,没有那么快或内存空间不够用而已。

我们把上面的算法提交,发现它其实是可以被LeetCode接受的。提交之后,我们得到了Accepted的反馈。我们的简易递归算法的运行时间竟然是0 ms,但是我们写出来的的确是一个最慢的算法,这可能是因为LeetCode上面的test case的输入比较小,无法把我们的问题暴露出来导致的。按照道理来讲,这个算法不符合要求,需要进一步优化满足性能要求。

leetcode算法想不出来怎么办,leetcode怎么写代码(12)

上一页1234下一页

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.