Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf2e26ad

Browse files
authored
Merge pull request6boris#88 from kylesliu/develop
update the 91 problem
2 parentsfc7559d +582812a commitf2e26ad

File tree

3 files changed

+77
-24
lines changed

3 files changed

+77
-24
lines changed

‎src/0091.Decode-Ways/README.md

Lines changed: 45 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,23 +1,28 @@
11
#[1. Add Sum][title]
22

33
##Description
4-
5-
Given two binary strings, return their sum (also a binary string).
6-
7-
The input strings are both**non-empty** and contains only characters`1` or`0`.
8-
4+
一个只包含 A-Z 的消息可以用如下方式编码成数字：
5+
```bash
6+
'A' -> 1
7+
'B' -> 2
8+
...
9+
'Z' -> 26
10+
```
11+
给定一个只包含数字的非空字符串，返回共有多少种解码方案。
912
**Example 1:**
1013

1114
```
12-
Input: a = "11", b = "1"
13-
Output: "100"
15+
Input: "12"
16+
Output: 2
17+
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
1418
```
1519

1620
**Example 2:**
1721

1822
```
19-
Input: a = "1010", b = "1011"
20-
Output: "10101"
23+
Input: "226"
24+
Output: 3
25+
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
2126
```
2227

2328
**Tags:** Math, String
@@ -28,16 +33,40 @@ Output: "10101"
2833
##题解
2934

3035
###思路1
31-
>按照小学算数那么来做，用`carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
36+
>(动态规划) O(n)
37+
>
38+
这道题目可以用动态规划来做。
39+
状态表示：f[i]f[i] 表示前 ii 个数字共有多少种解码方式。
40+
初始化：0个数字解码的方案数1，即 f[0]=1f[0]=1。
41+
状态转移：f[i]f[i] 可以表示成如下两部分的和：
3242

33-
```go
34-
35-
```
43+
- 如果第 ii 个数字不是0，则 ii 个数字可以单独解码成一个字母，此时的方案数等于用前 i−1i−1 个数字解码的方案数，即 f[i−1]f[i−1]；
44+
- 如果第 i−1i−1个数字和第 ii 个数字组成的两位数在 1010 到 2626 之间，则可以将这两位数字解码成一个字符，此时的方案数等于用前 i−2i−2 个数字解码的方案数，即 f[i−2]f[i−2]；
45+
时间复杂度分析：状态数是 nn 个，状态转移的时间复杂度是 O(1)O(1)，所以总时间复杂度是 O(n)O(n)。
3646

37-
###思路2
38-
>思路2
3947
```go
40-
48+
funcnumDecodings(sstring)int {
49+
n:=len(s)
50+
f:=make([]int, n+1)
51+
f[0] =1
52+
53+
fori:=1; i <= n; i++ {
54+
if s[i-1] <'0' || s[i-1] >'9' {
55+
return0
56+
}
57+
f[i] =0
58+
if s[i-1] !='0' {
59+
f[i] = f[i-1]
60+
}
61+
if i >1 {
62+
t:= (s[i-2]-'0')*10 + s[i-1] -'0'
63+
if t >=10 && t <=26 {
64+
f[i] += f[i-2]
65+
}
66+
}
67+
}
68+
return f[n]
69+
}
4170
```
4271

4372
##结语

‎src/0091.Decode-Ways/Solution.go

Lines changed: 27 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,30 @@
11
package Solution
22

3-
funcSolution(xbool)bool {
4-
returnx
3+
funcnumDecodings(sstring)int {
4+
// 思路：
5+
// 状态表示：f[i] i个数（最后一个数字是s[i-1]）解码得到的所有字符串的数量 f[i]从0开始
6+
// 状态计算： 集合可以分成：最后一个i是一位数，和最后一个i是两位数
7+
// 之前想过的错误思路：f[i] 表示以i结尾的decode共有多少种解法
8+
// 集合划分为不算i：f[i - j] + f[j] 和算i: f[i];
9+
n:=len(s)
10+
//加一是为了方便边界特判
11+
f:=make([]int,n+1)
12+
//空字符串特判
13+
f[0]=1
14+
// 如果最后一个i是个位数 1 ~ 26
15+
// 难点：如何转化char为int
16+
fori:=1;i<=n;i++ {//从一开始是因为表示的是前多少个字母，不是下标从一开始的字母
17+
//如果最后一个i是个位数，且不为0
18+
ifs[i-1]!='0' {
19+
f[i]+=f[i-1]
20+
}
21+
//如果最后一个i是两位数，且在1~26之间
22+
ifi>=2 {
23+
t:= (s[i-2]-'0')*10+s[i-1]-'0'
24+
ift>=10&&t<=26 {
25+
f[i]+=f[i-2]
26+
}
27+
}
28+
}
29+
returnf[n]
530
}

‎src/0091.Decode-Ways/Solution_test.go

Lines changed: 5 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -9,18 +9,17 @@ func TestSolution(t *testing.T) {
99
//测试用例
1010
cases:= []struct {
1111
namestring
12-
inputsbool
13-
expectbool
12+
inputsstring
13+
expectint
1414
}{
15-
{"TestCacse 1",true,true},
16-
{"TestCacse 1",true,true},
17-
{"TestCacse 1",false,false},
15+
{"TestCacse 1","12",2},
16+
{"TestCacse 1","226",3},
1817
}
1918

2019
//开始测试
2120
for_,c:=rangecases {
2221
t.Run(c.name,func(t*testing.T) {
23-
ret:=Solution(c.inputs)
22+
ret:=numDecodings(c.inputs)
2423
if!reflect.DeepEqual(ret,c.expect) {
2524
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
2625
c.expect,ret,c.inputs)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp