golang代码积累

连接字符串

  • str1+str2

  • fmt.Sprintf(“%s%s”,str1,str2)

  • strings.Builder

1
2
3
4
5
6
7
8
9
10
11
12
13
str1 := "str1"
str2 := "str2"

fmt.Println(str1 + str2)

fmt.Println(fmt.Sprintf("%s%s", str1, str2))

var stringbuilder strings.Builder
stringbuilder.WriteString(str1)

stringbuilder.WriteString(str2)

fmt.Println(stringbuilder.String())

Stack

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package main

import "fmt"

type Stack struct {
	items []interface{}
}

func (s *Stack) Push(item interface{}) {
	s.items = append(s.items, item)
}

func (s *Stack) Pop() interface{} {
	if len(s.items) == 0 {
		return nil
	}
	item := s.items[len(s.items)-1]
	s.items = s.items[:len(s.items)-1]
	return item
}

func (s *Stack) Peek() interface{} {
	if len(s.items) == 0 {
		return nil
	}
	return s.items[len(s.items)-1]
}

func (s *Stack) IsEmpty() bool {
	return len(s.items) == 0
}

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

func main() {
	stack := Stack{}

	stack.Push(1)
	stack.Push(2)
	stack.Push(3)

	fmt.Println("Stack:", stack.items)
	fmt.Println("Top:", stack.Peek())
	fmt.Println("Pop:", stack.Pop())
	fmt.Println("Stack:", stack.items)
	fmt.Println("Is Empty?", stack.IsEmpty())
	fmt.Println("Size:", stack.Size())
}

Queue

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package main

import "fmt"

type Queue struct {
	items []interface{}
}

func (q *Queue) Enqueue(item interface{}) {
	q.items = append(q.items, item)
}

func (q *Queue) Dequeue() interface{} {
	if len(q.items) == 0 {
		return nil
	}
	front := q.items[0]
	q.items = q.items[1:]
	return front
}

func (q *Queue) Front() interface{} {
	if len(q.items) == 0 {
		return nil
	}
	return q.items[0]
}

func (q *Queue) IsEmpty() bool {
	return len(q.items) == 0
}

func (q *Queue) Size() int {
	return len(q.items)
}

func main() {
	queue := Queue{}

	queue.Enqueue(1)
	queue.Enqueue(2)
	queue.Enqueue(3)

	fmt.Println("Queue:", queue.items)
	fmt.Println("Front:", queue.Front())
	fmt.Println("Dequeue:", queue.Dequeue())
	fmt.Println("Queue:", queue.items)
	fmt.Println("Is Empty?", queue.IsEmpty())
	fmt.Println("Size:", queue.Size())
}

Priority Queue

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
package main

import (
	"container/heap"
	"fmt"
)

type Item struct {
	value    string
	priority int
}
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int {
	return len(pq)
}
// < 表示最小堆 返回堆顶，即priority最小的值
func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(*Item)
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func main() {
	pq := make(PriorityQueue, 0)

	heap.Init(&pq)
	items := []*Item{
		{
			value:    "C",
			priority: 3,
		},
		{
			value:    "A",
			priority: 1,
		},
		{
			value:    "B",
			priority: 2,
		},
	}
	for _, item := range items {
		heap.Push(&pq, item)
	}

	for pq.Len() > 0 {
		item := heap.Pop(&pq).(*Item)
		fmt.Printf("%s( Priority:%d)", item.value, item.priority)
	}
}

层次遍历

1
2
3
4
5
6
7
8
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

version 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 func levelOrder(root *TreeNode)(res []int){
    if root==nil{
        return nil
    }
    cur:=make([]*TreeNode,0)
    cur=append(cur,root)
    for len(cur)>0{
        nodes:=make([]*TreeNode,0)
        for _,node:=range cur{
            res=append(res,node.Val)
            if node.Left!=nil{
                nodes=append(nodes,node.Left)
            }
            if node.Right!=nil{
                nodes=append(nodes,node.Right)
            }
        }
        cur=nodes
    }
    return
}

version 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func levelOrder(root *TreeNode)(res [][]int){
    if root==nil{
        return nil
    }
    cur:=make([]*TreeNode,0)
    //将首元节点插入
    cur=append(cur,root)
    for len(cur)>0{
        tempRes:=make([]int,0)
        nodes:=make([]*TreeNode,0)
        for _,node:=range cur{
            tempRes=append(tempRes,node.Val)
            if node.Left!=nil{
                nodes=append(nodes,node.Left)
            }
            if node.Right!=nil{
                nodes=append(nodes,node.Right)
            }
        }
        res=append(res,tempRes)
        cur=nodes
    }
    return
}

