溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
golang刷leetcode技巧的解碼方法，針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。
一條包含字母 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]=1if s[0]=='0'{return 0}else{dp[1]=1}for i:=1;i<len(s);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:=1pre:=1cur:=1for i:=1;i<len(s);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=prepre=curfmt.Println(cur,pre,prepre)}return cur}
關于golang刷leetcode技巧的解碼方法問題的解答就分享到這里了，希望以上內容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業資訊頻道了解更多相關知識。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
