help change the world

Algorithm Manual - analysis in Go

目录

[TOC]


第一章 数论

1.1 GCD

1.1 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))
}

1.2 快速幂

1.2 快速幂

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

1.3 素数线性筛

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

1.4 概率期望

第二章 排序

2.1 冒泡排序

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

2.2 快速排序

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
}

2.3 堆排序

package main

import "fmt"

type Heap struct {
    nums [1000010]int
    maxIdx int
}

func(this *Heap) Init(nums []int) {
    this.maxIdx = -1
    for i := 0; i < len(nums); i++ {
        this.Add(nums[i])
    }
}

func(this *Heap) Add(num int) {
    this.maxIdx += 1
    i := this.maxIdx
    this.nums[i] = num

    j := (i-1)/2

    for j >= 0 && i != 0 {
        if this.nums[j] <= num {
            break
        }
        this.nums[i] = this.nums[j]
        i = j
        j = (i-1)/2
    }
    this.nums[i] = num
}

func(this *Heap) Delete() int {
    res := this.nums[0]
    this.nums[0] = this.nums[this.maxIdx]
    this.maxIdx = this.maxIdx - 1

    tmp := this.nums[0]

    i := 0
    j := i * 2 + 1

    for j <= this.maxIdx {
        if j + 1 <= this.maxIdx && this.nums[j+1] < this.nums[j] {
            j += 1
        }
        if this.nums[j] >= tmp {
            break
        }
        this.nums[i] = this.nums[j]
        i = j
        j = i * 2 + 1
    }
    this.nums[i] = tmp
    return res
}

func main() {
    nums := []int{1,3,5,7,2,4,6,8}
    var heap Heap
    heap.Init(nums)

    fmt.Println(heap.nums[:len(nums)])

    for heap.maxIdx >= 0 {
        fmt.Println(heap.Delete())
    }
}
/*
[1 2 4 7 3 5 6 8]
1
2
3
4
5
6
7
8
*/

第三章 数据结构

3.1 链表

链表结构

 type ListNode struct {
     Val int
     Next *ListNode
 }

求单链表中结点的个数

fun GetListLen(head *ListNode) int {
    var result 0
    for {
        if head == nil {
            break
        }
        head = head.Next
        result += 1
    }
    return result
}

将单链表反转

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    next := head.Next    
    head.Next = nil

    for {
        if next.Next == nil {
            break
        }
        nextNext := next.Next

        next.Next = head
        head = next
        next = nextNext
    }
    next.Next = head

    return next
}

查找单链表中的倒数第K个结点(k > 0)

func getKthFromEnd(head *ListNode, k int) *ListNode {
    nodek := head
    for {
        if k == 0 {
            break
        }
        head = head.Next
        k -= 1
    }
    for {
        if head == nil {
            break
        }
        head = head.Next
        nodek = nodek.Next
    }
    return nodek
}

查找单链表的中间结点

func getMiddleNode(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    faster := head
    for {
        if faster == nil || faster.Next == nil {
            break
        }
        head = head.Next
        faster = faster.Next
        if faster !=nil && faster.Next != nil {
            faster = faster.Next
        }
    }
    return head
}

从尾到头打印单链表

从尾到头打印单链表

func reversePrint(head *ListNode) []int {
    var arr, result []int
    if head == nil {
        return result
    }

    for {
        now := head.Val
        arr = append(arr, now)
        head = head.Next
        if head == nil {
            break
        }
    }

    for i:=len(arr)-1; i>=0; i-- {
        result = append(result, arr[i])
    }
    return result
}

合并两个排序的链表

合并两个排序的链表

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }
    var result *ListNode 
    if l1.Val < l2.Val {
        result = l1
        result.Next = mergeTwoLists(l1.Next, l2)
    } else {
        result = l2
        result.Next = mergeTwoLists(l1, l2.Next)
    }
    return result
}

判断一个单链表中是否有环

判断一个单链表中是否有环

