剑指offer算法—Go实现

简介

最近在准备面试，发现一个不错的网站推荐给大家。也希望通过Go实现来把里面 剑指offer算法 的题做一下。
如果觉得帮到了你，希望能为我点个赞呀。
如果发现代码有错，非常希望您能够在留言中指出。
https://github.com/CyC2018/CS…
文章只贴自己写的代码，题目的所有内容和解题思路都在上面的网站里。
一些比较简单无聊的题，就跳过。。

未完待续。

归并排序，快排，堆排序

这一节不出现在剑指offer里边，但是经常面试问到。
1.归并排序

package main

import (
    "math/rand"
    "time"
)

// 产生n个随机数
func CreateList(list []int, n int) []int {
    s1 := rand.NewSource(time.Now().Unix())
    r1 := rand.New(s1)
    for i := 0; i < n; i++ {
        list = append(list, r1.Intn(100))
    }
    return list
}

func Merge(list []int, a, b int) {
    var (
        i, j int
        mid  int
        pos  int
    )

    temp := make([]int, len(list))
    copy(temp, list)
    i = a
    mid = (a + b) / 2
    j = mid + 1
    pos = a
    for i <= mid && j <= b {
        if temp[i] < temp[j] {
            list[pos] = temp[i]
            pos++
            i++
        } else {
            list[pos] = temp[j]
            pos++
            j++
        }
    }
    for i <= mid {
        list[pos] = temp[i]
        pos++
        i++
    }
    for j <= b {
        list[pos] = temp[j]
        pos++
        j++
    }
}

// 左闭右闭[a,b]
func MergeSort(list []int, a, b int) {
    if a+1 >= b {
        if list[a] > list[b] {
            list[a], list[b] = list[b], list[a]
        }
        return
    }
    // 排序包括下标(a+b)/2的值
    MergeSort(list, a, (a+b)/2)

    MergeSort(list, (a+b)/2+1, b)

    Merge(list, a, b)
}

func main() {
    // var inputList = []int{5, 3, 8, 22, 76, 1, 31, 55}
    var inputList = []int{}
    inputList = CreateList(inputList, 10)

    MergeSort(inputList, 0, len(inputList)-1)
    fmt.Println(inputList)
}

2.快排

// 左闭右闭[a,b]
func QuickSort(list []int) {
    var (
        midValue   int
        head, tail int
    )
    if len(list) <= 1 {
        return
    }
    head = 1
    midValue = list[0]
    tail = len(list) - 1
    for head < tail {
        for list[head] < midValue {
            head++
            if head >= tail {
                goto END
            }
        }
        for list[tail] > midValue {
            tail--
            if head >= tail {
                goto END
            }
        }
        list[head], list[tail] = list[tail], list[head]
        head++
        tail--
    }
END:
    if list[head] > midValue {
        list[0], list[head-1] = list[head-1], list[0]

        QuickSort(list[0 : head-1])
        QuickSort(list[head:])
    } else {
        list[0], list[head] = list[head], list[0]

        QuickSort(list[0:head])
        QuickSort(list[head+1:])
    }
}

3.堆排序
推荐文章：
https://www.cnblogs.com/cheng…
https://blog.csdn.net/MoreWin…

// i为处理节点,其是从孩子节点向下影响堆。
// n为堆的节点数
// 其存在一个前提假设，就是两个孩子都已经是大顶堆
func MaxHeapFixDown(list []int, i int, n int) {
    var (
        parent int
        kid    int
    )
    parent = i
    // (i+1)*2 和 (i+1)*2 -1 ：为孩子节点
    kid = (i+1)*2 - 1
    for kid < n {
        // 取孩子最大的一个
        if kid+1 < n && list[kid+1] > list[kid] {
            kid++
        }
        // 最大的孩子和父亲比较
        if list[parent] < list[kid] {
            // 如果孩子大，则交换
            list[parent], list[kid] = list[kid], list[parent]
            // 父亲,孩子换人
            parent = kid
            kid = (parent+1)*2 - 1
            continue
        } else {
            // 如果父亲大，则退出，主要是假设在两个子树本来都是大顶堆
            return
        }
    }
}

