help change the world

一、数论

GCD

package main
import "fmt"

func gcd(a ,b int) int {
    for {
        if b == 0 {
            return a
        }
        c := a%b
        a = b
        b = c
    }
}

func main () {
    fmt.Println(gcd(15, 12))
}

快速幂

package main
import "fmt"

func qpow(x, n int) int {
    if n == 0 {
        return 1
    }
    if n < 0 {
        x = 1 / x
        n = -1 * n
    }

    result := 1
    for {
        if n == 0 {
            break
        }
        if n&1 == 1 {
            result *= x
        }
        x *= x
        n >>= 1
    }

    return result
}

func main () {
    fmt.Println(qpow(2, 10))
}

素数线性筛

package main
import "fmt"

func findPrimes(n int) []int {
    var results []int
    isPrimeMap := make(map[int]bool)
    isPrimeMap[0], isPrimeMap[1] = false, false
    for i := 2; i<=n; i++ {
        if _, ok := isPrimeMap[i]; !ok{
            results = append(results, i)
        }
        for j:=i; j<=n; j+=i {
            isPrimeMap[j] = false
        }
    }
    return results
}

func main () {
    fmt.Println(findPrimes(100))
}

二、排序

冒泡排序

package main
import "fmt"

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func bubbleSort(a[]int) []int {
    n := len(a)
    for i:=n-1; i>=0; i-- {
        for j:=0; j<i; j++ {
            if a[i] < a[j] {
                a[i], a[j] = a[j], a[i]
            }
        }
    }
    return a
}

func main () {
    a := []int{1, 3, 2, 5, 3, 7, 4, 5}
    fmt.Println(bubbleSort(a))
}

快速排序

package main

import "fmt"

func quickSort(a []int, l int , r int) {
    if l >= r {
        return
    }
    x := a[l]
    i, j := l, r
    for i < j {
        for i<j && a[j]>=x {
            j-=1
        }
        if i < j {
            a[i] = a[j]
            i+=1
        }

        for i<j && a[i]<x {
            i+=1
        }
        if i < j {
            a[j] = a[i]
            j-=1
        }
    }
    a[i] = x
    quickSort(a, l, i-1)
    quickSort(a, i+1, r)
}

func main() {
    a := []int{5, 4, 3, 2, 1}
    quickSort(a,0, len(a)-1)
    fmt.Println(a)
    return
}

堆排序

四、数据结构

链表
队列


二叉树
拓扑排序
并查集
最小生成树
树状数组
Trie树

五、动态规划

01背包问题

package main
import "fmt"

type Bag struct {
    volume int
    value int
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func max_value(bags []*Bag ,capacity int) int {
    n := len(bags)
    var dp [100][100]int

    for i:= 1 ; i<n; i++ {
        for j:=0; j<=capacity; j++ {
            if j >= bags[i].volume {
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-bags[i].volume] + bags[i].value)
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }

    return dp[n-1][capacity]
}

func main () {
    bag1 := &Bag{1, 2}
    bag2 := &Bag{3, 4} 
    bag3 := &Bag{2, 3}

    bags := []*Bag{bag1, bag2, bag3}
    capacity := 5
    fmt.Println(max_value(bags, capacity))
}

最长递增子序列

package main
import "fmt"

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func lis(a[]int) int {
    var dp [101]int
    n := len(a)

    for i:=0; i<n; i++ {
        dp[i] = 1
        for j:=0; j<i; j++ {
            if a[i] > a[j] {
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
    }
    return dp[n-1]
}

func main () {
    a := []int{1, 3, 2, 5, 3, 7, 4, 5}
    fmt.Println(lis(a))
}

最长公共子序列

package main
import "fmt"

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func lcs(a, b []int) int {
    var dp [101][101]int
    n, m := len(a), len(b)

    for i:=1; i<=len(a); i++ {
        for j:=1; j<=len(b); j++ {
            if a[i-1] == b[j-1] {
                dp[i][j] = max(max(dp[i-1][j-1] + 1, dp[i-1][j]), dp[i][j-1])
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[n][m]
}

func main () {
    a := []int{1, 2, 3, 4, 5}
    b := []int{3, 4, 4, 4, 5}
    fmt.Println(lcs(a, b))
}

斐波那契

六、搜索

二分查找

package main
import "fmt"

func binarySearchIndex(arr []int, x int) int {
    st, ed := 0, len(arr)-1
    for st <= ed {
        mid := (st + ed)/2
        if arr[mid] == x {
            return mid
        }
        if arr[mid] > x {
            ed = mid-1
        } else {
            st = mid+1
        }
    }
    return -1
}

func main () {
    var arr = []int{1,2,3,4,6,7,8,9,10}
    x := 5
    fmt.Println(binarySearchIndex(arr, x))
}

BFS

DFS

七、图算法

最短路径
二分图