func hasCycle(head *ListNode) bool {
    if head == nil {
        return false
    }

    faster := head
    for {
        if faster == nil || faster.Next == nil {
            return false
        }
        faster = faster.Next.Next
        if head.Next == nil {
            return false
        }
        head = head.Next
        if faster == head {
            return true
        }
    }
    return false
}

两个单链表相交的第一个节点

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }

    a, b := headA, headB
    len_a, len_b := 1, 1
    for {
        if a.Next == nil {
            break
        }
        len_a += 1
        a = a.Next
    }
    for {
        if b.Next == nil {
            break
        }
        len_b += 1
        b = b.Next
    }
    if a != b {
        return nil
    }

    if len_a > len_b {
        count := len_a - len_b
        for count > 0 {
            count -= 1
            headA = headA.Next
        }
    } else if len_a < len_b {
         count := len_b - len_a
        for count > 0 {
            count -= 1
            headB = headB.Next
        }
    }

    for {
        if headA == headB {
            return headA
        }
        headA = headA.Next
        headB = headB.Next
    }
    return nil
}

已知单链表中存在环,求进入环中第一个节点

func detectCycle(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    origin := head

    faster := head
    for {
        if faster == nil || faster.Next == nil {
            return nil
        }
        faster = faster.Next.Next
        if head.Next == nil {
            return nil
        }
        head = head.Next
        if faster == head {
            break
        }
    }

    headA, headB := origin, faster

    a, b := headA, headB
    len_a, len_b := 1, 1
    for {
        if a.Next == headB {
            break
        }
        len_a += 1
        a = a.Next
    }
    for {
        if b.Next == headB {
            break
        }
        len_b += 1
        b = b.Next
    }


    if len_a > len_b {
        count := len_a - len_b
        for count > 0 {
            count -= 1
            headA = headA.Next
        }
    } else if len_a < len_b {
         count := len_b - len_a
        for count > 0 {
            count -= 1
            headB = headB.Next
        }
    }

    for {
        if headA == headB {
            return headA
        }
        headA = headA.Next
        headB = headB.Next
    }

    return nil
}

删除链表的节点

删除链表的节点

func deleteNode(head *ListNode, val int) *ListNode {
    if head == nil {
        return head
    }
    if head.Val == val {
        return head.Next
    }
    if head.Next != nil && head.Next.Val == val {
        head.Next = head.Next.Next
    }

    deleteNode(head.Next, val)

    return head
}

3.2 堆

3.3 二叉树

二叉树结构

// Definition for a binary tree node.
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
 }

二叉搜索树的最近公共祖先

二叉搜索树的最近公共祖先

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL || p == root || q == root) return root;

    if ((p->val < root->val && q->val > root->val) || (p->val > root->val && q->val < root->val)) 
        return root;

    if (p->val < root->val && q->val < root->val) 
        return lowestCommonAncestor(root->left, p, q);

    if (p->val > root->val && q->val > root->val) 
        return lowestCommonAncestor(root->right, p, q);

    return root;
}

二叉树的最近公共祖先

二叉树的最近公共祖先

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q){
    if (root == NULL || p == root || q == root) return root;
    struct TreeNode* lResult = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* rResult = lowestCommonAncestor(root->right, p, q);
    if (lResult != NULL && rResult != NULL) return root;
    if (lResult == NULL) return rResult;
    if (rResult == NULL) return lResult;
    return root;
}

二叉树的直径

二叉树的直径

var result = 0

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

func getTreeDeep(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return max(getTreeDeep(root.Left), getTreeDeep(root.Right)) + 1
}

func calResult(root *TreeNode) {
    if root == nil {
        return
    }

    lRootDeep := getTreeDeep(root.Left)
    rRootDeep := getTreeDeep(root.Right)

    if lRootDeep + rRootDeep > result {
        result = lRootDeep + rRootDeep
    }

    calResult(root.Left)
    calResult(root.Right)
}

func diameterOfBinaryTree(root *TreeNode) int {
    if root == nil {
        return 0
    }
    result = 0
    calResult(root)
    return result
}