// 大顶堆生成
func CreateMaxHeap(list []int) {
    // 从最小的非叶子节点开始生成。
    // 这样就会一直处在 两个孩子都已经是大顶堆 的前提
    // n := (len(list) - 1) / 2
    for n := (len(list) - 1) / 2; n >= 0; n-- {
        MaxHeapFixDown(list, n, len(list))
    }
}

// 从小到大排序
func HeapSort(list []int) {

    //1.大顶堆生成
    CreateMaxHeap(list)
    // 根与最后一个交换,此时我们概念中的堆的大小将减一
    // 也就是少一个节点不在大顶堆的范围内
    for n := len(list) - 1; n > 0; n-- {
        list[0], list[n] = list[n], list[0]
        // 因为动了根节点，对根节点进行处理
        MaxHeapFixDown(list, 0, n-1)
    }

}
func main() {
    var inputList = []int{5, 3, 8, 22, 76, 1, 31, 55}
    // var inputList = []int{}
    // inputList = CreateList(inputList, 10)

    HeapSort(inputList)
    fmt.Println(inputList)
}

红黑树

推荐文章：
https://zhuanlan.zhihu.com/p/…
https://blog.csdn.net/v_JULY_…
性质

1. 每个结点要么是红的要么是黑的。
2. 根结点是黑的。
3. 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
4. 如果一个结点是红的，那么它的两个儿子都是黑的。
5. 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

题目3-9

3.数组中重复的数字

// 数组中重复的数字
func topic3() {
    // 交换函数
    swap := func(list []int, i, j int) {
        list[i], list[j] = list[j], list[i]
    }

    input := []int{2, 3, 1, 0, 2, 5}
    for i := 0; i < len(input); i++ {
        // 将转换后
        for i != input[i] {

            // i要换到input[i]的位置，但是如果input[i]位置的值（intput[input[i]]）等与input[i]，说明重复来了
            if input[i] == input[input[i]] {
                fmt.Println(input[i], "重复")
                goto END
            }
            swap(input, i, input[i])
        }
    }
END:
    fmt.Println("done")
}

4.二维数组中的查找

// 我自己最初想到的方法
// 时间消费在算等差值d这个数组(这里懒得写)，以及下面的关于row的循环
func topic4() {
    list := [5][5]int{
        {1, 4, 7, 11, 15},
        {2, 5, 8, 12, 19},
        {3, 6, 9, 16, 22},
        {10, 13, 14, 17, 24},
        {18, 21, 23, 26, 30},
    }
    // 等差值,都为3只是特殊
    d := [5]int{3, 3, 3, 3, 3}

    // 行列数
    col := 5
    row := 5
    var input int
    fmt.Scanf("%d", &input)

    for i := 0; i < row; i++ {
        if input > list[i][col-1] || input < list[i][0] {
            // 比该行最大还大或者比最小的还小，下一行
            continue
        } else {
            if (input-list[i][0])%d[i] == 0 {
                fmt.Println("true")
                goto DONE
            }
            continue
        }
    }
    fmt.Println("false")
DONE:
    fmt.Println("done")
}

7.重建二叉树

type treeNode struct {
    value int
    left  *treeNode
    right *treeNode
}

func CreateTree(preorder, inorder []int) (ptNode *treeNode) {

    var (
        leftChiledSize int
    )

    if len(preorder) != len(inorder) {
        fmt.Println("error")
        // debug
        panic("err1")
    }
    ptNode = &treeNode{
        left:  nil,
        right: nil,
        value: preorder[0],
    }
    // 递归退出条件
    if len(preorder) == 1 {
        return ptNode
    }

    leftChiledSize = GetLeftChiledSize(preorder[0], inorder)
    ptNode.left = CreateTree(preorder[1:1+leftChiledSize], inorder[0:leftChiledSize])
    ptNode.right = CreateTree(preorder[1+leftChiledSize:], inorder[leftChiledSize+1:])
    return ptNode
}

