Golang数据结构与算法

/* map 案例 */
func MapCase() {
	mp := make(map[string]string, 3)
	mp["A"] = "a"
	mp["B"] = "b"
	mp["C"] = "c"
	fmt.Println(mp)
	f1(mp)
	fmt.Println(mp)
	/*
		map[A:a B:b C:c]
		map[A:a1 B:b C:c D:d E:e] 引用传递，会受影响
	*/
	for k, v := range mp {
		fmt.Println(k, v) // 多次执行结果不一样，是无序的
	}
}

func f1(mp map[string]string) {
	mp["A"] = "a1"
	mp["D"] = "d"
	mp["E"] = "e"
}

type Set struct {
	data map[int]struct{} // 利用map的key不能重复的特性实现set，value设置为空结构体，因为结构体不赋值的情况下占用空间为0
	sync.RWMutex
}

func newSet() *Set {
	return &Set{
		data: make(map[int]struct{}),
	}
}

func (s *Set) Add(i int) {
	s.Lock()
	defer s.Unlock()
	s.data[i] = struct{}{}
}
func (s *Set) Remove(i int) {
	s.Lock()
	defer s.Unlock()
	if len(s.data) == 0 {
		return
	}
	delete(s.data, i)
}
func (s *Set) Len() int {
	return len(s.data)
}

func (s *Set) Exists(i int) bool {
	s.RLock()
	defer s.RUnlock()
	_, ok := s.data[i]
	return ok
}

func (s *Set) IsEmpty() bool {
	return len(s.data) == 0
}

func (s *Set) List() []int {
	s.RLock()
	defer s.RUnlock()
	list := make([]int, len(s.data))
	i := 0
	for k, _ := range s.data {
		list[i] = k
		i++
	}
	return list
}

func (s *Set) Clear() {
	s.Lock()
	defer s.Unlock()
	s.data = make(map[int]struct{})
}

func SetCase() {
	set := newSet()
	set.Add(1)
	set.Add(2)
	set.Add(3)
	set.Add(4)
	set.Add(5)
	set.Add(6)
	set.Add(7)
	set.Add(8)
	set.Remove(3)
	fmt.Println(set.Exists(3), set.Exists(2), set.Len())
	fmt.Println(set.List())
	set.Clear()
	fmt.Println(set.List())
	/*
		false true 7
		[5 6 7 8 1 2 4]
		[]
	*/
}

func MemCacheCase() {
	cache := newMemCache()
	cache.Set("k1", "v1", 2*time.Second)
	cache.Set("k2", "v2", 4*time.Second)
	cache.Set("k3", "v3", 0)
	cache.Set("k4", "v4", 6*time.Second)
	cache.Set("k5", "v5", 8*time.Second)
	fmt.Println(cache.Get("k1"))
	fmt.Println(cache.Get("k2"))
	fmt.Println(cache.Get("k3"))
	fmt.Println(cache.Get("k4"))
	fmt.Println(cache.Get("k5"))
	time.Sleep(6 * time.Second)
	fmt.Println(cache.Get("k1"))
	fmt.Println(cache.Get("k2"))
	fmt.Println(cache.Get("k3"))
	fmt.Println(cache.Get("k4"))
	fmt.Println(cache.Get("k5"))
	/*
		v1
		v2
		v3
		v4
		v5
		<nil>
		<nil>
		v3
		<nil>
		v5
	*/
}

type Item struct {
	ExpireAt time.Time
	value    interface{}
}

type MemCache struct {
	data         map[string]*Item
	sync.RWMutex // 只要是使用map的场景，我们就要注意使用锁
}

func newMemCache() *MemCache {
	cache := &MemCache{
		data: make(map[string]*Item),
	}
	go cache.cleaner()
	return cache
}

func (c *MemCache) Set(key string, value interface{}, duration time.Duration) {
	c.Lock()
	defer c.Unlock()
	item := &Item{
		value: value,
	}
	if duration != 0 {
		item.ExpireAt = time.Now().Add(duration)
	}
	c.data[key] = item
}