version 3

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
func levelOrder(root *TreeNode) (res [][]int) {
	if root == nil {
		return [][]int{}
	}
	cur := make([]*TreeNode,0)
	cur=append(cur,root)
	cnt := 1
	for len(cur) > 0 {
		arr := make([]int, 0)
		nodes := make([]*TreeNode, 0)
		for _, node := range cur {
			if node.Left != nil {
				nodes = append(nodes, node.Left)
			}
			if node.Right != nil {
				nodes = append(nodes, node.Right)
			}
			arr = append(arr, node.Val)
		}
		if cnt==-1{
			for i,Len:=0,len(arr);i<len(arr)/2;i++{
				arr[Len-1-i],arr[i]=arr[i],arr[Len-1-i]
			}
		}
		cnt*=-1
		res=append(res,arr)
		cur = nodes
	}
	return res
}

检查是否为二叉搜索树

二叉树的中序遍历

version 1 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func inorderTraversal(root *TreeNode) (res []int) {
	//边界条件
	//自定义函数
    re := func(root *TreeNode) {}
	re = func(root *TreeNode) {
		if root == nil {
			return
		}
		if root.Left != nil {
			re(root.Left)
		}
		res = append(res, root.Val)
		if root.Right != nil {
			re(root.Right)
		}
	}
	re(root)
	return
}

version 2 迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func isValidBST(root *TreeNode)bool{
    stack:=make([]*TreeNode,0)
    inorder:=math.MinInt64
    for len(stack)>0||root!=nil{
        for root!=nil{
            stack=append(stack,root)
            root=root.Left
        }
        root=stack[len(stack)-1]
        stack=stack[:len(stack)-1]
        if root.Val<=inorder{
            return false
        }
        inorder=root.Val
        root=root.Right
    }
    return true
}

计算二叉树的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

func maxDepth(root *TreeNode)int{
    var dfs func(root *TreeNode)int
    dfs=func(root *TreeNode)int{
        if root==nil{
            return 0
        }
        return max(dfs(root.Left),dfs(root.Right))+1
    }
    return dfs(root)
}

平衡二叉树的判断

平衡二叉树中的每一个节点的左右子树的高度差不超过2

思路：在每一个节点求得其左右子树的高度，判断是否符合平衡二叉树的要求

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
func max(a,b int)int{
	if a>b{
		return a
	}
	return b
}

func getDepth(root *TreeNode)int{
	if root==nil{
		return 0
	}
	return max(getDepth(root.Left),getDepth(root.Right))+1
}
func abs(a,b int)int{
	if a>b{
		return a-b
	}
	return b-a
}
func isBalanced(root *TreeNode)bool{
	if root==nil{
		return true
	}
	return isBalanced(root.Left)&&
		isBalanced(root.Right)&&abs(getDepth(root.Left),getDepth(root.Right))<2
}

二叉搜索树与双向链表

要求：不创建任何新的节点，只能调整树中节点指针的指向,最终形成一个有序的双向链表，返回头结点

思路：因为用中序遍历二叉搜索树，得到的是一个从小到大的有序结果，所以我们可以利用中序遍历的特性，在其中把节点与节点连接起来，最终就可以得到一个有序双向链表

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
class Solution {
public:
    Node* head=nullptr;
    Node *prev=nullptr;
    void dfs(Node* cur){
       if(cur==NULL){
           return ;
       }
        dfs(cur->left);
        //找到tree中最小值
        if (head==NULL){
            head=cur;
            prev=cur;
        }else{
            //找到较小值
            prev->right=cur;
            cur->left=prev;
            prev=cur;
        }
        dfs(cur->right);
    }
    Node* treeToDoublyList(Node* root) {
        if (root==NULL){
            return NULL;
        }
        dfs(root);
        //双向链表收尾相连
        prev->right=head;
        head->left=prev;
        return head;
    }
};

重构二叉树

根据前序遍历和中序遍历重构 得到后序遍历

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

