日韩一区二区黄片视频在线看,黄色在线免费观看,国产一级淫乱视频,人人草人,黄色小视频在线免费看,亚洲狼人,少妇97,免费视频一二区

算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問題叫做?解碼方法，我們先來看題面：

https://leetcode-cn.com/problems/decode-ways/

A message containing letters from A-Z is being encoded to numbers using the following mapping:

題意

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

'A' -> 1

'B' -> 2

...

'Z' -> 26

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

題目數(shù)據(jù)保證答案肯定是一個(gè) 32 位的整數(shù)。

樣例

示例 1：

輸入："12"
輸出：2
解釋：它可以解碼為 "AB"（1?2）或者 "L"（12）。

示例 2：

輸入："226"
輸出：3
解釋：它可以解碼為 "BZ"?(2?26), "VF"?(22?6), 或者 "BBF"?(2?2?6) 。

示例 3：

輸入：s = "0"
輸出：0

示例 4：

輸入：s = "1"
輸出：1

示例 5：

輸入：s = "2"
輸出：1

解題

https://www.cnblogs.com/techflow/p/13489811.html

題解

我們觀察一下樣例，比如12可以理解成12這個(gè)字符也就是L，也可以理解成1和2兩個(gè)字符拼接而成。同樣226有三種還原的方法，分別是(2, 2, 6), (22, 6), (2, 26)。我們只需要返回所有可能的數(shù)量即可。

這道題看起來沒有頭緒，但是當(dāng)我們仔細(xì)分析一下其中的情況，其實(shí)并不復(fù)雜。首先對(duì)于字符串當(dāng)中的每一位來說，只有0到9這10種可能性。我們逐一來考慮，首先如果是0，由于我們的A映射的是1，所以0只能和前面一個(gè)數(shù)字湊成10或者是20，如果前一位不是1或者是2，那么說明這個(gè)字符串是非法的，也就是沒有辦法還原。

如果某一位是1-9當(dāng)中的數(shù)字，它都可以單獨(dú)成為一個(gè)字母。我們?cè)倏紤]它的前一位，它的前一位只有1和2這兩種可能可以構(gòu)成新的組成。這里要注意，如果它的前一位是2的話，那么當(dāng)前位必須要小于6，因?yàn)橛⑽淖帜缸疃嘀坏?6。所以這里也需要進(jìn)行一個(gè)特殊判斷，除此之外，就沒有其他情況了。

這些可能性都列舉出來之后，剩下的就簡(jiǎn)單了，比如我們可以用深搜來搜索所有解的可能性。由于我們已經(jīng)列舉出了所有的情況，所以這段代碼并不難寫，但是想要一次就寫對(duì)也不容易。

class?Solution:
????def?numDecodings(self, s: str)?-> int:
????????n = len(s)
????????ret = 0
????????
????????def?dfs(i):
????????????nonlocal?ret
????????????
????????????if?i >= n:
????????????????ret += 1
????????????????return?
????????????
????????????# 當(dāng)前位如果是0則說明無解，return
????????????# 當(dāng)前位為0說明上一位不是1或者2
????????????if?s[i] == '0':
????????????????return
????????????
????????????# 遞歸單個(gè)的情況
????????????dfs(i+1)
????????????
????????????# 判斷下一位能否構(gòu)成組合
????????????if?i+1?< n and?(s[i] == '1'?or?(s[i] == '2'?and?ord(s[i+1]) <= ord('6'))):
????????????????dfs(i+2) 
????????????????
????????dfs(0)
????????return?ret

搜索算法固然可以解，但是一定會(huì)超時(shí)。這一點(diǎn)也不難想明白，當(dāng)我們的字符串長(zhǎng)度大了之后，帶來的解的可能性是非常多的。最極端的情況下，比如每一位都是1，它都可以單獨(dú)作為一個(gè)字符也可以和下一位組合成11構(gòu)成新的字符。這樣的情況總數(shù)是以斐波那契數(shù)列遞增的，n不需要多大帶來的解的數(shù)量就是天文數(shù)字了。

使用搜索算法我們需要窮舉每一種情況，哪怕尋找每一個(gè)解只需要的復(fù)雜度也是無法抗住的。

所以我們必須要想一些更優(yōu)的方法，這個(gè)方法也不難想，就是動(dòng)態(tài)規(guī)劃。

我們分析一下會(huì)發(fā)現(xiàn)每一位數(shù)字能夠組成的解只和它的前一位有關(guān)，和后面的都沒有關(guān)系。這樣的話顯然是滿足動(dòng)態(tài)規(guī)劃的無后效性的。也就是說前面的字符組合的情況不會(huì)影響后面的解。

我們假設(shè)dp[i]存儲(chǔ)的是前i個(gè)數(shù)字構(gòu)成的解的數(shù)量，對(duì)于s[i]來說有10種情況，分別是0到9。如果s[i]為0，那么s[i-1]如果是1或者是2的話，只有一種情況，就是0和s[i-1]組成10或者是20。那么dp[i] = dp[i-2]。

如果s[i]不為0，那么s[i]可以選擇單獨(dú)成為一個(gè)字符，那么dp[i] = dp[i-1]。當(dāng)然如果s[i-1]是1或者是2的話，s[i]也可以選擇和s[i-1]合起來組成一個(gè)字符。那么這樣的情況下，dp[i]需要再額外增加dp[i-2]，也就是dp[i]構(gòu)成的答案可能性增加了。

如果把這些狀態(tài)之間的轉(zhuǎn)移情況都梳理清楚了，那么這個(gè)代碼肯定不難寫的。

class Solution:
????def numDecodings(self, s:?str) -> int:
????????n = len(s)
????????# 為了簡(jiǎn)化判斷，我們把s前面加上0，這樣字符串下標(biāo)從1開始
????????s = '0'?+ s
????????dp?= [0?for?_ in range(n+2)]
????????
????????dp[0] = 1
????????for?i in range(1, n+1):
????????????# 如果當(dāng)前位0，那么判斷前一位是否是1或2
????????????# 否則一定無解
????????????if?s[i] == '0':
????????????????if?i > 1?and?s[i-1] in ('1', '2'):
????????????????????dp[i] = dp[i-2]
????????????????else:
????????????????????return?0
????????????????continue
????????????dp[i] = dp[i-1]
????????????# 能和前一位構(gòu)成字符，那么加上dp[i-2]的數(shù)量
????????????if?i > 1?and?s[i-1] == '1'?or?s[i-1] == '2'?and?ord(s[i]) <= ord('6'):
????????????????dp[i] += dp[i-2]
????????return?dp[n]