二叉树的深度

二叉树的深度

func maxDepth(root *TreeNode) int {
    result := 0
    if root == nil {
        return result
    }

    stack := []*TreeNode{}
    stack = append(stack, root)

    for {
        if len(stack) == 0 {
            break
        }
        line := []int{}
        now_stack := []*TreeNode{}

        for i := 0;  i < len(stack); i++ {
                line = append(line, stack[i].Val)
                if stack[i].Left != nil {
                    now_stack = append(now_stack, stack[i].Left)
                }
                if stack[i].Right != nil {
                    now_stack = append(now_stack, stack[i].Right)
                }
            }
        stack = now_stack
        result = result + 1
    }

    return result
}

二叉树最大宽度

二叉树最大宽度

func widthOfBinaryTree(root *TreeNode) int {
    if root == nil {
        return 0
    }

    result := 1
    stack := []*TreeNode{}

    root.Val = 1
    stack = append(stack, root)

    for {
        if len(stack) == 0 {
            break
        }

        if stack[len(stack)-1].Val - stack[0].Val + 1 > result {
            result = stack[len(stack)-1].Val - stack[0].Val + 1
        }

        now_stack := []*TreeNode{}
        for i := 0;  i < len(stack); i++ {
            if stack[i].Left != nil {
                stack[i].Left.Val = stack[i].Val * 2
                now_stack = append(now_stack, stack[i].Left)
            }
            if stack[i].Right != nil {
                stack[i].Right.Val = stack[i].Val * 2 + 1
                now_stack = append(now_stack, stack[i].Right)
            }
        }
        stack = now_stack
    }

    return result
}

镜像二叉树

func swapNode(root *TreeNode) {
    if root == nil {
        return
    }
    if root.Left == nil && root.Right == nil {
        return 
    }

    swap := root.Left
    root.Left = root.Right
    root.Right = swap

    swapNode(root.Left)
    swapNode(root.Right)
}

func mirrorTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Left == nil && root.Right == nil {
        return root
    }

    swapNode(root)
    return root
}

对称的二叉树

对称的二叉树

func isSymmetric(root *TreeNode) bool {
    nodeList := []*TreeNode{root}
    for {
        isBreak := true
        values := []int{}
        nodeListNew := []*TreeNode{}
        for _, node := range nodeList {
            if node == nil {
                values = append(values, -123456789)
                nodeListNew = append(nodeListNew, nil)
                nodeListNew = append(nodeListNew, nil)
            } else {
                isBreak = false
                values = append(values, node.Val)
                nodeListNew = append(nodeListNew, node.Left)
                nodeListNew = append(nodeListNew, node.Right)
            }
        }
        if isBreak {
            break
        }
        for i:=0; i<=len(values)/2; i++ {
            if values[i] != values[len(values)-1-i] {
                return false
            }
        }
        nodeList = nodeListNew
    }
    return true
}

3.4 并查集

示例题目:省份数量

var fa[210]int

func findXFa(x int) int {
    if x == fa[x] {
        return x
    } else {
        return findXFa(fa[x])
    }
}

func union(x int, y int) {
    fx := findXFa(x)
    fy := findXFa(y)

    if (fx == fy){
        return
    } else if fy > fx {
        fa[fy] = fx
    } else { 
        fa[fx] = fy
    }
}

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    for i := 0; i < n; i++ {
        fa[i] = i
    }

    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if i != j && isConnected[i][j] == 1 {
                union(i, j)
            }
        }
    }

    var result int
    for i := 0; i < n; i++ {
        if fa[i] == i {
            result += 1
        }
    }
    return result
}

3.5 线段树

线段树

package main

import (
    "fmt"
)

type SegmentTree struct {
    nums []int
    sums [40010]int
}

func(this *SegmentTree) Build(left, right, idx int) {
    if left == right {
        this.sums[idx] = this.nums[left-1]
    } else {
        mid := (left + right) >> 1
        this.Build(left, mid, idx<<1)
        this.Build(mid + 1, right, idx<<1 | 1)
        this.sums[idx] = this.sums[idx<<1] + this.sums[idx<<1 | 1]
    }
}