func buildTree(pr []int, in []int) (head *TreeNode) {
	var dfs func(pr []int, in []int, l0 int, r0 int, l1 int, r1 int) *TreeNode
	// 用map来快速得到中序遍历中pr[l0]的位置
    pos := map[int]int{}
	for idx, v := range in {
		pos[v] = idx
	}
	dfs = func(pr []int, in []int, l0 int, r0 int, l1 int, r1 int) *TreeNode {
		if l0 > r0 {
			return nil
		}

		root := &TreeNode{Val: pr[l0]}
		idx := pos[pr[l0]]
		lsize := idx - l1
		//rsize:=r1-idx
		// [l0+1,lsize+l0] [lsize+l0+1,r0]
		// [l1,idx-1] [addr+1,r1]

		root.Left = dfs(pr, in, l0+1, lsize+l0, l1, idx-1)
		root.Right = dfs(pr, in, lsize+l0+1, r0, idx+1, r1)
		return root
	}

	return dfs(pr, in, 0, len(pr)-1, 0, len(in)-1)
}

二叉搜索树的后序遍历

后序遍历中的最后一个结果是该遍历结果的根节点，可以从头遍历 遍历结果，查看小于根节点的元素，再往后遍历大于根节点的元素，如果其中有比根节点小的元素，则此二叉树不是二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func verifyPostorder(postorder []int) bool {
	var dfs func(arr []int, l, r int) bool

	dfs = func(arr []int, l, r int) bool {
		if r <= l {
			return true
		}
		mid:=arr[r]
		var p int=l
		for arr[p]<mid{
			p++
		}
		
		var idx int=p
		for arr[p]>mid{
			p++
		}
		return p==r&&dfs(arr,l,idx-1)&&dfs(arr,idx,r-1)
	}
	return dfs(postorder, 0, len(postorder)-1)
}

lowerbit的求法

lowerbit=n&(-n)

1
2
3
4
5
6
7
8
9
//快速求得一个数在二进制中每一个1所在位置代表的值大小
func hammingWeight(num uint32) (cnt int) {
	for num > 0 {
		lowbit := num & (-num)
		num -= lowbit
		cnt++
	}
	return
}

位运算专题

抑或的用法

1
2
3
4
5
6
7
8
9
10
11
12
13
# 其中抑或相当于一个不会进位的加法
1^1=0
0^1=1
0^0=0

#两个相同的数向抑或，结果为0
#一个数与0向抑或的结果是原数
a^a=0
0^a=a

a^b=c
c^a=b
b^c=a

1442. 形成两个异或相等数组的三元组数目 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//leetcode 1442
//
func countTriplets(arr []int) (cnt int) {
	n := len(arr)
	orres := make([]int, n+1)

	orres[0] = 0
	for idx, v := range arr {
		orres[idx+1] = orres[idx] ^ v
	}

	for i := 1; i <= n; i++ {
		for j := i + 1; j <=n && i < j; j++ {
			if orres[j]^orres[i-1] == 0 {
				//i j 可以
				cnt += j - i 
			}
		}
	}
	return
}

421. 数组中两个数的最大异或值 - 力扣（LeetCode）

构造 字典树 快速知晓数组中的其他数字的每一位的bit的大小，利用贪心，1^0=1

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

func max(a,b int)int{
	if a>b{
		return a
	}	
	return b
}

const heightbit=30

type trie struct {
	left,right *trie	
}

func (t *trie) add(num int){
	cur:=t
	for i:=heightbit;i>=0;i--{
		bit:=(num>>i)&1
		if bit==0{
			if cur.left==nil{
				cur.left=&trie{}
                cur=cur.left
			}else{
				cur=cur.left	
			}
		}else{
			if cur.right==nil{
				cur.right=&trie{}
                cur=cur.right
			}else{
				cur=cur.right
			}
		}
	}
	return
}

func (t *trie)check(num int)(res int){
	cur:=t
	for i:=heightbit;i>=0;i--{
		b:=(num>>i)&1
		if b==0{
			//需要1
			if cur.right!=nil{
				res|=(1<<i)
                cur=cur.right
            }else{
                cur=cur.left
            }
		}else{
			//需要0
			if cur.left!=nil{
				res|=(1<<i)
                cur=cur.left
            }else{
                cur=cur.right
            }
		}
	}
	return 
}

func findMaximumXOR(nums []int) (x int) {
	root := *&trie{}
	for i:=1;i<len(nums);i++{
		root.add(nums[i-1])
		x = max(x, root.check(nums[i]))
	}
	return
}
golang代码积累
http://example.com/2023/09/13/golang代码积累/
作者
Forrest
发布于
2023年9月13日
许可协议