golang刷leetcode技巧的解碼方法

golang刷leetcode技巧的解碼方法，針對(duì)這個(gè)問(wèn)題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問(wèn)題的小伙伴找到更簡(jiǎn)單易行的方法。

永吉網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)建站！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、APP開(kāi)發(fā)、響應(yīng)式網(wǎng)站等網(wǎng)站項(xiàng)目制作，到程序開(kāi)發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)建站于2013年成立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專(zhuān)注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)建站。

一條包含字母 A-Z 的消息通過(guò)以下方式進(jìn)行了編碼：

'A' -> 1

'B' -> 2

...

'Z' -> 26

給定一個(gè)只包含數(shù)字的非空字符串，請(qǐng)計(jì)算解碼方法的總數(shù)。

示例 1:

輸入: "12"

輸出: 2

解釋: 它可以解碼為 "AB"（1 2）或者 "L"（12）。

示例 2:

輸入: "226"

輸出: 3

解釋: 它可以解碼為 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6)

解題思路：

1，動(dòng)態(tài)規(guī)劃解決

假設(shè)s[0:i-1] 有dp[i]種解碼方案

2，狀態(tài)轉(zhuǎn)移方程

A，如果s[i]='0' 有兩種情況

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

這個(gè)時(shí)候s[i-1] s[i]必須一起解碼才行

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

(2) 其他情況

這時(shí)候解碼失敗

dp［i+1]=0

B，如果s[i-1]='1'，s[i]這一位單獨(dú)解碼或者和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，其他情況，只能單獨(dú)解碼

dp[i+1]=dp[i]

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

如果s[0]=='0'直接解碼失敗，返回0

dp［1］＝1

為了便于計(jì)算，我們?cè)黾恿薲p［0］，且初始化值是1

測(cè)試用例：

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

代碼實(shí)現(xiàn)：

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<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)]}

代碼優(yōu)化：

由于我們只用到了dp[i]和dp[i-1]倆變量，其他存儲(chǔ)是非必須的，所以，可以?xún)?yōu)化

func numDecodings(s string) int {       if s[0]=='0'{       return 0    }    prepre:=1    pre:=1    cur:=1    
   for 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=pre       pre=cur       fmt.Println(cur,pre,prepre)   }   return cur}

關(guān)于golang刷leetcode技巧的解碼方法問(wèn)題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒(méi)有解開(kāi)，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識(shí)。

分享題目：golang刷leetcode技巧的解碼方法
網(wǎng)站鏈接：http://muchs.cn/article12/jehgdc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、網(wǎng)站維護(hù)、定制網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)、App開(kāi)發(fā)、云服務(wù)器

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容