func (c *MemCache) Get(key string) interface{} {
	c.RLock()
	defer c.RUnlock()
	item, ok := c.data[key]
	if !ok {
		return nil
	}
	if !item.ExpireAt.IsZero() && item.ExpireAt.Before(time.Now()) { // 过期
		return nil
	}
	return item.value
}
func (c *MemCache) cleaner() {
	for {
		<-time.After(5 * time.Second)
		c.Lock()
		for k, item := range c.data {
			if !item.ExpireAt.IsZero() && item.ExpireAt.Before(time.Now()) { // 过期
				delete(c.data, k)
			}
		}
		c.Unlock()
		time.Sleep(time.Second)
	}
}

package _case

import "fmt"

// 单链表
type SingleLinkNode struct {
	Data interface{}
	Next *SingleLinkNode
}

func LinkCase() {
	link := &LinkNode{data: 1}
	link = link.Link(&LinkNode{data: 2})
	link = link.Link(&LinkNode{data: 3})
	link = link.Link(&LinkNode{data: 4})
	link = link.Link(&LinkNode{data: 5})
	link = link.Link(&LinkNode{data: 6})
	link = link.Link(&LinkNode{data: 7})
	link = link.Link(&LinkNode{data: 8})
	link = link.Link(&LinkNode{data: 9})
	link = link.Link(&LinkNode{data: 10})
	fmt.Println(link.Len(), link)
	node5 := link.Move(-5)
	fmt.Println(node5)
	fmt.Println(node5.Move(5))
	node5.Unlink(3)
	fmt.Println(link.Len(), link)
}

// 双链表
type LinkNode struct {
	prev *LinkNode
	data interface{}
	next *LinkNode
}

type BidLink = LinkNode // 别名,思维上的区别，这个指链表，上面那个指节点，其实是一个东西
func (l *BidLink) Next() *LinkNode {
	return l.next
}

func (l *BidLink) Prev() *LinkNode {
	return l.prev
}

// 添加
func (l *BidLink) Link(node *LinkNode) *LinkNode {
	if node == nil {
		return nil
	}
	node.next = l.next
	node.prev = l
	if l.next != nil {
		l.next.prev = node
	}
	l.next = node
	return node
}

// 向前或向后查找第n个
func (l *BidLink) Move(n int) *LinkNode {
	var r *LinkNode
	// 向后找
	if n > 0 {
		r = l.next
		for i := 1; i < n; i++ {
			if r == nil {
				return nil
			}
			r = r.next
		}
		return r
	} else if n < 0 { // 向前找
		r = l.prev
		for i := n + 1; i < 0; i++ {
			if r == nil {
				return nil
			}
			r = r.prev
		}
		return r
	}
	return l
}

// 移除当前节点前、后n个元素
func (l *BidLink) Unlink(n int) {
	if n == 0 {
		return
	}
	if n > 0 {
		l.Link(l.Move(n + 1))
	}
	if n < 0 {
		p := l.Move(n - 1)
		if p == nil {
			l.prev = p
		} else {
			p.Link(l)
		}
	}
}

func (l *BidLink) Len() int {
	prevLen := 0
	nextLen := 0
	p := l.prev
	for {
		if p == nil {
			break
		}
		prevLen++
		p = p.prev
	}
	n := l.next
	for {
		if n == nil {
			break
		}
		nextLen++
		n = n.next
	}
	return prevLen + nextLen + 1
}

package _case

import (
	"fmt"
	"sync"
)

func LRUCacheCase() {
	cache := newLRUCache(3)
	cache.Put("a", "1")
	cache.Put("b", "2")
	cache.Put("c", "3")
	fmt.Println(cache.Size())
	cache.List()
	fmt.Println(cache.Get("a"))
	fmt.Println(cache.Get("b"))
	cache.List()
	cache.Put("d", "4")
	fmt.Println(cache.Size())
	cache.List()
}

type Node struct {
	key        string
	value      interface{}
	prev, next *Node
}

type LRUCache struct {
	cap        int
	head, tail *Node
	nodeMap    map[string]*Node
	sync.Mutex
}

func newLRUCache(cap int) *LRUCache {
	return &LRUCache{
		cap:     cap,
		head:    nil,
		tail:    nil,
		nodeMap: map[string]*Node{},
	}
}

