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

Commit dfc4c44

Browse files
6boris6boris
authored
Merge pull request 6boris#114 from kylesliu/develop
update 241 problem solution
2 parents 68d2473 + 245ae98 commit dfc4c44

File tree

3 files changed

+87
-7
lines changed

3 files changed

+87
-7
lines changed

‎src/0241.Different-Ways-to-Add-Parentheses/Solution.go

Lines changed: 51 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,55 @@
11
package Solution
22

3+
import "strconv"
4+
35
func diffWaysToCompute(input string) []int {
4-
return []int{}
6+
return ways(input, map[string][]int{})
7+
}
8+
9+
func calculate(a, b int, operate rune) int {
10+
switch operate {
11+
case '+':
12+
return a + b
13+
case '-':
14+
return a - b
15+
case '*':
16+
return a * b
17+
default:
18+
panic("operate not exist")
19+
}
20+
}
21+
22+
func ways(input string, cache map[string][]int) []int {
23+
if _, ok := cache[input]; ok {
24+
return cache[input]
25+
}
26+
27+
ans := []int{}
28+
29+
for i := 0; i < len(input); i++ {
30+
ch := input[i]
31+
32+
if ch == '+' || ch == '-' || ch == '*' {
33+
left := input[:i]
34+
right := input[i+1:]
35+
36+
l := ways(left, cache)
37+
r := ways(right, cache)
38+
39+
for _, a := range l {
40+
for _, b := range r {
41+
ans = append(ans, calculate(a, b, rune(ch)))
42+
}
43+
}
44+
}
45+
}
46+
47+
if len(ans) == 0 {
48+
number, _ := strconv.Atoi(input)
49+
ans = append(ans, number)
50+
}
51+
52+
cache[input] = ans
53+
54+
return ans
555
}

‎src/0241.Different-Ways-to-Add-Parentheses/Solution_test.go

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

33
import (
4-
"reflect"
54
"strconv"
65
"testing"
76
)
@@ -21,9 +20,17 @@ func TestSolution(t *testing.T) {
2120
for i, c := range cases {
2221
t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
2322
got := diffWaysToCompute(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)
23+
if len(got) != len(c.expect) {
24+
t.Fatalf("expected: %v, but got: %v, with inputs: %v", c.expect, got, c.inputs)
25+
}
26+
m := make(map[int]int)
27+
for v := range got {
28+
m[v]++
29+
}
30+
for v := range c.expect {
31+
if _, ok := m[v]; !ok {
32+
t.Fatalf("expected: %v, but got: %v, with inputs: %v", c.expect, got, c.inputs)
33+
}
2734
}
2835
})
2936
}

‎src/0621.Task-Scheduler/Solution.go

Lines changed: 25 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,31 @@
11
package Solution
22

3+
import "sort"
34

4-
5+
func max(a, b int) int {
6+
if a > b {
7+
return a
8+
}
9+
return b
10+
}
511

612
func leastInterval(tasks []byte, n int) int {
7-
return 0
13+
tmp := make([]int, 26)
14+
temp := []int{}
15+
p := 1
16+
for _, v := range tasks {
17+
tmp[v-'A']++
18+
}
19+
for _, v := range tmp {
20+
temp = append(temp, v)
21+
}
22+
sort.Slice(temp, func(a, b int) bool {
23+
return temp[a] > temp[b]
24+
})
25+
for i := 1; i < len(temp); i++ {
26+
if temp[0] == temp[i] {
27+
p++
28+
}
29+
}
30+
return max((n+1)*(temp[0]-1)+p, len(tasks))
831
}

0 commit comments

Comments
 (0)
0