Go Java算法之解碼方法示例詳解
解碼方法
一條包含字母 A-Z 的消息通過(guò)以下映射進(jìn)行了 編碼 ：
- 'A' -> "1"
- 'B' -> "2"
- ...
- 'Z' -> "26"
要 解碼 已編碼的消息，所有數(shù)字必須基于上述映射的方法，反向映射回字母（可能有多種方法）。例如，"11106" 可以映射為：
"AAJF" ，將消息分組為 (1 1 10 6)
"KJF" ，將消息分組為 (11 10 6)
注意，消息不能分組為 (1 11 06) ，因?yàn)?"06" 不能映射為 "F" ，這是由于 "6" 和 "06" 在映射中并不等價(jià)。
給你一個(gè)只含數(shù)字的 非空 字符串 s ，請(qǐng)計(jì)算并返回 解碼 方法的 總數(shù) 。
題目數(shù)據(jù)保證答案肯定是一個(gè) 32 位 的整數(shù)。
- 示例 1：
輸入：s = "12"
輸出：2
解釋?zhuān)核梢越獯a為 "AB"（1 2）或者 "L"（12）。
- 示例 2：
輸入：s = "226"
輸出：3
解釋?zhuān)核梢越獯a為 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
- 示例 3：
輸入：s = "0"
輸出：0
解釋?zhuān)簺](méi)有字符映射到以 0 開(kāi)頭的數(shù)字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于沒(méi)有字符，因此沒(méi)有有效的方法對(duì)此進(jìn)行解碼，因?yàn)樗袛?shù)字都需要映射。
提示：
1 <= s.length <= 100
s 只包含數(shù)字，并且可能包含前導(dǎo)零。
方法一：動(dòng)態(tài)規(guī)劃（Java）
對(duì)于給定的字符串 s ，設(shè)它的長(zhǎng)度為 n ，其中的字符從左到右依次為 s[1],s[2],...,s[n]。我們可以使用動(dòng)態(tài)規(guī)劃的方法計(jì)算出字符串的解碼方法數(shù)。
具體地，設(shè) fi表示字符串s的前i個(gè)字符 s[1..i]的解碼方法數(shù)。在進(jìn)行狀態(tài)轉(zhuǎn)移時(shí)，我們可以考慮最后一次解碼使用了 s中的哪些字符
class Solution {
public int numDecodings(String s) {
int n = s.length();
int[] f = new int[n + 1];
f[0] = 1;
for (int i = 1; i <= n; ++i) {
if (s.charAt(i - 1) != '0') {
f[i] += f[i - 1];
}
if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
f[i] += f[i - 2];
}
}
return f[n];
}
}
時(shí)間復(fù)雜度：o（n）
空間復(fù)雜度：o（n）
方法二：動(dòng)態(tài)規(guī)劃——優(yōu)化（go）
具體的方法思路請(qǐng)看上文表述，本方法對(duì)空間復(fù)雜度進(jìn)行了優(yōu)化，通過(guò)使用臨時(shí)變量的方式，使得空間復(fù)雜度從o(n)降為o(1)
func numDecodings(s string) int {
n := len(s)
// a = f[i-2], b = f[i-1], c = f[i]
a, b, c := 0, 1, 0
for i := 1; i <= n; i++ {
c = 0
if s[i-1] != '0' {
c += b
}
if i > 1 && s[i-2] != '0' && ((s[i-2]-'0')*10+(s[i-1]-'0') <= 26) {
c += a
}
a, b = b, c
}
return c
}
時(shí)間復(fù)雜度：o（n）
空間復(fù)雜度：o（1）
以上就是Go Java算法之解碼方法示例詳解的詳細(xì)內(nèi)容，更多關(guān)于Go Java算法解碼的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Java中的CopyOnWriteArrayList深入解讀
這篇文章主要介紹了Java中的CopyOnWriteArrayList深入解讀,在 ArrayList 的類(lèi)注釋上,JDK 就提醒了我們,如果要把 ArrayList 作為共享變量的話,是線程不安全的,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了Java中的Timer與TimerTask源碼及使用解析,在Java中,經(jīng)常使用Timer來(lái)定時(shí)調(diào)度任務(wù),Timer調(diào)度任務(wù)有一次性調(diào)度和循環(huán)調(diào)度,循環(huán)調(diào)度有分為固定速率調(diào)度(fixRate)和固定時(shí)延調(diào)度(fixDelay),需要的朋友可以參考下2023-10-10
SpringBoot統(tǒng)一返回處理出現(xiàn)cannot?be?cast?to?java.lang.String異常解決
這篇文章主要給大家介紹了關(guān)于SpringBoot統(tǒng)一返回處理出現(xiàn)cannot?be?cast?to?java.lang.String異常解決的相關(guān)資料,文中通過(guò)圖文介紹的非常詳細(xì),需要的朋友可以參考下2023-09-09
JAVA中string數(shù)據(jù)類(lèi)型轉(zhuǎn)換詳解
在JAVA中string是final類(lèi)，提供字符串不可以修改，string類(lèi)型在項(xiàng)目中經(jīng)常使用，下面給大家介紹了string七種數(shù)據(jù)類(lèi)型轉(zhuǎn)換，需要的朋友可以參考下2015-07-07
RabbitMq中channel接口的幾種常用參數(shù)詳解
這篇文章主要介紹了RabbitMq中channel接口的幾種常用參數(shù)詳解,RabbitMQ 不會(huì)為未確認(rèn)的消息設(shè)置過(guò)期時(shí)間,它判斷此消息是否需要重新投遞給消費(fèi)者的唯一依據(jù)是消費(fèi)該消息的消費(fèi)者連接是否己經(jīng)斷開(kāi),需要的朋友可以參考下2023-08-08
這篇文章主要介紹了Java Condition條件變量提高線程通信效率,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-10-10
這篇文章主要介紹了 Java解決通信過(guò)程的中文亂碼的問(wèn)題的相關(guān)資料,需要的朋友可以參考下2017-01-01
JavaWeb后臺(tái)購(gòu)物車(chē)類(lèi)實(shí)現(xiàn)代碼詳解
這篇文章主要介紹了JavaWeb后臺(tái)購(gòu)物車(chē)類(lèi)實(shí)現(xiàn)代碼詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07
spring boot高并發(fā)下耗時(shí)操作的實(shí)現(xiàn)方法
這篇文章主要給大家介紹了關(guān)于spring boot高并發(fā)下耗時(shí)操作的實(shí)現(xiàn)方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用spring boot具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-11-11
這篇文章主要介紹了Java之常用類(lèi)小結(jié)案例講解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07