Golang算法

• ACM模式：fmt.Scan(&n) 只能往读入基本数据类型

	var n int
	var s string
	num, _ := fmt.Scan(&n, &s)
	if num == 0 {
		fmt.Println("没有元素")
	}else {
		fmt.Println("输入元素：",n,s)
	}

• 变量声明习惯
  – 无需初始化：var
  – 需要初始化：{}
  – 除基本变量 让其他声明都可为nil

• n,m = m,n

• math方法

绝对值：func Abs(x float64) float64
次方值：func Pow(x, y float64) float64
最大值：func Max(x, y float64) float64
最小值：func Min(x, y float64) float64

向下取整：func Floor(x float64) float64
向上取整：func Ceil(x float64) float64

最大整数：MaxInt64
最小整数：MinInt64

• 递归：存在子集同父集想到递归
• 返回所有可能：回溯算法
• 返回最大、最优… 最值：动态规划
• 但注意⚠️： 返回所有可能的确切值：回溯算法；返回所有可能的数量：动态规划！
• 注意：类似于二分法的这种指针在循环中的，要保证每次循环指针有移动，不然就有可能陷入死循环
• Go也支持位运算啊啊啊啊：mid := (right + left) >> 1
• Go引用函数只能使用匿名函数
• 换行才用,号！！！

	res := []int{3}

	res := []int{
		3,
	}

• 不要只使用基本数据类型啊！！！
  使用工具结构体实现高效读写：

	/ 高效读写byte流
	buf := bytes.Buffer{}
	buf.WriteByte('1')
	buf.WriteString("2")
	buf.Bytes()

	/ 高效读写字符串
	str := strings.Builder{}
	str.WriteByte('1')
	str.WriteString("2")
	str.String()

• 大哥 var 声明四大引用类型和指针为nil！ （切片、map、channel、接口）+ 指针
  会导致空指针：

	var m map[int]int
	m[0] = 0

• 10e3 ：10*10³
• 2³¹：1<<31
• 奇数：n&1 == 1 ；偶数：n&1 == 0
• string虽然不是基本数据类型，但底层是数组啊，string和[]byte和[]rune可以直接转换

a := []byte{}
b := string(a)
c := []rune(b)

• 数组，字符串是基本数据类型啊 赋值会拷贝
• 当出现点与点有向关联：画图 ⇒ 拓扑排序 【map存节点+入度】

func canFinish(numCourses int, prerequisites [][]int) bool {
    / topo[节点]入度
    topo := make(map[int]int,numCourses)
    。。。
    / 入度为0的节点存入stack
    stack := []int{}
    for i:=0;i
        if topo[i] == 0 {
            stack = append(stack,i)
        }
    }
    count := 0 / 也可以是[]res 返回拓扑过程
    for len(stack) > 0 {
        // 取出入度为0的节点
        zeroIndegree := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        count++
        // 将0度节点所指向的节点的入度减1
        for _,v := range prerequisites {
            if v[1] == zeroIndegree {
                topo[v[0]]--
                / 注意 ：直接在这里再获取入度为0的点
                if topo[v[0]] == 0 {
                    stack = append(stack,v[0])
                }
            }
        }
    }
    return count == numCourses
}

• 头节点前添加一个哨兵节点
• 双指针
• 排序：归并
• 快慢指针注意点
  1、使用fast.Next
  2、fast先传递

for fast.Next != nil {
     fast = fast.Next.Next
     if fast == nil {
         break
     }
     slow = slow.Next
 }

• 默认递增

import "sort"

/ int切片
func Ints(a []int)
/ float64切片
func Float64s(a []float64)
/ string切片
func Strings(a []string)

• 自定义排序（<升序 、 >降序）

    sss := [][]int{}
    
    / 根据二维数组第一个元素排序
    / 注意⚠️：i、j是下标
	sort.Slice(sss, func(i, j int) bool {
		return sss[i][0] < sss[j][0]
	})
	
	/ 稳定排序
	sort.SliceStable(...,...)

• 从1开始的数。。。关联数组下标。。。
• 双指针
• copy(dst, src []Type) int函数要初始化目标切片长度 不然将复制min(len(dst),len(src))个

	dst := make([]int,len(src))
	copy(dst,src)

• 前缀和：将遍历累加和存放到map中

• 按层遍历
• 递归YYDS：只思考第一步和第二步的关系 再加个递归终止条件就！！！

记住：

    for root != nil || len(stack) > 0 {
		for root != nil {
			......	
            stack = append(stack,root)
            root = root.Left
        }
        ......
   }

前序遍历

func preorderTraversal(root *TreeNode) []int {
    var res []int
    stack := []*TreeNode{}
    for root != nil || len(stack) > 0 {
        for root != nil {
            res = append(res,root.Val)
            stack = append(stack,root)
            root = root.Left
        }
        root = stack[len(stack)-1].Right
        stack = stack[:len(stack)-1]
    }
    return res
}

中序遍历

func inorderTraversal(root *TreeNode) []int {
    var res []int
    stack := []*TreeNode{}
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1].Right
		res = append(res, stack[len(stack)-1].Val)
        stack = stack[:len(stack)-1]
	}
	return res
}

后续遍历(多一个变量：上一个被记录的节点)

func postorderTraversal(root *TreeNode) []int {
    var res []int
    stack := []*TreeNode{}
    var pre *TreeNode //上一个被记录的元素
    for root != nil || len(stack) > 0 {
        for root != nil {
            stack = append(stack,root)
            root = root.Left
        }
        node := stack[len(stack)-1]
        if node.Right != nil && node.Right != pre {
            root = node.Right
        }else{
            res = append(res,node.Val)
            pre = node //该节点已被记录
            stack = stack[:len(stack)-1]
        }
    }
    return res
}

路径：在二叉树中走一条线 且每个节点只走一遍
124. 二叉树中最大路径和
543. 二叉树的直径

func diameterOfBinaryTree(root *TreeNode) int {
    // 全局遍历作为最终结果
    var res int
    // 求数深度函数
    var depth func(*TreeNode) int
    depth = func(node *TreeNode) int {
    	......
    	/ 递归求左右子树的深度
        leftDepth := depth(node.Left)
        rightDepth := depth(node.Right)
        
        ......
        将root + left + right 作为更新最终结果res的一种情况
		......
        / 而只将 root+left 和 root+right作为返回的结果
        return max(leftPath,rightPath)+1
    }
    depth(root)
    return res
}