func(this *SegmentTree) Update(k, v, left, right, idx int) {
    if left == right && left == k {
        this.sums[idx] = v
        return
    }
    mid := (left + right) >> 1
    if k <= mid {
        this.Update(k, v, left, mid, idx << 1)
    } else {
        this.Update(k, v, mid + 1, right, idx << 1 | 1)
    }
    this.sums[idx] = this.sums[idx<<1] + this.sums[idx<<1 | 1]
}

func(this *SegmentTree) QuerySum(st, ed, left, right, idx int) int {
    if st <= left  && right <= ed {
        return this.sums[idx]
    } else {
        mid := (left +right) >> 1
        res := 0
        if st <= mid {
            res += this.QuerySum(st, ed, left, mid, idx << 1)
        }
        if ed > mid {
            res += this.QuerySum(st, ed, mid+1, right, idx << 1 | 1)
        }
        return res
    }
}


func main() {
    nums := []int{1, 2, 3, 4, 5, 6}
    // fmt.Println(len(nums)-1)

    var segTree SegmentTree
    segTree.nums = nums

    segTree.Build(1, len(nums), 1)
    fmt.Println(segTree.QuerySum(1, 3, 1, len(nums),1))
    fmt.Println(segTree.QuerySum(3, 6, 1, len(nums),1))
    fmt.Println(segTree.QuerySum(1, 6, 1, len(nums),1))

    segTree.Update(1, 5, 1, len(nums), 1)
    fmt.Println(segTree.QuerySum(1, 3, 1, len(nums),1))
    fmt.Println(segTree.QuerySum(3, 6, 1, len(nums),1))
    fmt.Println(segTree.QuerySum(1, 6, 1, len(nums),1))
}
/*
6
18
21
10
18
25
*/

3.6 Trie树

3.7 二叉排序树

第四章 动态规划

4.1 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))
}

4.2 最长递增子序列

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

4.3 最长公共子序列

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

4.4 最大字段和

最大字段和

func maxSubArray(nums []int) int {
    sum, res := nums[0], nums[0]

    for i := 1; i < len(nums); i++ {
        if sum > 0 {
            sum += nums[i]
        } else {
            if nums[i] > sum {
                sum = nums[i]
            } 
        }
        if sum > res {
            res = sum
        }
    }
    return res
}

4.5 树塔问题

树塔问题

func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    var dp [210][210]int

    for i:=n-1; i>=0; i-- {
        for j:=0; j<=i; j++ {
            if triangle[i][j] + dp[i+1][j] < triangle[i][j] + dp[i+1][j+1] {
                dp[i][j] = triangle[i][j] + dp[i+1][j]
            } else {
                dp[i][j] = triangle[i][j] + dp[i+1][j+1]
            }
        }
    }
    return dp[0][0]
}

4.6 两个字符串的编辑距离

编辑距离


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

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

func minDistance(word1 string, word2 string) int {
    var dp[1010][1010]int
    dp[0][0] = 0
    l1, l2 := len(word1), len(word2)

    for i := 0; i <= l1; i++ {
        dp[i][0] = i
    }
    for i := 0; i <= l2; i++ {
        dp[0][i] = i
    }

    for i := 0; i < l1; i++ {
        for j := 0; j < l2; j++ {
            if word1[i] == word2[j] {
                dp[i+1][j+1] = dp[i][j]
            } else {
                dp[i+1][j+1] = min(dp[i][j], min(dp[i+1][j], dp[i][j+1])) + 1
            }
        }
    }

    return dp[l1][l2]
}

4.7 股票买卖问题

121.买卖股票的最佳时机

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

func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }

    var result int
    minNum := prices[0]
    for i := 0; i< len(prices); i++ {
        if prices[i]>minNum {
            result = max(result, prices[i] - minNum)
        }
        if prices[i] < minNum {
            minNum = prices[i]
        }
    }
    return result
}

