golang刷leetcode技巧的解码方法-成都快上网建站

快上网建站品牌

13518219792

golang刷leetcode技巧的解码方法

golang刷leetcode技巧的解码方法，针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

永吉网站制作公司哪家好，找创新互联建站！从网页设计、网站建设、微信开发、APP开发、响应式网站等网站项目制作，到程序开发，运营维护。创新互联建站于2013年成立到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选创新互联建站。

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1

'B' -> 2

...

'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"

输出: 2

解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

输入: "226"

输出: 3

解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6)

解题思路：

1，动态规划解决

假设s[0:i-1] 有dp[i]种解码方案

2，状态转移方程

A，如果s[i]='0' 有两种情况

（1）s[i-1]='1' || '2'

     这个时候s[i-1] s[i]必须一起解码才行

    故 dp[i+1]=dp[i-1]

  (2) 其他情况

  这时候解码失败

dp［i+1]=0

B，如果s[i-1]='1'，s[i]这一位单独解码或者 和s[i-1]一起解码都可以

dp[i+1]=dp[i]+dp[i-1]

C,如果s[i-1]='2',s[i]>'0' && s[i]<='6' ,同上

dp[i+1]=dp[i]+dp[i-1]

D， 其他情况，只能单独解码

dp[i+1]=dp[i]

3,初始化条件，由于dp[i+1]用到了dp[i]和dp[i-1],所以递增迭代

如果s[0]=='0'直接解码失败，返回0

dp［1］＝1

为了便于计算，我们增加了dp［0］，且初始化值是1

测试用例：

"50926""10""100""110""12""123""0""226""1""123456"

代码实现：

func numDecodings(s string) int {    dp:=make([]int,len(s)+1)    dp[0]=1    if s[0]=='0'{       return 0    }else{       dp[1]=1    }
    
   for i:=1;i       if s[i]=='0'{           if s[i-1]=='1' ||  s[i-1]=='2'{                   dp[i+1]=dp[i-1]           }       }else{           if s[i-1]=='1'{                  dp[i+1]=dp[i]+dp[i-1]           }else if s[i-1]=='2' && s[i]<='6'{                   dp[i+1]=dp[i]+dp[i-1]           }else{               dp[i+1]=dp[i]           }       }   }   return dp[len(s)]}

代码优化：

由于我们只用到了dp[i]和dp[i-1]俩变量，其他存储是非必须的，所以，可以优化

func numDecodings(s string) int {       if s[0]=='0'{       return 0    }    prepre:=1    pre:=1    cur:=1    
   for i:=1;i       if s[i]=='0'{           if s[i-1]=='1' ||  s[i-1]=='2'{                 cur=prepre           }else{               return 0           }       }else{           if s[i-1]=='1' || ( s[i-1]=='2' && s[i]<='6'){               cur=pre+prepre           }else{               cur=pre           }       }       prepre=pre       pre=cur       fmt.Println(cur,pre,prepre)   }   return cur}

关于golang刷leetcode技巧的解码方法问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注创新互联行业资讯频道了解更多相关知识。


本文名称：golang刷leetcode技巧的解码方法
链接URL：http://kswjz.com/article/jehgdc.html
扫二维码与项目经理沟通

我们在微信上24小时期待你的声音

解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流

其他资讯

行业动态

企业网站建设的重要性！

现在虽然是移动互联网时代，但企业网站依然重要，包含PC站点，移动站。可以说企业网站关系企业的未来发展和前途，尤其对中小企业更是如此，一些中小企业老板，对自己的名片很在乎，因为这是个门面。...

服务项目

联系吧 在百度地图上找到我们

电话：13518219792

如遇占线或暂未接听请拨：136xxx98888

业务咨询 技术咨询 售后服务
网站设计
重庆网站设计
成都网站设计
温江网站设计
企业网站设计
网站制作
达州网站制作
手机网站制作
成都网站制作
成都商城网站制作
联系我们
电话：13518219792
邮箱：631063699@qq.com
地址：成都青羊区锦天国际1002号
网址：www.kswjz.com
网站建设
网站建设推广
成都企业网站建设
旅游网站建设方案
成都定制网站建设

微信二维码

Copyright © 2002-2023 www.kswjz.com 快上网建站品牌 QQ：244261566 版权所有 备案号：蜀ICP备19037934号