8000 Merge pull request #88 from kylesliu/develop · dycn/awesome-golang-leetcode@f2e26ad · GitHub
[go: up one dir, main page]
Skip to content

Commit f2e26ad

Browse files
6boris6boris
authored
Merge pull request 6boris#88 from kylesliu/develop
update the 91 problem
2 parents fc7559d + 582812a commit f2e26ad

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` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即 8000 可，直到把两个二进制串都遍历完即可。
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+
func numDecodings(s string) int {
49+
n := len(s)
50+
f := make([]int, n+1)
51+
f[0] = 1
52+
53+
for i := 1; i <= n; i++ {
54+
if s[i-1] < '0' || s[i-1] > '9' {
55+
return 0
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-
func Solution(x bool) bool {
4-
return x
3+
func numDecodings(s string) 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+
for i := 1; i <= n; i++ { //从一开始是因为表示的是前多少个字母，不是下标从一开始的字母
17+
//如果最后一个i是个位数，且不为0
18+
if s[i-1] != '0' {
19+
f[i] += f[i-1]
20+
}
21+
//如果最后一个i是两位数，且在1~26之间
22+
if i >= 2 {
23+
t := (s[i-2]-'0')*10 + s[i-1] - '0'
24+
if t >= 10 && t <= 26 {
25+
f[i] += f[i-2]
26+
}
27+
}
28+
}
29+
return f[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
name string
12-
inputs bool
13-
expect bool
12+
inputs string
13+
expect int
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 := range cases {
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)
0