122.买卖股票的最佳时机 II

func maxProfit(prices []int) int {
    if len(prices) <= 1 {
        return 0
    }

    result := 0
    minPrice := prices[0]
    for i:=0; i<len(prices); i++ {
        if prices[i] > minPrice {
            result += prices[i] - minPrice
            minPrice = prices[i]
        } else {
            minPrice = prices[i]
        }
    }
    return result
}

第五章 搜索

5.1 二分查找

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

5.2 BFS

例题:剑指 Offer 13. 机器人的运动范围

func sumDig(i int) int {
    res :=0
    for {
        if i == 0 {
            break
        }
        res += i%10
        i/=10
    }
    return res
}

type Node struct {
    x int
    y int
}

func movingCount(m int, n int, k int) int {
    first := &Node{0, 0}
    stack := []*Node{first}
    isOk := make(map[int]int)

    res := 0
    for {
        if len(stack) == 0 {
            break
        }

        head := stack[0]
        stack = stack[1:]

        if val, ok := isOk[head.x]; ok {
            if val == head.y {
                continue
            }
        }

        if sumDig(head.x) + sumDig(head.y) <= k {
            res += 1
            if head.x + 1 < m {
                nd := &Node{head.x + 1, head.y}
                stack = append(stack, nd)
            }
            if head.y + 1 < n {
                nd := &Node{head.x, head.y+1}
                stack = append(stack, nd)
            }
        }

        isOk[head.x] = head.y
    }
    return res
}

5.3 DFS

第六章 图算法

6.1 最短路径

dijkstra

6.2 二分图

匈牙利算法原理

6.3 拓扑排序

示例题目 : 课程表 II

func findOrder(numCourses int, prerequisites [][]int) []int {
    in := make(map[int]int) // 点的入边数量
    edge := make(map[int][]int) // 点的下一个连接点

    for i := 0; i < len(prerequisites); i++ {
        prerequisite := prerequisites[i]
        edge[prerequisite[1]] = append(edge[prerequisite[1]], prerequisite[0])
        in[prerequisite[0]] += 1
    }

    queue := []int{}
    for i := 0; i < numCourses; i++ {
        if in[i] == 0 {
            queue = append(queue, i)
        }
    }

    result := []int{}
    var top int
    for len(queue) > 0 {
        top = queue[0]
        queue = queue[1:]
        result = append(result, top)
        for _, val := range edge[top] {
            in[val] -= 1
            if in[val] == 0 {
                queue = append(queue, val)
            }
        }
    }
    if len(result) == numCourses {
        return result
    }
    return []int{}
}

6.4 最小生成树

第七章 字符串算法

7.1 KMP

7.2 Manacher

manacher介绍

package main

import "fmt"

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

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

type Manacher struct {
     originStrList string
     strList string
}

func(this *Manacher) InitStr() {
    var newStr string
    newStr += "#"
    for i := 0; i < len(this.originStrList); i++ {
        newStr += string(this.originStrList[i])
        newStr += "#"
    }
    this.strList = newStr
}

func(this *Manacher) Solve() int {
    radiuxList := [100010]int{}
    rightRadiuxIdx, nowIdx := 0, 0

    res := 0
    for i:=1; i<len(this.strList); i++ {
        if rightRadiuxIdx > i {
            radiuxList[i] = min(radiuxList[2*nowIdx-i], rightRadiuxIdx - i)
        } else {
            radiuxList[i] = 1
        }

        for i - radiuxList[i] >= 0 &&
            i + radiuxList[i] < len(this.strList) &&
            this.strList[i - radiuxList[i]] == this.strList[i + radiuxList[i]] {
            radiuxList[i] += 1
        }

        res = max(radiuxList[i], res)
        if radiuxList[i] + i > rightRadiuxIdx {
            rightRadiuxIdx = radiuxList[i] + i
            nowIdx = i
        }
    }
    return res - 1
}

