头图来源:无题-八伝-pixiv


优先队列

适用场景

优先队列能够快速获取队列中具有最优先级(如最小或最大)的元素,一般通过最小(或最大)堆来实现优先队列,堆顶元素就是优先队列中的队首元素。适用于每次拿取数据都需要从动态变化的数组中取出最小(或最大)的数。

时间复杂度

  • 入队列:O(logn)
  • 出队列:O(logn)

相关题目

  1. leetcode--407.接雨水 II
  2. leetcode--373.查找和最小的 K 对数字
  3. leetcode--786.第K个最小的素数分数

实现

Go中的heap包提供了堆的各种操作。由于Go非侵入式接口的特征,要使用heap来构建优先队列需要先实现heap包中规定的接口(Len(),Less()Swap())
示例

import (
    "container/heap"
    "fmt"
)

// IntHeap 是一个由整数组成的最小堆。
type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
//如果是最大堆,则是 return h[i]>h[j]
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
    // Push 和 Pop 使用 pointer receiver 作为参数,
    // 因为它们不仅会对切片的内容进行调整,还会修改切片的长度。
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    h := &IntHeap{2, 1, 5}
    heap.Init(h)
    heap.Push(h, 3)
    fmt.Printf("minimum: %d\n", (*h)[0])
    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h))
    }
}

二分查找

摘自【二分查找、二分边界查找算法的模板代码总结--思否】

适用场景

  • 待查找的数组是有序的

时间复杂度

  • O(logn)

相关题目

  1. leetcode--33.搜索旋转排序数组
  2. leetcode--4.寻找两个正序数组的中位数
  3. leetcode--162.寻找峰值

实现

一般二分查找分为以下几种:

  1. 标准的二分查找
  2. 二分查找左边界
  3. 二分查找右边界

标准二分查找

func BinSearch(nums []int,int target) int{
   left:=0
   right:=len(nums)-1
   for left<=right{
     mid:=left+((right-left)>>1)
     if nums[mid]==target{
        return mid
     }else if nums[mid]>target{
        right=mid-1
     }else{
        left=mid+1
     }
   }
   return -1;
}

注:

  1. left+((right-left)>>1)等价于(left+right)/2,改写的目的是为了防止left+right过大而产生溢出,采用位运算则是为了提升性能
  2. left+((right-left)>>1)对于奇数长度的目标数组而言位于正中间;对于偶数长度的目标数组则偏左边,因此当左右边界相遇时只会是以下两种情况:

    • leftmid相等,rightmid小1
    • leftrightmid三数相等

二分查找左边界

左边界:不超过目标值的最大满足条件值(的下标)

适用场景

  • 数组有序,但包含重复元素
func BinSearch(nums []int,int target) int{
   left:=0
   right:=len(nums)-1
   for left<right{
     mid:=left+((right-left)>>1)
     if nums[mid]<target{
        left=mid+1
     }else{
        right=mid
     }
   }
   return left;
}

注:

  1. 右边界的更新变成了right=mid是因为再找到了目标值后还要继续向左查找左边界。
  2. 由于右边界的更新变成了right=mid,因此需要将循环条件改为left<right,不然可能会进入死循环
  3. 在退出循环后,rightmidleft三值均相等。

二分查找右边界

和查找左边界同理,只要将left和right反过来就行了

注意此时的mid=left+((right-left)>>1)+1,因为整型除法向下取整的特性如果没有加1在某些情况下将会陷入死循环,非常危险

func BinSearch(nums []int,int target) int{
   left:=0
   right:=len(nums)-1
   for left<right{
     mid:=left+((right-left)>>1)+1
     if nums[mid]>target{
        right=mid-1
     }else{
        left=mid
     }
   }
   return left;
}

快速幂

通过位运算快速求一个数的幂次方。

时间复杂度

  • O(logn)

实现

func quickPow(x,n int)int{
    if x==0{
        return x;
    }
    res:=1
    for n>0{
        if n&1==1{
            res*=x
        }
        x*=x 
        n>>=1
    }
    return res
}

最短路径

狄杰斯特拉

狄杰斯特拉(Dijkstra)算法运用了贪心的策略,计算一个顶点到其余各定点的最短路径,可用于解决无负权图中的最短路径问题。

时间复杂度

  • O(v^2) (v为顶点个数)

实现

代码来源于求图中两点最短路径(dijkstra) go实现,稍作修改

type Dijkstra struct {
    Visit bool   // 表示是否访问
    Val   int    // 表示距离
    Pathfrom  int // 路径的显示
}

const (
    INT_MAX = 2<<31 - 1
)

func getShortPathByDijkstra(begin int, vertex [][]int) []Dijkstra {
    if 0 == len(vertex) || 0 == len(vertex[0]) || len(vertex) != len(vertex[0]) {
        return []Dijkstra{}
    }
    d := make([]Dijkstra, len(vertex))

    for i := 0; i < len(vertex); i++ {
        d[i].Visit = false
        d[i].Val = vertex[begin][i]
        d[i].Pathfrom = begin
    }

    d[begin].Visit = true
    d[begin].Val = 0
    count := 1
    for count < len(vertex) { // 从源点到目的点依次加入最短路径节点进去
        min := INT_MAX
        temp := 0
        for i := 0; i < len(vertex); i++ { // 从还没到过的点中取出最小点并开始新一轮的更新
            if !d[i].Visit && d[i].Val < min {
                min = d[i].Val
                temp = i
            }
        }
        d[temp].Visit = true
        for i := 0; i < len(vertex); i++ { // 进行松弛,即更新源点到各节点的最短路径
            if !d[i].Visit && vertex[temp][i] != INT_MAX && d[temp].Val + vertex[temp][i] < d[i].Val {
                d[i].Val = d[temp].Val + vertex[temp][i]
                d[i].Pathfrom = temp
            }
        }
        count ++
    }
    return d
}

func path(d []Dijkstra,dest int)[]int{
    if dest==d[dest].Pathfrom{
        fmt.Println(dest)
        return []int{dest}
    }
    return append(path(d,d[dest].Pathfrom),dest)
}

链表反转

type ListNode struct {
    Val  int
    Next *ListNode
}

func reverse(head *ListNode,tail *ListNode)*ListNode{
    prev:=tail.Next
    p:=head
    for p!=nil{
        next:=p.Next
        p.Next=prev
        prev=p
        p=next
    }
    return tail
}

func reverseList(head *ListNode) *ListNode {
    tail:=head
    if tail==nil{
        return tail
    }
    for tail.Next!=nil{
        tail=tail.Next
    }
    return reverse(head,tail)
}

前缀树(字典树)

排序

最后修改:2022 年 06 月 21 日 05 : 46 PM
如果觉得我的文章对你有用,请随意赞赏