头图来源：无题-八伝-pixiv
优先队列
适用场景
优先队列能够快速获取队列中具有最优先级（如最小或最大）的元素，一般通过最小（或最大）堆来实现优先队列，堆顶元素就是优先队列中的队首元素。适用于每次拿取数据都需要从动态变化的数组中取出最小（或最大）的数。
时间复杂度
- 入队列：O(logn)
- 出队列：O(logn)
相关题目
实现
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)
相关题目
实现
一般二分查找分为以下几种：
- 标准的二分查找
- 二分查找左边界
- 二分查找右边界
标准二分查找
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;
}注：
left+((right-left)>>1)等价于(left+right)/2，改写的目的是为了防止left+right过大而产生溢出，采用位运算则是为了提升性能left+((right-left)>>1)对于奇数长度的目标数组而言位于正中间；对于偶数长度的目标数组则偏左边，因此当左右边界相遇时只会是以下两种情况：- left和mid相等，right比mid小1
- left、right和mid三数相等
二分查找左边界
左边界：不超过目标值的最大满足条件值（的下标）
适用场景
- 数组有序，但包含重复元素
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;
}注：
- 右边界的更新变成了
right=mid是因为再找到了目标值后还要继续向左查找左边界。 - 由于右边界的更新变成了
right=mid，因此需要将循环条件改为left<right，不然可能会进入死循环 - 在退出循环后，right、mid和left三值均相等。
二分查找右边界
和查找左边界同理，只要将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)
}