//获取左子树节点数
func GetLeftChiledSize(root int, inorder []int) int {
    for i := 0; i < len(inorder); i++ {
        if root == inorder[i] {
            return i
        }
    }
    // debug
    panic("err2")
}

// 后续遍历
func PostOrderTraversal(ptree *treeNode) {
    if ptree.left == nil && ptree.right == nil {
        fmt.Println(ptree.value)
        return
    }

    if ptree.left != nil {
        PostOrderTraversal(ptree.left)
    }
    if ptree.right != nil {
        PostOrderTraversal(ptree.right)
    }
    fmt.Println(ptree.value)
}

func topic7() {
    preorder := []int{3, 9, 20, 15, 7}
    inorder := []int{9, 3, 15, 20, 7}
    treeRoot := CreateTree(preorder, inorder)
    PostOrderTraversal(treeRoot)
}

8.二叉树的下一个结点

type treeNode struct {
    value  int
    parent *treeNode
    left   *treeNode
    right  *treeNode
}

func CreateTree(preorder, inorder []int) (ptNode *treeNode) {

    var (
        leftChiledSize int
    )

    if len(preorder) != len(inorder) {
        fmt.Println("error")
        // debug
        panic("err1")
    }
    ptNode = &treeNode{
        parent: nil,
        left:   nil,
        right:  nil,
        value:  preorder[0],
    }
    // 递归退出条件
    if len(preorder) == 1 {
        return ptNode
    }

    leftChiledSize = GetLeftChiledSize(preorder[0], inorder)
    ptNode.left = CreateTree(preorder[1:1+leftChiledSize], inorder[0:leftChiledSize])
    ptNode.left.parent = ptNode
    ptNode.right = CreateTree(preorder[1+leftChiledSize:], inorder[leftChiledSize+1:])
    ptNode.right.parent = ptNode
    return ptNode
}

func GetLeftChiledSize(root int, inorder []int) int {
    for i := 0; i < len(inorder); i++ {
        if root == inorder[i] {
            return i
        }
    }
    // debug
    panic("err2")
}

// 前序遍历获取节点
func PreOrderGetNode(ptree *treeNode, target int) (res *treeNode) {
    if ptree.value == target {
        return ptree
    }
    if ptree.left != nil {
        if res = PreOrderGetNode(ptree.left, target); res != nil {
            return res
        }
    }
    if ptree.right != nil {
        if res = PreOrderGetNode(ptree.right, target); res != nil {
            return res
        }
    }

    // debug
    // fmt.Println("can not find")

    return nil
}

//获取中序遍历下的下一个节点
func InOrderNext(pt *treeNode) (res *treeNode) {
    // 有右子树 -> 取右树最左节点
    if pt.right != nil {
        circle := pt.right
        for circle.left != nil {
            circle = circle.left
        }
        return circle
    }
    // 无右子树 -> 向上找第一个左链接指向的树包含该节点的祖先节点。
    circle := pt
    for circle.parent != nil {
        if circle.parent.left == circle {
            return circle.parent
        }
        circle = circle.parent
    }

    // debug
    fmt.Println("cannot find")

    return nil
}

func topic8() {
    preorder := []int{3, 9, 20, 15, 7}
    inorder := []int{9, 3, 15, 20, 7}
    // 生成树
    rootTree := CreateTree(preorder, inorder)

    // 前序遍历获取值为15的节点
    target := PreOrderGetNode(rootTree, 7)

    res := InOrderNext(target)
    if res == nil {
        fmt.Println("没有下一个节点")
    } else {
        fmt.Println(res.value)
    }
}