go在刷题中的小技巧

Go

模拟常用的数据结构

栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type content interface {
	string | int | int8 | int16 | int32 | int64 | float32 | float64 | []int
}

type Stack[T content] struct {
	data []T
}

func (s *Stack[T]) Push(el T) {
	s.data = append(s.data, el)
}

func (s *Stack[T]) Pop() (t T) {
	if len(s.data) == 0 {
		return
	}
	t = s.data[len(s.data)-1]
	s.data = s.data[:len(s.data)-1]
	return
}

队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type content interface {
	string | int | int8 | int16 | int32 | int64 | float32 | float64 | []int
}

type Queue[T content] struct {
	data []T
}

func (s *Queue[T]) EnQueue(el T) {
	s.data = append(s.data, el)
}

func (s *Queue[T]) DeQueue() (t T) {
	if len(s.data) == 0 {
		return
	}
	t = s.data[0]
	s.data = s.data[1:]
	return
}

最小堆

极简实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type MinHeap struct {
	sort.IntSlice
}

func (h *MinHeap) Push(x interface{}) {
	h.IntSlice = append(h.IntSlice, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	old := h.IntSlice
	n := len(old)
	x := old[n-1]
	h.IntSlice = old[0 : n-1]
	return x
}

最大堆

最大堆是最小堆的实现修改了 Less 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type MaxHeap struct {
	sort.IntSlice
}

func (h *MaxHeap) Push(x interface{}) {
	h.IntSlice = append(h.IntSlice, x.(int))
}

func (h *MaxHeap) Less(i, j int) bool {
	return h.IntSlice[i] > h.IntSlice[j]
}

func (h *MaxHeap) Pop() interface{} {
	old := h.IntSlice
	n := len(old)
	x := old[n-1]
	h.IntSlice = old[0 : n-1]
	return x
}

使用案列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func main() {
	minHeap := &MinHeap{[]int{1, 2, 4, 7, 9}}
	heap.Init(minHeap)
	heap.Push(minHeap, 3)
	pop := heap.Pop(minHeap)
	fmt.Printf("MinHeap len %v, Minheap Pop once %v
", minHeap.Len(), pop)

	maxHeap := &MaxHeap{[]int{1, 2, 4, 7, 9}}
	heap.Init(maxHeap)
	heap.Push(maxHeap, 3)
	pop1 := heap.Pop(maxHeap)
	fmt.Printf("MaxHeap len %v, MaxHeap Pop once %v
", maxHeap.Len(), pop1)

}

双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
type content interface {
	string | int | int8 | int16 | int32 | int64 | float32 | float64 | []int
}

type Deque[T content] struct {
	data []T
}

func (s *Deque[T]) EnQueueFront(el T) {
	s.data = append(s.data, el)
}

func (s *Deque[T]) DeQueueFront() (t T) {
	if len(s.data) == 0 {
		return
	}
	t = s.data[0]
	s.data = s.data[1:]
	return
}

func (s *Deque[T]) EnQueueBack(el T) {
	s.data = append(s.data, el)
}

func (s *Deque[T]) DeQueueBack() (t T) {
	if len(s.data) == 0 {
		return
	}
	t = s.data[0]
	s.data = s.data[1:]
	return
}

例子

1
2
3
4
5
6
7
8
9
10
11
12
func main() {
	q := Deque[string]{}
	q.EnQueueFront("aa")
	c := q.DeQueueBack()
	a := q.DeQueueFront()
	b := q.DeQueueFront()
	println(c)
	// 空字符串就是为空
	println(b == "")
	println(a == "")
}