Skip to content

Commit 1934e38

Browse files
halfrosthalfrost
committed
添加 structures
1 parent ef3da5d commit 1934e38

18 files changed

+1079
-0
lines changed

‎structures/Heap.go

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package structures
2+
3+
// intHeap 实现了 heap 的接口
4+
type intHeap []int
5+
6+
func (h intHeap) Len() int {
7+
return len(h)
8+
}
9+
10+
func (h intHeap) Less(i, j int) bool {
11+
return h[i] < h[j]
12+
}
13+
14+
func (h intHeap) Swap(i, j int) {
15+
h[i], h[j] = h[j], h[i]
16+
}
17+
18+
func (h *intHeap) Push(x interface{}) {
19+
// Push 使用 *h，是因为
20+
// Push 增加了 h 的长度
21+
*h = append(*h, x.(int))
22+
}
23+
24+
func (h *intHeap) Pop() interface{} {
25+
// Pop 使用 *h ，是因为
26+
// Pop 减短了 h 的长度
27+
res := (*h)[len(*h)-1]
28+
*h = (*h)[:len(*h)-1]
29+
return res
30+
}

‎structures/Heap_test.go

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package structures
2+
3+
import (
4+
"container/heap"
5+
"fmt"
6+
"testing"
7+
8+
"github.com/stretchr/testify/assert"
9+
)
10+
11+
func Test_intHeap(t *testing.T) {
12+
ast := assert.New(t)
13+
14+
ih := new(intHeap)
15+
heap.Init(ih)
16+
17+
heap.Push(ih, 1)
18+
heap.Pop(ih)
19+
20+
begin, end := 0, 10
21+
for i := begin; i < end; i++ {
22+
heap.Push(ih, i)
23+
ast.Equal(0, (*ih)[0], "插入 %d 后的最小值却是 %d，ih=%v", i, (*ih)[0], (*ih))
24+
}
25+
26+
for i := begin; i < end; i++ {
27+
fmt.Println(i, *ih)
28+
ast.Equal(i, heap.Pop(ih), "Pop 后 ih=%v", (*ih))
29+
}
30+
}

‎structures/Interval.go

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package structures
2+
3+
// Interval 提供区间表示
4+
type Interval struct {
5+
Start int
6+
End int
7+
}
8+
9+
// Interval2Ints 把 Interval 转换成 整型切片
10+
func Interval2Ints(i Interval) []int {
11+
return []int{i.Start, i.End}
12+
}
13+
14+
// IntervalSlice2Intss 把 []Interval 转换成 [][]int
15+
func IntervalSlice2Intss(is []Interval) [][]int {
16+
res := make([][]int, 0, len(is))
17+
for i := range is {
18+
res = append(res, Interval2Ints(is[i]))
19+
}
20+
return res
21+
}
22+
23+
// Intss2IntervalSlice 把 [][]int 转换成 []Interval
24+
func Intss2IntervalSlice(intss [][]int) []Interval {
25+
res := make([]Interval, 0, len(intss))
26+
for _, ints := range intss {
27+
res = append(res, Interval{Start: ints[0], End: ints[1]})
28+
}
29+
return res
30+
}

‎structures/Interval_test.go

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package structures
2+
3+
import (
4+
"testing"
5+
6+
"github.com/stretchr/testify/assert"
7+
)
8+
9+
func Test_Interval2Ints(t *testing.T) {
10+
ast := assert.New(t)
11+
12+
actual := Interval2Ints(Interval{Start: 1, End: 2})
13+
expected := []int{1, 2}
14+
ast.Equal(expected, actual)
15+
}
16+
17+
func Test_IntervalSlice2Intss(t *testing.T) {
18+
ast := assert.New(t)
19+
20+
actual := IntervalSlice2Intss(
21+
[]Interval{
22+
Interval{
23+
Start: 1,
24+
End: 2,
25+
},
26+
Interval{
27+
Start: 3,
28+
End: 4,
29+
},
30+
},
31+
)
32+
expected := [][]int{
33+
[]int{1, 2},
34+
[]int{3, 4},
35+
}
36+
37+
ast.Equal(expected, actual)
38+
}
39+
func Test_Intss2IntervalSlice(t *testing.T) {
40+
ast := assert.New(t)
41+
42+
expected := []Interval{
43+
Interval{
44+
Start: 1,
45+
End: 2,
46+
},
47+
Interval{
48+
Start: 3,
49+
End: 4,
50+
},
51+
}
52+
actual := Intss2IntervalSlice([][]int{
53+
[]int{1, 2},
54+
[]int{3, 4},
55+
},
56+
)
57+
58+
ast.Equal(expected, actual)
59+
}

