当前位置:网站首页>算法---解码方法(Kotlin)
算法---解码方法(Kotlin)
2022-08-01 20:22:00 【小米科技Android 研发曹新雨】
题目
一条包含字母 A-Z 的消息通过以下映射进行了 编码 :
‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“11106” 可以映射为:
“AAJF” ,将消息分组为 (1 1 10 6)
“KJF” ,将消息分组为 (11 10 6)
注意,消息不能分组为 (1 11 06) ,因为 “06” 不能映射为 “F” ,这是由于 “6” 和 “06” 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1:
输入:s = “12”
输出:2
解释:它可以解码为 “AB”(1 2)或者 “L”(12)。
示例 2:
输入:s = “226”
输出:3
解释:它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。
示例 3:
输入:s = “0”
输出:0
解释:没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 ‘J’ -> “10” 和 ‘T’-> “20” 。
由于没有字符,因此没有有效的方法对此进行解码,因为所有数字都需要映射。
提示:
1 <= s.length <= 100
s 只包含数字,并且可能包含前导零。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/decode-ways
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解决思路
解决方法
fun numDecodings(s: String): Int {
val chars = s.toCharArray()
val size = chars.size
val dp = Array(size + 1) {
0 }
dp[0] = 1
for (i in 1..size) {
val j = chars[i - 1] - '0'
if (j != 0) {
dp[i] += dp[i - 1]
}
if (i - 2 >= 0) {
val k = chars[i - 2] - '0'
if (k != 0) {
val num = k * 10 + j
dp[i] += if (num <= 26) dp[i - 2] else 0
}
}
}
return dp[size]
}
fun numDecodings2(s: String): Int {
val chars = " $s".toCharArray()
val size = chars.size
val dp = Array(size) {
0 }
dp[0] = 1
for (i in 1 until size) {
//j 表示当前位 k表示前一位
val j = chars[i] - '0'
val k = chars[i - 1] - '0'
if (j != 0) {
dp[i] += dp[i - 1]
}
val num = k * 10 + j
dp[i] += if (num in 10..26) dp[i - 2] else 0
}
return dp[size - 1]
}
总结
1.这个题也是动态规划的经典题
当前的结果和上一个结果有很大的关系
要么当前解码单独的一个 要么和前一个一块
相对来说 会比较复杂
但是思路足够清晰
知道自己想要什么
还是可以做出来的
2.第二种方法是添加了一个空的字符串 用于解决-2的问题
代码会相对优化一点 但是原理不变
边栏推荐
- 18. Distributed configuration center nacos
- Different operating with different locks, rounding
- Custom command to get focus
- 【Untitled】
- Get started quickly with MongoDB
- [Personal work] Wireless network image transmission module
- 57: Chapter 5: Develop admin management services: 10: Develop [get files from MongoDB's GridFS, interface]; (from GridFS, get the SOP of files) (Do not use MongoDB's service, you can exclude its autom
- Batch get protein .pdb files based on Uniprot ID/PDB ID
- myid file is missing
- 网络不通?服务丢包?这篇 TCP 连接状态详解及故障排查,收好了~
猜你喜欢
[Energy Conservation Institute] Comparative analysis of smart small busbar and column head cabinet solutions in data room
PROE/Croe如何编辑已完成的草图,让其再次进入草绘状态
【kali-信息收集】(1.3)探测网络范围:DMitry(域名查询工具)、Scapy(跟踪路由工具)
Remove 360's detection and modification of the default browser
[Personal work] Wireless network image transmission module
18、分布式配置中心nacos
第56章 业务逻辑之物流/配送实体定义
【节能学院】数据机房中智能小母线与列头柜方案的对比分析
58:第五章:开发admin管理服务:11:开发【管理员人脸登录,接口】;(未实测)(使用了阿里AI人脸识别)(演示了,使用RestTemplate实现接口调用接口;)
18. Distributed configuration center nacos
随机推荐
Greenplum Database Source Code Analysis - Analysis of Standby Master Operation Tools
密码学的基础:X.690和对应的BER CER DER编码
mysql自增ID跳跃增长解决方案
Intranet penetration lanproxy deployment
myid file is missing
WhatsApp群发实战分享——WhatsApp Business API账号
【个人作品】记之-串口日志记录工具
57:第五章:开发admin管理服务:10:开发【从MongoDB的GridFS中,获取文件,接口】;(从GridFS中,获取文件的SOP)(不使用MongoDB的服务,可以排除其自动加载类)
给定中序遍历和另外一种遍历方法确定一棵二叉树
【kali-信息收集】(1.5)系统指纹识别:Nmap、p0f
Redis does web page UV statistics
【节能学院】安科瑞餐饮油烟监测云平台助力大气污染攻坚战
解除360对默认浏览器的检测与修改
9月备考PMP,应该从哪里备考?
【无标题】
瀚高数据导入
启明云端分享|盘点ESP8684开发板有哪些功能
18. Distributed configuration center nacos
【多任务学习】Modeling Task Relationships in Multi-task Learning with Multi-gate Mixture-of-Experts KDD18
内网穿透 lanproxy部署