剑指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指针的每条路径都包含相同数目的黑结点。

clipboard.png

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

本文来自:Segmentfault

感谢作者:l1nkkk

查看原文:剑指offer算法---Go实现

• 编辑
• 预览