func main() {
    str := "abcdefed111"
    var manacher Manacher
    manacher.originStrList = str
    manacher.InitStr()

    fmt.Println(manacher.originStrList)
    fmt.Println(manacher.strList)

    fmt.Println(manacher.Solve())
}
/*
abcdefed111
#a#b#c#d#e#f#e#d#1#1#1#
5
*/

7.3 AC自动机

第八章 海量数据处理

8.1 Bitmap

8.2 布隆过滤器

原理介绍

8.3 Simhash

SimHash原理

SimHash原理

8.4 MapReduce

第九章 其他

LRU

LRU

package lru

import "container/list"

// Cache is an LRU cache. It is not safe for concurrent access.
type Cache struct {
    // MaxEntries is the maximum number of cache entries before
    // an item is evicted. Zero means no limit.
    MaxEntries int

    // OnEvicted optionally specifies a callback function to be
    // executed when an entry is purged from the cache.
    OnEvicted func(key Key, value interface{})

    ll    *list.List
    cache map[interface{}]*list.Element
}

// A Key may be any value that is comparable. See http://golang.org/ref/spec#Comparison_operators
type Key interface{}

type entry struct {
    key   Key
    value interface{}
}

// New creates a new Cache.
// If maxEntries is zero, the cache has no limit and it's assumed
// that eviction is done by the caller.
func New(maxEntries int) *Cache {
    return &Cache{
        MaxEntries: maxEntries,
        ll:         list.New(),
        cache:      make(map[interface{}]*list.Element),
    }
}

// Add adds a value to the cache.
func (c *Cache) Add(key Key, value interface{}) {
    if c.cache == nil {
        c.cache = make(map[interface{}]*list.Element)
        c.ll = list.New()
    }
    if ee, ok := c.cache[key]; ok {
        c.ll.MoveToFront(ee)
        ee.Value.(*entry).value = value
        return
    }
    ele := c.ll.PushFront(&entry{key, value})
    c.cache[key] = ele
    if c.MaxEntries != 0 && c.ll.Len() > c.MaxEntries {
        c.RemoveOldest()
    }
}

// Get looks up a key's value from the cache.
func (c *Cache) Get(key Key) (value interface{}, ok bool) {
    if c.cache == nil {
        return
    }
    if ele, hit := c.cache[key]; hit {
        c.ll.MoveToFront(ele)
        return ele.Value.(*entry).value, true
    }
    return
}

// Remove removes the provided key from the cache.
func (c *Cache) Remove(key Key) {
    if c.cache == nil {
        return
    }
    if ele, hit := c.cache[key]; hit {
        c.removeElement(ele)
    }
}

// RemoveOldest removes the oldest item from the cache.
func (c *Cache) RemoveOldest() {
    if c.cache == nil {
        return
    }
    ele := c.ll.Back()
    if ele != nil {
        c.removeElement(ele)
    }
}

func (c *Cache) removeElement(e *list.Element) {
    c.ll.Remove(e)
    kv := e.Value.(*entry)
    delete(c.cache, kv.key)
    if c.OnEvicted != nil {
        c.OnEvicted(kv.key, kv.value)
    }
}

// Len returns the number of items in the cache.
func (c *Cache) Len() int {
    if c.cache == nil {
        return 0
    }
    return c.ll.Len()
}

// Clear purges all stored items from the cache.
func (c *Cache) Clear() {
    if c.OnEvicted != nil {
        for _, e := range c.cache {
            kv := e.Value.(*entry)
            c.OnEvicted(kv.key, kv.value)
        }
    }
    c.ll = nil
    c.cache = nil
}

LFU

数组中出现次数超过一半的数字

数组中出现次数超过一半的数字

func majorityElement(nums []int) int {
    val, cnt := 0, 0
    for idx, _ := range nums {
        if cnt == 0 {
            val = nums[idx]
            cnt = cnt + 1
        } else if nums[idx] == val {
            cnt = cnt + 1
        } else {
            cnt = cnt - 1
        }
    }
    return val
}

无序数组中位数

求两个有序数组的中位数

全排列