‎structures/ListNode.go

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
package structures
2+
3+
import (
4+
"fmt"
5+
)
6+
7+
// ListNode 是链接节点
8+
// 这个不能复制到*_test.go文件中。会导致Travis失败
9+
type ListNode struct {
10+
Val int
11+
Next *ListNode
12+
}
13+
14+
// List2Ints convert List to []int
15+
func List2Ints(head *ListNode) []int {
16+
// 链条深度限制，链条深度超出此限制，会 panic
17+
limit := 100
18+
19+
times := 0
20+
21+
res := []int{}
22+
for head != nil {
23+
times++
24+
if times > limit {
25+
msg := fmt.Sprintf("链条深度超过%d，可能出现环状链条。请检查错误，或者放宽 l2s 函数中 limit 的限制。", limit)
26+
panic(msg)
27+
}
28+
29+
res = append(res, head.Val)
30+
head = head.Next
31+
}
32+
33+
return res
34+
}
35+
36+
// Ints2List convert []int to List
37+
func Ints2List(nums []int) *ListNode {
38+
l := &ListNode{}
39+
t := l
40+
for _, v := range nums {
41+
t.Next = &ListNode{Val: v}
42+
t = t.Next
43+
}
44+
return l.Next
45+
}
46+
47+
// GetNodeWith returns the first node with val
48+
func (l *ListNode) GetNodeWith(val int) *ListNode {
49+
res := l
50+
for res != nil {
51+
if res.Val == val {
52+
break
53+
}
54+
res = res.Next
55+
}
56+
return res
57+
}
58+
59+
// Ints2ListWithCycle returns a list whose tail point to pos-indexed node
60+
// head's index is 0
61+
// if pos = -1, no cycle
62+
func Ints2ListWithCycle(nums []int, pos int) *ListNode {
63+
head := Ints2List(nums)
64+
if pos == -1 {
65+
return head
66+
}
67+
c := head
68+
for pos > 0 {
69+
c = c.Next
70+
pos--
71+
}
72+
tail := c
73+
for tail.Next != nil {
74+
tail = tail.Next
75+
}
76+
tail.Next = c
77+
return head
78+
}

‎structures/ListNode_test.go

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
package structures
2+
3+
import (
4+
"testing"
5+
6+
"github.com/stretchr/testify/assert"
7+
)
8+
9+
func Test_l2s(t *testing.T) {
10+
ast := assert.New(t)
11+
ast.Equal([]int{}, List2Ints(nil), "输入nil，没有返回[]int{}")
12+
13+
one2three := &ListNode{
14+
Val: 1,
15+
Next: &ListNode{
16+
Val: 2,
17+
Next: &ListNode{
18+
Val: 3,
19+
},
20+
},
21+
}
22+
ast.Equal([]int{1, 2, 3}, List2Ints(one2three), "没有成功地转换成[]int")
23+
24+
limit := 100
25+
overLimitList := Ints2List(make([]int, limit+1))
26+
ast.Panics(func() { List2Ints(overLimitList) }, "转换深度超过 %d 限制的链条，没有 panic", limit)
27+
}
28+
29+
func Test_s2l(t *testing.T) {
30+
ast := assert.New(t)
31+
ast.Nil(Ints2List([]int{}), "输入[]int{}，没有返回nil")
32+
33+
ln := Ints2List([]int{1, 2, 3, 4, 5, 6, 7, 8, 9})
34+
i := 1
35+
for ln != nil {
36+
ast.Equal(i, ln.Val, "对应的值不对")
37+
ln = ln.Next
38+
i++
39+
}
40+
}
41+
42+
func Test_getNodeWith(t *testing.T) {
43+
ast := assert.New(t)
44+
//
45+
ln := Ints2List([]int{1, 2, 3, 4, 5, 6, 7, 8, 9})
46+
val := 10
47+
node := &ListNode{
48+
Val: val,
49+
}
50+
tail := ln
51+
for tail.Next != nil {
52+
tail = tail.Next
53+
}
54+
tail.Next = node
55+
expected := node
56+
actual := ln.GetNodeWith(val)
57+
ast.Equal(expected, actual)
58+
}
59+
60+
func Test_Ints2ListWithCycle(t *testing.T) {
61+
ast := assert.New(t)
62+
ints := []int{1, 2, 3}
63+
l := Ints2ListWithCycle(ints, -1)
64+
ast.Equal(ints, List2Ints(l))
65+
66+
l = Ints2ListWithCycle(ints, 1)
67+
ast.Panics(func() { List2Ints(l) })
68+
}

