宜宾网站建设公司

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技巧的解码方法
本文路径：http://hbruida.cn/article/jehgdc.html

其他资讯