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

Commita99b26b

Browse files
committed
add 322 solution
1 parentbfe1fdf commita99b26b

File tree

4 files changed

+161
-0
lines changed

4 files changed

+161
-0
lines changed

‎src/0006.ZigZag-Conversion/Solution.go

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

3+
import"fmt"
4+
35
funcconvert(sstring,numRowsint)string {
46
ifnumRows==1||numRows<=0||numRows>len(s) {
57
returns
@@ -23,10 +25,30 @@ func convert(s string, numRows int) string {
2325
}
2426
}
2527
}
28+
fmt.Println(strArr)
2629
res:=make([]byte,0)
2730

2831
for_,str:=rangestrArr {
2932
res=append(res,str...)
3033
}
3134
returnstring(res)
3235
}
36+
funcconvert2(sstring,numRowsint)string {
37+
ifnumRows<=1 {
38+
returns
39+
}
40+
lenth,cycle,n:=len(s),2*numRows-2,0
41+
result:=make([]byte,lenth)
42+
fori:=0;i<numRows;i++ {
43+
forj1:=i;j1<lenth;j1=cycle+j1 {
44+
45+
n+=copy(result[n:],string(s[j1]))
46+
j2:=j1+cycle-2*i
47+
ifi!=0&&i!=numRows-1&&j2<lenth {
48+
n+=copy(result[n:],string(s[j2]))
49+
}
50+
51+
}
52+
}
53+
returnstring(result)
54+
}

‎src/0322.Coin-Change/README.md

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
#[322. Coin Change][title]
2+
3+
##Description
4+
5+
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
6+
7+
**Example 1:**
8+
9+
```
10+
Input: coins = [1, 2, 5], amount = 11
11+
Output: 3
12+
Explanation: 11 = 5 + 5 + 1
13+
```
14+
15+
**Example 2:**
16+
17+
```
18+
Input: coins = [2], amount = 3
19+
Output: -1
20+
```
21+
22+
**Tags:** Math, String
23+
24+
##题意
25+
>给定 nn 种不同硬币的面值，以及需要凑出的总面值 totaltotal。请写一个函数，求最少需要多少硬币，可以凑出 totaltotal 的钱。
26+
如果不存在任何一种拼凑方案，则返回-1。
27+
28+
29+
30+
##题解
31+
32+
###动态规划
33+
>状态表示：
34+
- dp[i]表示凑出 ii 价值的钱，最少需要多少个硬币。
35+
- 第i种硬币 dp[i] = min(dp[i], min(dp[i - coins[i]] ) + 1)
36+
37+
```go
38+
funccoinChange(coins []int,amountint)int {
39+
dp:=make([]int, amount+1)
40+
fori:=0; i < amount+1; i++ {
41+
dp[i] = amount +1
42+
}
43+
dp[0] =0
44+
45+
fori:=1; i <= amount; i++ {
46+
forj:=0; j <len(coins); j++ {
47+
if coins[j] <= i {
48+
dp[i] =min(dp[i], dp[i-coins[j]]+1)
49+
}
50+
}
51+
}
52+
if dp[amount] > amount {
53+
return -1
54+
}
55+
return dp[amount]
56+
}
57+
```
58+
59+
###思路2
60+
>思路2
61+
```go
62+
63+
```
64+
65+
##结语
66+
67+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
68+
69+
[title]:https://leetcode.com/problems/two-sum/description/
70+
[me]:https://github.com/kylesliu/awesome-golang-leetcode

‎src/0322.Coin-Change/Solution.go

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package Solution
2+
3+
funccoinChange(coins []int,amountint)int {
4+
dp:=make([]int,amount+1)
5+
fori:=0;i<amount+1;i++ {
6+
dp[i]=amount+1
7+
}
8+
dp[0]=0
9+
10+
fori:=1;i<=amount;i++ {
11+
forj:=0;j<len(coins);j++ {
12+
ifcoins[j]<=i {
13+
dp[i]=min(dp[i],dp[i-coins[j]]+1)
14+
}
15+
}
16+
}
17+
ifdp[amount]>amount {
18+
return-1
19+
}
20+
returndp[amount]
21+
}
22+
23+
funcmin(x,yint)int {
24+
ifx>y {
25+
returny
26+
}
27+
returnx
28+
}

‎src/0322.Coin-Change/Solution_test.go

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package Solution
2+
3+
import (
4+
"reflect"
5+
"strconv"
6+
"testing"
7+
)
8+
9+
funcTestSolution(t*testing.T) {
10+
//测试用例
11+
cases:= []struct {
12+
namestring
13+
inputs []int
14+
amountint
15+
expectint
16+
}{
17+
{"TestCase", []int{1,2,5},11,3},
18+
{"TestCase", []int{2},3,-1},
19+
}
20+
21+
//开始测试
22+
fori,c:=rangecases {
23+
t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {
24+
got:=coinChange(c.inputs,c.amount)
25+
if!reflect.DeepEqual(got,c.expect) {
26+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
27+
c.expect,got,c.inputs)
28+
}
29+
})
30+
}
31+
}
32+
33+
//压力测试
34+
funcBenchmarkSolution(b*testing.B) {
35+
36+
}
37+
38+
//使用案列
39+
funcExampleSolution() {
40+
41+
}

0 commit comments

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