func (c *LRUCache) removeTail() *Node {
	var tail *Node
	if c.tail == nil {
		return nil
	}
	tail = c.tail
	prev := c.tail.prev
	if prev != nil {
		prev.next = nil
	}
	c.tail = prev
	return tail
}

func (c *LRUCache) add(node *Node) {
	node.next = c.head
	node.prev = nil
	if c.head != nil {
		c.head.prev = node
	}
	c.head = node
	if c.tail == nil {
		c.tail = node
	}
}

func (c *LRUCache) moveToHead(node *Node) {
	if node == c.head {
		return
	}
	prev := node.prev
	next := node.next
	if prev != nil {
		prev.next = next
	}
	if next != nil {
		next.prev = prev
	}
	if node == c.tail {
		c.tail = prev
	}
	node.prev = nil
	node.next = c.head
	c.head.prev = node
	c.head = node
}

func (c *LRUCache) Put(key string, value interface{}) {
	c.Lock()
	defer c.Unlock()
	node, ok := c.nodeMap[key]
	if !ok {
		if c.cap == len(c.nodeMap) {
			// 移除尾部元素
			tail := c.removeTail()
			if tail != nil {
				delete(c.nodeMap, tail.key)
			}
		}
		// 头部添加新元素
		node = &Node{
			key:   key,
			value: value,
		}
		c.add(node)
	} else {
		node.value = value
		c.moveToHead(node)
	}
	c.nodeMap[node.key] = node
}

func (c *LRUCache) Get(key string) interface{} {
	c.Lock()
	defer c.Unlock()
	node, ok := c.nodeMap[key]
	if !ok {
		return nil
	}
	c.moveToHead(node)
	return node.value
}

func (c *LRUCache) Size() int {
	return len(c.nodeMap)
}
func (c *LRUCache) List() []*Node {
	list := make([]*Node, 0)
	n := c.head
	for {
		if n == nil {
			break
		}
		fmt.Println(n)
		list = append(list, n)
		n = n.next
	}
	return list
}

package main

import (
	"fmt"
	"sync"
)

func main() {
	QueueCase1()
}

func QueueCase1() {
	queue := newQueue()
	wg := sync.WaitGroup{}
	for i := 0; i < 10; i++ {
		wg.Add(1)
		go func() {
			defer wg.Done()
			for j := 0; j < 10; j++ {
				queue.Add(j)
			}
		}()
	}
	wg.Wait()
	fmt.Println(queue.Len())
	for {
		v := queue.Remove()
		if v == nil {
			break
		}
	}
	fmt.Println(queue.Len())
}

func QueueCase() {
	queue := newQueue()
	queue.Add("A")
	queue.Add("B")
	queue.Add("C")
	queue.Add("D")
	queue.Add("E")
	fmt.Println(queue.Len())
	fmt.Println(queue.Remove())
	fmt.Println(queue.Remove())
	fmt.Println(queue.Remove())
	fmt.Println(queue.Remove())
}

type Queue struct {
	data []interface{}
	sync.Mutex
}

func newQueue() *Queue {
	return &Queue{
		data: make([]interface{}, 0),
	}
}

func (q *Queue) Add(v interface{}) {
	q.Lock()
	defer q.Unlock()
	q.data = append(q.data, v)
}

func (q *Queue) Remove() interface{} {
	q.Lock()
	defer q.Unlock()
	var v interface{}
	if len(q.data) > 0 {
		v = q.data[0]
		q.data = q.data[1:]
	}
	return v
}

func (q *Queue) Len() int {
	return len(q.data)
}

package main

import (
	"fmt"
	"sync"
)

func main() {
	StackCase1()
}

func StackCase() {
	stack := newStack()
	stack.Push("A")
	stack.Push("B")
	stack.Push("C")
	stack.Push("D")
	stack.Push("E")
	fmt.Println(stack.Size())
	fmt.Println(stack.Peak())
	fmt.Println(stack.Pop())
	fmt.Println(stack.Pop())
	stack.Push("F")
	fmt.Println(stack.Peak())
	fmt.Println(stack.Size())
}

type Stack struct {
	data []interface{}
	sync.Mutex
}