‎structures/NestedInteger.go

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package structures
2+
3+
// NestedInteger is the interface that allows for creating nested lists.
4+
// You should not implement it, or speculate about its implementation
5+
type NestedInteger struct {
6+
Num int
7+
Ns []*NestedInteger
8+
}
9+
10+
// IsInteger Return true if this NestedInteger holds a single integer, rather than a nested list.
11+
func (n NestedInteger) IsInteger() bool {
12+
return n.Ns == nil
13+
}
14+
15+
// GetInteger Return the single integer that this NestedInteger holds, if it holds a single integer
16+
// The result is undefined if this NestedInteger holds a nested list
17+
// So before calling this method, you should have a check
18+
func (n NestedInteger) GetInteger() int {
19+
return n.Num
20+
}
21+
22+
// SetInteger Set this NestedInteger to hold a single integer.
23+
func (n *NestedInteger) SetInteger(value int) {
24+
n.Num = value
25+
}
26+
27+
// Add Set this NestedInteger to hold a nested list and adds a nested integer to it.
28+
func (n *NestedInteger) Add(elem NestedInteger) {
29+
n.Ns = append(n.Ns, &elem)
30+
}
31+
32+
// GetList Return the nested list that this NestedInteger holds, if it holds a nested list
33+
// The list length is zero if this NestedInteger holds a single integer
34+
// You can access NestedInteger's List element directly if you want to modify it
35+
func (n NestedInteger) GetList() []*NestedInteger {
36+
return n.Ns
37+
}

‎structures/NestedInterger_test.go

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package structures
2+
3+
import (
4+
"testing"
5+
6+
"github.com/stretchr/testify/assert"
7+
)
8+
9+
func Test_NestedInteger(t *testing.T) {
10+
ast := assert.New(t)
11+
12+
n := NestedInteger{}
13+
14+
ast.True(n.IsInteger())
15+
16+
n.SetInteger(1)
17+
ast.Equal(1, n.GetInteger())
18+
19+
elem := NestedInteger{Num: 1}
20+
21+
expected := NestedInteger{
22+
Num: 1,
23+
Ns: []*NestedInteger{&elem},
24+
}
25+
n.Add(elem)
26+
27+
ast.Equal(expected, n)
28+
29+
ast.Equal(expected.Ns, n.GetList())
30+
}

‎structures/Point.go

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package structures
2+
3+
// Point 定义了一个二维坐标点
4+
type Point struct {
5+
X, Y int
6+
}
7+
8+
// Intss2Points 把 [][]int 转换成 []Point
9+
func Intss2Points(points [][]int) []Point {
10+
res := make([]Point, len(points))
11+
for i, p := range points {
12+
res[i] = Point{
13+
X: p[0],
14+
Y: p[1],
15+
}
16+
}
17+
return res
18+
}
19+
20+
// Points2Intss 把 []Point 转换成　[][]int
21+
func Points2Intss(points []Point) [][]int {
22+
res := make([][]int, len(points))
23+
for i, p := range points {
24+
res[i] = []int{p.X, p.Y}
25+
}
26+
return res
27+
}

0 commit comments

Comments
 (0)