LeetCode - 解题笔记 - 91 - Decode Ways
2021/9/3 23:37:30
本文主要是介绍LeetCode - 解题笔记 - 91 - Decode Ways,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Solution 1
这个题一看就让我想到了很久以前做的一个划分区间的问题,最后要的也不是划分结果而是划分方式,这个也是这样的,就是两种角色:选当前一个还是选当前一个加前面一个。
状态变量 ans[i]
:前i个字符能够实现的划分方案数
决策:
- 仅选择当前一位,要求数字在1到9之间,所有
ans[i-1]
的方案都能采用,否则为0 - 选择当前一位和前面一位,要求组合数字在10到26之间,所有
ans[i-2]
的方案都能采用,否则为0 ans[i]
即为上述两种决策结果的加和
此外还进行了一个优化,由于每一次计算只跟前两个值有关,将整个ans数组省略,用三个状态变量维护。
- 时间复杂度: O ( N ) O(N) O(N),其中 N N N为输入字符串的长度,线性遍历
- 空间复杂度: O ( 1 ) O(1) O(1),用状态变量维护
class Solution { public: int numDecodings(string s) { int now = 0, pre1 = 1, pre2 = 0; for (int i = 0; i < s.size(); ++i) { // cout << now << " " << pre1 << " " << pre2 << endl; now = 0; if (s[i] != '0') { now += pre1; } if (i > 0 && ((s[i - 1] - 48) * 10 + s[i] - 48 >= 10) && ((s[i - 1] - 48) * 10 + s[i] - 48 <= 26)) { // cout << s[i - 1] << " " << s[i] << endl; now += pre2; } pre2 = pre1; pre1 = now; } return now; } };
Solution 2
Solution 1的Python实现
class Solution: def numDecodings(self, s: str) -> int: pre1, pre2 = 1, 0 for i in range(len(s)): now = 0 if s[i] != '0': now += pre1 if i > 0 and 10 <= int(s[i - 1 : i + 1]) <= 26: now += pre2 pre2, pre1 = pre1, now return now
这篇关于LeetCode - 解题笔记 - 91 - Decode Ways的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享