func newStack() *Stack {
	return &Stack{
		data: make([]interface{}, 0),
	}
}

func (s *Stack) Push(v interface{}) {
	s.Lock()
	defer s.Unlock()
	s.data = append(s.data, v)
}

func (s *Stack) Pop() interface{} {
	s.Lock()
	defer s.Unlock()
	var v interface{}
	if len(s.data) > 0 {
		v = s.data[len(s.data)-1]
		s.data = s.data[0 : len(s.data)-1]
	}
	return v
}

func (s *Stack) Peak() interface{} {
	s.Lock()
	defer s.Unlock()
	var v interface{}
	if len(s.data) > 0 {
		v = s.data[len(s.data)-1]
	}
	return v
}

func (s *Stack) Size() int {
	return len(s.data)
}

func strVaild(s string) bool {
	stack := newStack()
	for _, c := range s {
		if c == '(' || c == '[' || c == '{' {
			stack.Push(c)
		} else if c == ')' || c == ']' || c == '}' {
			if stack.Size() == 0 {
				return false
			}
			c1 := stack.Pop()
			if c == ')' && c1 == '(' || c == ']' && c1 == '[' || c == '}' && c1 == '{' {
				continue
			}
			return false
		}
	}
	return stack.Size() == 0
}

func StackCase1() {
	str1 := "{abdcd[89jyf(59332)]}"
	str2 := "{abdcd[89j(yf(59332)]}"
	str3 := "{abdcd[89jyf}}(59332)]}"
	fmt.Println(strVaild(str1))
	fmt.Println(strVaild(str2))
	fmt.Println(strVaild(str3))
}

package _case

import (
	"fmt"
	"math"
)

type Node struct {
	key   int
	val   interface{}
	left  *Node
	right *Node
}

func BstreeCase() {
	bst := &Node{key: 10, val: "A"}
	bst.Insert(5, "B")
	bst.Insert(15, "C")
	bst.Insert(8, "D")
	bst.Insert(13, "E")
	bst.Insert(17, "F")
	bst.Insert(4, "G")
	bst.Insert(7, "H")
	bst.Insert(6, "I")
	bst.Insert(12, "J")
	bst.Insert(14, "K")
	bst.Insert(16, "L")
	bst.Insert(18, "M")
	printTree(bst)
	fmt.Println(bst.Find(15))
	fmt.Println(bst.Find(5))
	fmt.Println(bst.Find(15).FindMin())
	fmt.Println(bst.Find(4).FindMin())
	bst.Delete(15)
	printTree(bst)
	bst.Delete(5)
	printTree(bst)
}

func (n *Node) Insert(key int, val interface{}) *Node {
	if n == nil {
		return &Node{
			key: key,
			val: val,
		}
	}
	if key < n.key {
		n.left = n.left.Insert(key, val)
	} else if key > n.key {
		n.right = n.right.Insert(key, val)
	}
	return n
}

func (n *Node) Search(key int) interface{} {
	node := n.Find(key)
	if node != nil {
		return node.val
	}
	return nil
}

func (n *Node) Find(key int) *Node {
	if n == nil || n.key == key {
		return n
	}
	if key < n.key {
		return n.left.Find(key)
	}
	return n.right.Find(key)
}

func (n *Node) FindMin() *Node {
	if n == nil {
		return nil
	}
	l := n
	for l.left != nil {
		l = l.left
	}
	return l
}

func (n *Node) Delete(key int) *Node {
	if n == nil {
		return nil
	}
	if key < n.key {
		n.left = n.left.Delete(key)
	} else if key > n.key {
		n.right = n.right.Delete(key)
	} else {
		if n.left == nil {
			return n.right
		}
		if n.right == nil {
			return n.left
		}
		min := n.right.FindMin()
		n.key = min.key
		n.val = min.val
		n.right = n.right.Delete(min.key)
	}
	return n
}

func levelOrder(root *Node) []int {
	if root == nil {
		return []int{}
	}
	var result []int
	queue := []*Node{root}
	for len(queue) > 0 {
		count := len(queue)
		for i := 0; i < count; i++ {
			node := queue[0]
			queue = queue[1:]
			if node.left != nil {
				queue = append(queue, node.left)
			}
			if node.right != nil {
				queue = append(queue, node.right)
			}
		}
		result = append(result, count)
	}
	return result
}

