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

Commita16e51a

Browse files
committed
add 628 solution
1 parent668447c commita16e51a

File tree

3 files changed

+162
-0
lines changed

3 files changed

+162
-0
lines changed
Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
#[628. Maximum Product of Three Numbers][title]
2+
3+
##Description
4+
5+
Given an integer array, find three numbers whose product is maximum and output the maximum product.
6+
**Example 1:**
7+
8+
```
9+
Input: a = "11", b = "1"
10+
Output: "100"
11+
```
12+
13+
**Example 2:**
14+
15+
```
16+
Input: a = "1010", b = "1011"
17+
Output: "10101"
18+
```
19+
20+
**Tags:** Math, String
21+
22+
##题意
23+
>求2数之和
24+
25+
##题解
26+
27+
###思路1
28+
>三个数的最大乘积，必然是三个最大的数的乘积或者两个最小的（负）数与最大数的乘积。
29+
通过线性扫描或者排序找出最大的三个数和最小的两个数即可。
30+
31+
时间复杂
32+
线性扫描的时间复杂度是 O(n)O(n)；排序的时间复杂度是 O(nlogn)O(nlog⁡n)。
33+
34+
```go
35+
funcmaximumProduct(nums []int)int {
36+
sort.Ints(nums)
37+
n:=len(nums)
38+
returnmax(nums[n-1]*nums[n-2]*nums[n-3], nums[n-1]*nums[0]*nums[1])
39+
}
40+
```
41+
42+
###思路2
43+
>思路2
44+
```go
45+
46+
```
47+
48+
##结语
49+
50+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
51+
52+
[title]:https://leetcode.com/problems/maximum-product-of-three-numbers/
53+
[me]:https://github.com/kylesliu/awesome-golang-leetcode
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package Solution
2+
3+
import (
4+
"sort"
5+
)
6+
7+
funcmax(x,yint)int {
8+
ifx>y {
9+
returnx
10+
}
11+
returny
12+
}
13+
14+
// 暴力排序解法
15+
funcmaximumProduct(nums []int)int {
16+
sort.Ints(nums)
17+
n:=len(nums)
18+
returnmax(nums[n-1]*nums[n-2]*nums[n-3],nums[n-1]*nums[0]*nums[1])
19+
}
20+
21+
// 桶排序排序 O(N)
22+
funcmaximumProduct2(nums []int)int {
23+
max1,max2,max3,min1,min2:=-1001,-1001,-1001,1001,1001
24+
25+
for_,v:=rangenums {
26+
ifv>max1 {
27+
max3=max2
28+
max2=max1
29+
max1=v
30+
}elseifv>max2 {
31+
max3=max2
32+
max2=v
33+
}elseifv>max3 {
34+
max3=v
35+
}
36+
37+
ifv<min1 {
38+
min2=min1
39+
min1=v
40+
}elseifv<min2 {
41+
min2=v
42+
}
43+
44+
}
45+
returnmax(max1*min1*min2,max1*max2*max3)
46+
}
Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
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+
expectint
15+
}{
16+
{"TestCase", []int{1,2,3},6},
17+
{"TestCase", []int{1,2,3,4},24},
18+
}
19+
20+
//开始测试
21+
fori,c:=rangecases {
22+
t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {
23+
got:=maximumProduct(c.inputs)
24+
if!reflect.DeepEqual(got,c.expect) {
25+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
26+
c.expect,got,c.inputs)
27+
}
28+
})
29+
}
30+
}
31+
32+
funcTestSolution2(t*testing.T) {
33+
//测试用例
34+
cases:= []struct {
35+
namestring
36+
inputs []int
37+
expectint
38+
}{
39+
{"TestCase", []int{1,2,3},6},
40+
{"TestCase", []int{1,2,3,4},24},
41+
}
42+
43+
//开始测试
44+
fori,c:=rangecases {
45+
t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {
46+
got:=maximumProduct2(c.inputs)
47+
if!reflect.DeepEqual(got,c.expect) {
48+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
49+
c.expect,got,c.inputs)
50+
}
51+
})
52+
}
53+
}
54+
55+
//压力测试
56+
funcBenchmarkSolution(b*testing.B) {
57+
58+
}
59+
60+
//使用案列
61+
funcExampleSolution() {
62+
63+
}

0 commit comments

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