剑指offer算法—Go实现

简介

最近在准备面试，发现一个不错的网站推荐给大家。也希望通过Go实现来把里面 剑指offer算法
。
如果觉得帮到了你，希望能为我点个赞呀。
如果发现代码有错，非常希望您能够在留言中指出。

https://github.com/CyC2018/CS…

文章只贴自己写的代码，题目的所有内容和解题思路都在上面的网站里。
一些比较简单无聊的题，就跳过。。

未完待续。

题目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)
    }
}