func printTree(root *Node) {
	levels := levelOrder(root)
	fmt.Println(levels)
	levelCount := len(levels)
	length := int(math.Pow(2, float64(levelCount-1)) + 5)
	tb := make([][]int, levelCount)
	for i := 0; i < levelCount; i++ {
		tb[i] = make([]int, length)
	}
	calNodePosition(root, levelCount, 0, 0, false, true, tb)
	for _, item := range tb {
		for _, i := range item {
			if i == 0 {
				fmt.Print(" ")
				continue
			}
			fmt.Print(i)
		}
		fmt.Println()
	}
}

func calNodePosition(node *Node, levelCount, parentLevel, parentIndex int, isLeft, isRoot bool, tb [][]int) {
	if tb == nil {
		panic("")
	}
	if node == nil {
		return
	}
	currentLevel := parentLevel + 1
	var currentIndex = parentIndex + (levelCount - currentLevel)
	if isLeft {
		currentIndex = parentIndex - (levelCount - currentLevel)
	}
	if isRoot {
		currentLevel = 0
		currentIndex = len(tb[currentLevel]) / 2
	}
	tb[currentLevel][currentIndex] = node.key
	calNodePosition(node.left, levelCount, currentLevel, currentIndex, true, false, tb)
	calNodePosition(node.right, levelCount, currentLevel, currentIndex, false, false, tb)
}

package _case

import "fmt"

func BubbleSortCase() {
	arr := make([]int, len(IntArr))
	copy(arr, IntArr)
	fmt.Println(arr)
	bubbleSort(arr)
	fmt.Println(arr)
}

// 冒泡排序
// 从第一个元素开始向后遍历依次比较相邻两个元素的大小
// 如果前一个元素比后一个元素大，则交换位置
// 继续比较下一个相邻元素，直到最后一个元素
// 重复上述过程，但每次只需要比较到上一轮结束的位置
func bubbleSort(arr []int) {
	n := len(arr)
	for i := 0; i < n-1; i++ {
		flag := false // 看是否没有发生任何交换
		for j := 0; j < n-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				flag = true
			}
		}
		// 没有发生任何交换，本身就是有序的
		if !flag {
			break
		}
	}
}

package _case

import "fmt"

func SelectionSortCase() {
	arr := make([]int, len(IntArr))
	copy(arr, IntArr)
	fmt.Println(arr)
	selectionSort(arr)
	fmt.Println(arr)
}

// 选择排序
// 第一层循环，遍历切片，依次定义当前索引为最小值的索引
// 第二层循环，遍历剩余的元素，与最小值进行比较，如果当前值比最小值更小，则进行交换，每一轮可以得到一个最小值
func selectionSort(arr []int) {
	size := len(arr)
	for i := 0; i < size-1; i++ {
		minIndex := i
		for j := i + 1; j < size; j++ {
			if arr[j] < arr[minIndex] {
				minIndex = j
			}
		}
		if minIndex != i {
			arr[i], arr[minIndex] = arr[minIndex], arr[i]
		}
	}
}

package _case

import "fmt"

func InsertSortCase() {
	arr := make([]int, len(IntArr))
	copy(arr, IntArr)
	fmt.Println(arr)
	insertSort(arr)
	fmt.Println(arr)
}

// 插入排序
// 从第二个元素开始，依次遍历整个序列，保存当前位置得值到一个临时变量tmp
// 从当前位置开始，依次向前比较，若值大于tmp，则将该元素向后移动一个位置
// 如果值小于tmp，则将tmp的值插入到该值的后面一个位置
func insertSort(arr []int) {
	if len(arr) <= 1 {
		return
	}
	for i := 1; i < len(arr); i++ {
		tmp := arr[i]
		j := i - 1
		for j >= 0 && arr[j] > tmp {
			arr[j+1] = arr[j]
			j = j - 1
		}
		arr[j+1] = tmp
	}
}

package _case

import "fmt"

func QuickSortCase() {
	arr := make([]int, len(IntArr))
	copy(arr, IntArr)
	fmt.Println(arr)
	quickSort(arr, 0, len(arr)-1)
	fmt.Println(arr)
}

// 快速排序
// 取一个基准数，通常是头或者尾，本案例取末尾
// 遍历所有元素，与基准值做对比，小于基准值将元素依次放到序列指定位置i
// 遍历了一轮之后，将基准元素与i+1位置进行交换，形成以基准元素为分割的序列,之前小于基准，之后小于基准
// 返回当前基准元素的索引位置
func partition(arr []int, start, end int) int {
	pivot := arr[end]
	i := start - 1
	for j := start; j < end; j++ {
		if arr[j] < pivot {
			i++
			if i != j {
				arr[i], arr[j] = arr[j], arr[i]
			}
		}
	}
	arr[i+1], arr[end] = arr[end], arr[i+1]
	return i + 1
}

func quickSort(arr []int, start, end int) {
	if start < end {
		pivotIndex := partition(arr, start, end)
		fmt.Println(arr, pivotIndex)
		quickSort(arr, start, pivotIndex-1)
		quickSort(arr, pivotIndex+1, end)
	}
}

package _case

// 顺序查找（线性查找）
func sequentialSearch(arr []int, target int) int {
	for i := 0; i < len(arr); i++ {
		if arr[i] == target {
			return i
		}
	}
	return -1
}

package _case

import "fmt"

func BinarySearchCase() {
	var arr = []int{1, 3, 4, 5, 6, 8, 9, 10, 15, 17, 30}
	fmt.Println(binarySearch(arr, 5))
	fmt.Println(binarySearch(arr, 15))
	fmt.Println(binarySearch(arr, 25))
}

func binarySearch(arr []int, target int) int {
	start := 0
	end := len(arr) - 1
	for start <= end {
		mid := start + (end-start)/2
		if arr[mid] == target {
			return mid
		} else if arr[mid] > target {
			end = mid - 1
		} else {
			start = mid + 1
		}
	}
	return -1
}

package _case

import "fmt"

func HasnSearchCase() {
	um := NewUserMap()
	um.Insert(&User{ID: 1, Name: "Nick"})
	um.Insert(&User{ID: 3, Name: "Mac"})
	um.Insert(&User{ID: 4, Name: "Os"})
	um.Insert(&User{ID: 5, Name: "fbi"})
	um.Insert(&User{ID: 9, Name: "mlk"})
	fmt.Println(um.Search(1))
	fmt.Println(um.Search(2))
	fmt.Println(um.Search(4))
	fmt.Println(um.Search(5))
	fmt.Println(um.Search(8))
}
func HasnSearchCase1() {
	uht := NewUserHashTable()
	uht.Insert(&User{ID: 1, Name: "Nick"})
	uht.Insert(&User{ID: 13, Name: "Mac"})
	uht.Insert(&User{ID: 3, Name: "Os"})
	uht.Insert(&User{ID: 5, Name: "fbi"})
	uht.Insert(&User{ID: 9, Name: "mlk"})
	fmt.Println(uht.Search(1))
	fmt.Println(uht.Search(2))
	fmt.Println(uht.Search(4))
	fmt.Println(uht.Search(5))
	fmt.Println(uht.Search(8))
}

type UserMap map[int]*User // 实际应用要考虑锁

type User struct {
	ID   int
	Name string
}

func (u UserMap) Insert(user *User) {
	u[user.ID] = user
}

func (u UserMap) Search(id int) *User {
	user, ok := u[id]
	if !ok {
		return nil
	}
	return user
}

func NewUserMap() UserMap {
	return make(UserMap)
}

// 自己实现简单hashTable
type UserHashTable struct {
	data [][]*User
}

func NewUserHashTable() *UserHashTable {
	return &UserHashTable{
		data: make([][]*User, 10),
	}
}

func (user *User) Hash() int {
	return user.ID % 10
}

func (uht *UserHashTable) Insert(user *User) {
	index := user.Hash()
	uht.data[index] = append(uht.data[index], user)
}

func (uht *UserHashTable) Search(id int) *User {
	index := id % 10
	for _, user := range uht.data[index] {
		if user.ID == id {
			return user
		}
	}
	return nil
}