基础算法和数据结构

1 DONE 排序

  • State "DONE" from "TODO" [2018-03-20 Tue 18:34]

1.1 DONE 两个有序数组合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func merge(A, B []int) []int {
C := make([]int, 0)
a_i, b_i := 0, 0
for a_i < len(A) && b_i < len(B) {
if A[a_i] > B[b_i] {
C = append(C, B[b_i])
b_i += 1
} else if A[a_i] < B[b_i] {
C = append(C, A[a_i])
a_i += 1
} else {
C = append(C, A[a_i], B[b_i])
a_i += 1
b_i += 1
}
}

if a_i < len(A) {
C = append(C, A[a_i:]...)
}

if b_i < len(B) {
C = append(C, B[b_i:]...)
}

return C
}
1
2
3
4
5
6
7
8
9
10
11
package main

import "fmt"



func main() {
fmt.Println(merge([]int{1, 3, 5}, []int{2, 4, 6}))
fmt.Println(merge([]int{1, 3, 5, 7, 9}, []int{2, 4, 6}))
fmt.Println(merge([]int{1, 3, 5}, []int{2, 4, 6, 8, 10}))
}

1.2 DONE 插入排序

  • State "DONE" from "TODO" [2018-03-17 Sat 13:10]
1
2
3
4
5
6
7
8
9
10
11
func isort(nums []int) {
for i := 1; i < len(nums); i += 1 {
for j := i; j > 0; j -= 1 {
if nums[j-1] > nums[j] {
nums[j-1], nums[j] = nums[j], nums[j-1]
} else {
break
}
}
}
}
1
2
3
4
5
6
7
8
9
10
11
package main

import "fmt"



func main() {
nums := []int{2, 3, 6, 1, 5, 7, 9, 4}
isort(nums)
fmt.Println(nums)
}

1.3 DONE 二分排序

1
2
3
4
5
6
7
8
9
10
func bsort(nums []int) {
if len(nums) == 1 {
return
}

bsort(nums[0 : len(nums)/2])
bsort(nums[len(nums)/2:])

copy(nums, merge(nums[0:len(nums)/2], nums[len(nums)/2:]))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
package main

import "fmt"





func main() {
nums := []int{2, 3, 5, 4, 1, 10, 7, 9, 8}
bsort(nums)
fmt.Println(nums)
}

1.4 DONE 快速排序

1
2
3
4
5
6
7
8
9
func qsort(nums []int) {
if len(nums) < 2 {
return
}

p := partition(nums)
qsort(nums[0:p])
qsort(nums[p+1:])
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func partition(nums []int) int {
r := rand.Intn(len(nums))
nums[r], nums[0] = nums[0], nums[r]
mid := nums[0]
s, e := 0, len(nums)-1
for s < e {
for s < e && nums[e] >= mid {
e -= 1
}

if s < e {
nums[s] = nums[e]
}

for s < e && nums[s] <= mid {
s += 1
}

if s < e {
nums[e] = nums[s]
}
}
nums[s] = mid
return s
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

import (
"fmt"
"math/rand"
)





func main() {
nums := []int{2, 8, 5, 4, 6, 10, 7, 9, 3}
qsort(nums)
fmt.Println(nums)
nums = []int{2, 8, 5, 7, 1, 10, 4, 9, 3}
qsort(nums)
fmt.Println(nums)
nums = []int{2, 8, 5, 7, 10, 11, 4, 9, 3}
qsort(nums)
fmt.Println(nums)
}

1.5 DONE 堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
func parent(i int) int {
return (i - 1) / 2
}

func left(i int) int {
return 2*i + 1
}

func right(i int) int {
return 2*i + 2
}

func heapDown(nums []int, start, end int) {
p := start
l := left(p)
for {
if l > end {
break
}

if l < end && nums[l] < nums[l+1] {
l += 1
}

if nums[p] >= nums[l] {
break
} else {
nums[l], nums[p] = nums[p], nums[l]
p = l
l = left(p)
}
}
}

func hsort(nums []int) {
for i := len(nums) / 2; i >= 0; i -= 1 {
heapDown(nums, i, len(nums)-1)
}

for i := len(nums) - 1; i > 0; i -= 1 {
nums[i], nums[0] = nums[0], nums[i]

heapDown(nums, 0, i-1)
}
}
1
2
3
4
5
6
7
8
9
10
11
package main

import "fmt"



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

1.6 DONE 计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func countingSort(nums []int) []int {
max := nums[0]
for _, num := range nums {
if num > max {
max = num
}
}

ansArr := make([]int, len(nums))
countArr := make([]int, max+1)

for i := 0; i < len(nums); i += 1 {
countArr[nums[i]] += 1
}

for i := 1; i < len(countArr); i += 1 {
countArr[i] += countArr[i-1]
}

for i := len(nums) - 1; i >= 0; i -= 1 {
ansArr[countArr[nums[i]]-1] = nums[i]
countArr[nums[i]] -= 1
}

return ansArr
}
1
2
3
4
5
6
7
8
9
10
package main

import "fmt"



func main() {
nums := []int{2, 3, 5, 2, 3, 4, 8, 9, 7, 6, 8, 7, 5, 4, 6, 7}
fmt.Println(countingSort(nums))
}

1.7 DONE 基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
func radixSort(nums []int) []int {
max := nums[0]
for _, num := range nums {
if num > max {
max = num
}
}
d := 1
tmp_max := max
for tmp_max > 0 {
tmp_max /= 10
d += 1
}

for i := 0; i < d; i += 1 {
nums = countingSort(nums, i)
}

return nums
}

func countingSort(nums []int, d int) []int {
max := 9
ansArr := make([]int, len(nums))
countArr := make([]int, max+1)

for i := 0; i < len(nums); i += 1 {
countArr[getBit(nums[i], d)] += 1
}

for i := 1; i < len(countArr); i += 1 {
countArr[i] += countArr[i-1]
}

for i := len(nums) - 1; i >= 0; i -= 1 {
ansArr[countArr[getBit(nums[i], d)]-1] = nums[i]
countArr[getBit(nums[i], d)] -= 1
}

return ansArr
}

func getBit(num, d int) int {
for num != 0 && d > 0 {
num /= 10
d -= 1
}

return num % 10
}
1
2
3
4
5
6
7
8
9
10
package main

import "fmt"



func main() {
nums := []int{123, 336, 255, 298, 321, 49, 82, 93, 78, 65, 81, 73, 550, 425, 68, 72}
fmt.Println(radixSort(nums))
}

1.8 DONE 桶排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
type ListNode struct {
next *ListNode
num int
}

func insert(h *ListNode, val int) *ListNode {
newNode := &ListNode{num: val}
dummyNode := &ListNode{next: h}
pre := dummyNode
curr := h
for curr != nil && curr.num <= val {
pre = curr
curr = curr.next
}

newNode.next = curr
pre.next = newNode

return dummyNode.next
}

func merge(lh, rh *ListNode) *ListNode {
dummyNode := &ListNode{}
dummy := dummyNode
for lh != nil && rh != nil {
if lh.num <= rh.num {
dummy.next = lh
lh = lh.next
} else {
dummy.next = rh
rh = rh.next
}
dummy = dummy.next
}

if lh != nil {
dummy.next = lh
}
if rh != nil {
dummy.next = rh
}

return dummyNode.next
}

func BucketSort(nums []int, bucket_num int) {
buckets := make([]*ListNode, bucket_num)
for _, num := range nums {
i := num / bucket_num
h := buckets[i]
buckets[i] = insert(h, num)
}

h := buckets[0]
for i := 1; i < len(buckets); i += 1 {
h = merge(h, buckets[i])
}

for i := 0; i < len(buckets); i += 1 {
nums[i] = h.num
h = h.next
}

return
}
1
2
3
4
5
6
7
8
9
10
11
package main

import "fmt"



func main() {
nums := []int{22, 25, 11, 15, 33, 44, 55, 66, 77, 88, 99}
BucketSort(nums, 10)
fmt.Println(nums)
}

2 DONE 查找

2.1 DONE 二分查找

  • State "DONE" from "TODO" [2018-03-27 Tue 11:28]

2.1.1 DONE 递归

  • State "DONE" from "TODO" [2018-03-27 Tue 11:28]
1
2
3
4
5
6
7
8
9
10
11
12
13
func binarySearch(nums []int, start, end, target int) int {
if start > end {
return -1
}
mid := start + (end-start)/2
if nums[mid] > target {
return binarySearch(nums, start, mid-1, target)
} else if nums[mid] < target {
return binarySearch(nums, mid+1, end, target)
} else {
return mid
}
}

2.1.2 DONE 非递归

  • State "DONE" from "TODO" [2018-03-27 Tue 11:28]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func binarySearch(nums []int, start, end, target int) int {
for {
if start > end {
return -1
}

mid := start + (end-start)/2
if nums[mid] > target {
end = mid - 1
} else if nums[mid] < target {
start = mid + 1
} else {
return mid
}
}
}

2.2 DONE 插值查找

  • State "DONE" from "TODO" [2018-03-27 Tue 11:24]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func interpolationSearch(nums []int, start, end, target int) int {
if start > end {
return -1
}

mid := start + (target-nums[start])/(nums[end]-nums[start])*(end-start)
if nums[mid] > target {
return interpolationSearch(nums, start, mid-1, target)
} else if nums[mid] < target {
return interpolationSearch(nums, mid+1, end, target)
} else {
return mid
}
}

2.3 DONE 斐波那契查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package main

import "fmt"

type FibonacciFunc func(int) int

func GenFibonacciFunc(size int) FibonacciFunc {
if size < 2 {
size = 2
}
capacity := 20
nums := make([]int, size, capacity)
nums[0] = 0
nums[1] = 1
for i := 2; i < len(nums); i += 1 {
nums[i] = nums[i-1] + nums[i-2]
}

return func(index int) int {
if len(nums) > index {
return nums[index]
}

csize := len(nums)
for csize <= index {
nums = append(nums, nums[csize-1]+nums[csize-2])
csize += 1
}

return nums[index]
}
}

func fibonacciSearch(nums []int, target int) int {
fibFunc := GenFibonacciFunc(10)
size := len(nums)
start, end := 0, size-1
fi := 0
for {
if size > fibFunc(fi) {
fi += 1
} else {
break
}
}

for {
if start > end {
return -1
}

// adjust fi
for start+fibFunc(fi-1)-1 > end {
fi -= 1
}
mid := start + fibFunc(fi-1) - 1

if target < nums[mid] {
end = mid - 1
fi -= 1
} else if target > nums[mid] {
start = mid + 1
fi -= 2
} else {
return mid
}
}
}

func main() {
nums := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
fmt.Println(fibonacciSearch(nums, 1))
fmt.Println(fibonacciSearch(nums, 10))
fmt.Println(fibonacciSearch(nums, 5))
fmt.Println(fibonacciSearch(nums, 15))
}

2.4 DONE 字符串暴力匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func violenMatch(s, p string) bool {
sLen, pLen := len(s), len(p)
si, pi := 0, 0
for si < sLen && pi < pLen {
if s[si] == p[pi] {
si += 1
pi += 1
} else {
si = si - pi + 1
pi = 0
}
}

if pi == pLen {
return true
} else {
return false
}
}
1
2
3
4
5
6
7
8
9
package main

import "fmt"



func main() {
fmt.Println(violenMatch("BBC ABCDAB ABCDABCDABDE", "ABCDABD"))
}

2.5 DONE KMP算法

假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置:

  • 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符
  • 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。 此举意味着失配时,模式串P相对于文本串S向右移动了 j-next[j] 位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func getNext(p string) []int {
pLen := len(p)
next := make([]int, pLen)
next[0] = -1

k, j := -1, 0
for j < pLen-1 {
if k == -1 || p[j] == p[k] {
k += 1
j += 1
next[j] = k
} else {
k = next[k]
}
fmt.Println(next, j, k)
}

return next
}

func kmpMatch(s, p string) bool {
next := getNext(p)

sLen := len(s)
pLen := len(p)

i, j := 0, 0
for i < sLen && j < pLen {
if j == -1 || s[i] == p[j] {
i += 1
j += 1
} else {
j = next[j]
}
}

if j == pLen {
return true
} else {
return false
}
}
1
2
3
4
5
6
7
8
9
package main

import "fmt"



func main() {
fmt.Println(kmpMatch("BBC ABCDAB ABCDABCDABDE", "CDABCDABD"))
}

3 DONE 链表

  • State "DONE" from "TODO" [2018-03-26 Mon 17:27]

3.1 DONE 单向链表

  • State "DONE" from "TODO" [2018-03-22 Thu 22:19]
    1
    2
    3
    4
    type ListNode struct {
    Val int
    Next *ListNode
    }
    1
    2
    3
    4
    5
    struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
    };

3.1.1 DONE Rotate List

  • State "DONE" from "FIXED" [2018-03-22 Thu 15:04]
  • State "FIXED" from "TODO" [2018-03-22 Thu 15:04]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func rotateRight(head *ListNode, k int) *ListNode {
size := 0
curr := head
for curr != nil {
curr = curr.Next
size += 1
}
if size == 0 {
return head
}

k = k % size
if k == 0 {
return head
}

index := size - k - 1
curr = head
for index > 0 {
curr = curr.Next
index -= 1
}

nh := curr.Next
curr.Next = nil

curr = nh
for curr.Next != nil {
curr = curr.Next
}
curr.Next = head

return nh
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package main

import "fmt"





func main() {
head := &ListNode{
Val: 1,
Next: &ListNode{
Val: 2,
Next: &ListNode{
Val: 3,
},
},
}

head = rotateRight(head, 1)
curr:= head
for curr != nil {
fmt.Println(curr.Val)
curr = curr.Next
}
}

3.1.2 DONE Reverse Linked List

  • State "DONE" from "TODO" [2018-03-22 Thu 16:18]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func reverseList(head *ListNode) *ListNode {
if head == nil {
return head
}

dummyNode := &ListNode{Next: head}
pre := head
curr := head.Next
head.Next = nil
for curr != nil {
pre = curr
curr = curr.Next

pre.Next = dummyNode.Next
dummyNode.Next = pre
}

return dummyNode.Next
}

3.1.3 DONE Delete Node in a Linked List

  • State "DONE" from "TODO" [2018-03-22 Thu 16:52]
1
2
3
4
5
6
7
8
class Solution {
public:
void deleteNode(ListNode* node) {
auto next = node->next;
*node = *next;
delete next;
}
};

3.1.4 DONE Merge Two Sorted Lists

  • State "DONE" from "TODO" [2018-03-22 Thu 17:40]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummyNode := &ListNode{}
dummy := dummyNode

for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
dummy.Next = l1
l1 = l1.Next
} else {
dummy.Next = l2
l2 = l2.Next
}
dummy = dummy.Next
}

if l1 != nil {
dummy.Next = l1
}
if l2 != nil {
dummy.Next = l2
}

return dummyNode.Next
}

3.1.5 DONE Linked List Cycle

  • State "DONE" from "TODO" [2018-03-22 Thu 18:03]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
bool hasCycle(ListNode *head) {
if (head == NULL || head->next == NULL) {
return false;
}

auto lp = head->next;
auto rp = head->next->next;

while (lp != NULL && rp != NULL) {
if (lp == rp) {
return true;
}

lp = lp->next;
if (rp->next == NULL) {
return false;
}
rp = rp->next->next;
}

return false;
}
};

3.1.6 DONE Linked List Cycle II

  • State "DONE" from "TODO" [2018-03-22 Thu 22:18]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == NULL || head->next == NULL) {
return NULL;
}

auto lp = head->next;
auto rp = head->next->next;

while (lp != NULL && rp != NULL) {
if (lp == rp) {
break;
}

lp = lp->next;
if (rp->next == NULL) {
return NULL;
}
rp = rp->next->next;
}

if (lp != rp) {
return NULL;
}

int cl = 1;
rp = rp->next;
while (lp != rp) {
rp = rp->next;
cl += 1;
}

lp = head;
rp = head;
while (cl > 0) {
lp = lp->next;
cl -= 1;
}

while (lp != rp) {
lp = lp->next;
rp = rp->next;
}

return rp;
}
};

3.1.7 DONE 合并K个元素的有序链表

  • State "DONE" from "TODO" [2018-04-08 Sun 11:38]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import (
"container/heap"
)

type ListNode struct {
Val int
Next *ListNode
}

type MyMinHeap []*ListNode

func (h MyMinHeap) Len() int { return len(h) }
func (h MyMinHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h MyMinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *MyMinHeap) Push(e interface{}) {
*h = append(*h, e.(*ListNode))
}

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

func mergeKLists(lists []*ListNode) *ListNode {
h := &MyMinHeap{}
head := &ListNode{}
dummyNode := head
for i := 0; i < len(lists); i += 1 {
if lists[i] != nil {
heap.Push(h, lists[i])
}
}

for h.Len() > 0 {
n := heap.Pop(h).(*ListNode)
if n.Next != nil {
heap.Push(h, n.Next)
}
dummyNode.Next = n
dummyNode = dummyNode.Next
}

return head.Next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummyNode := &ListNode{}
dummy := dummyNode

for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
dummy.Next = l1
l1 = l1.Next
} else {
dummy.Next = l2
l2 = l2.Next
}
dummy = dummy.Next
}

if l1 != nil {
dummy.Next = l1
}
if l2 != nil {
dummy.Next = l2
}

return dummyNode.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) < 1 {
return nil
}

head := lists[0]
for i := 1; i < len(lists); i += 1 {
head = mergeTwoLists(head, lists[i])
}

return head
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
dummyNode := &ListNode{}
dummy := dummyNode

for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
dummy.Next = l1
l1 = l1.Next
} else {
dummy.Next = l2
l2 = l2.Next
}
dummy = dummy.Next
}

if l1 != nil {
dummy.Next = l1
}
if l2 != nil {
dummy.Next = l2
}

return dummyNode.Next
}

func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 2 {
return mergeTwoLists(lists[0], lists[1])
} else if len(lists) == 1 {
return lists[0]
} else if len(lists) == 0 {
return nil
}

ll := mergeKLists(lists[:len(lists)/2])
rl := mergeKLists(lists[len(lists)/2:])

return mergeTwoLists(ll, rl)
}

3.1.8 DONE 每k个一组翻转链表

  • State "DONE" from "TODO" [2018-04-08 Sun 14:49]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
func reverseKGroup(head *ListNode, k int) *ListNode {
if head == nil || k < 2 {
return head
}

dummyNode := &ListNode{Next: head}
kg_dummyNode := dummyNode
kg_pre := kg_dummyNode.Next
kg_curr := kg_pre.Next
kg_tail := kg_pre

cn := k - 1
for kg_curr != nil {
kg_pre = kg_curr
kg_curr = kg_curr.Next

kg_pre.Next = kg_dummyNode.Next
kg_dummyNode.Next = kg_pre
cn -= 1

if cn == 0 && kg_curr != nil {
kg_tail.Next = kg_curr
kg_dummyNode = kg_tail
kg_pre = kg_curr
kg_curr = kg_pre.Next
kg_tail = kg_pre
cn = k - 1
}
}
kg_tail.Next = nil

if cn > 0 {
pre := kg_dummyNode.Next
curr := pre.Next
pre.Next = nil
for curr != nil {
pre = curr
curr = curr.Next

pre.Next = kg_dummyNode.Next
kg_dummyNode.Next = pre
}
}

return dummyNode.Next
}

3.2 DONE 双向链表

  • State "DONE" from "TODO" [2018-03-26 Mon 17:27]

3.2.1 DONE All O`one Data Structure

  • State "DONE" from "TODO" [2018-03-26 Mon 17:26]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package main

import (
"container/list"
"fmt"
)

type Ele struct {
Key string
Counter int
}

type AllOne struct {
EleM map[string]*list.Element
Lst *list.List
}

/** Initialize your data structure here. */
func Constructor() AllOne {
return AllOne{
Lst: list.New(),
EleM: make(map[string]*list.Element),
}
}

/** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
func (this *AllOne) Inc(key string) {
if e, ok := this.EleM[key]; ok {
e.Value.(*Ele).Counter += 1
next := e
for {
if next == nil {
break
}
if next.Value.(*Ele).Counter > e.Value.(*Ele).Counter {
break
} else {
next = next.Next()
}
}

if next == nil {
this.Lst.MoveToBack(e)
} else {
this.Lst.MoveBefore(e, next)
}
} else {
ele := &Ele{
Key: key,
Counter: 1,
}
e := this.Lst.PushFront(ele)
this.EleM[key] = e
}
return
}

/** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
func (this *AllOne) Dec(key string) {
if e, ok := this.EleM[key]; ok {
ele := e.Value.(*Ele)
if ele.Counter == 1 {
this.Lst.Remove(e)
delete(this.EleM, key)
} else {
ele.Counter -= 1
prev := e
for {
if prev == nil {
break
}

if prev.Value.(*Ele).Counter < ele.Counter {
break
} else {
prev = prev.Prev()
}
}
if prev == nil {
this.Lst.MoveToFront(e)
} else {
fmt.Println("prev: ", prev.Value)
this.Lst.MoveAfter(e, prev)
}
}
}
return
}

/** Returns one of the keys with maximal value. */
func (this *AllOne) GetMaxKey() string {
tail := this.Lst.Back()
if tail != nil {
return tail.Value.(*Ele).Key
} else {
return ""
}
}

/** Returns one of the keys with Minimal value. */
func (this *AllOne) GetMinKey() string {
head := this.Lst.Front()
if head != nil {
return head.Value.(*Ele).Key
} else {
return ""
}
}

func (this *AllOne) Debug() {
fmt.Println(this.EleM)
for e := this.Lst.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}

func main() {
ao := Constructor()
ao.Inc("b")
ao.Inc("a")
ao.Debug()
ao.Inc("a")
ao.Debug()
ao.Inc("b")
ao.Debug()
ao.Inc("a")
ao.Debug()
ao.Inc("c")
ao.Dec("c")
ao.Dec("a")
ao.Dec("a")
ao.Debug()
fmt.Println(ao.GetMaxKey())
fmt.Println(ao.GetMinKey())
}

4 DONE LIFO 栈

  • State "DONE" from "TODO" [2018-03-27 Tue 22:45]

4.1 DONE 实现

  • State "DONE" from [2018-03-27 Tue 17:21]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
type Stack struct {
lst *list.List
}

func New() *Stack {
return &Stack{
lst: list.New(),
}
}

func (s *Stack) Len() int {
return s.lst.Len()
}

func (s *Stack) Empty() bool {
return s.lst.Len() == 0
}

func (s *Stack) Push(v interface{}) {
s.lst.PushBack(v)
}

func (s *Stack) Pop() interface{} {
back := s.lst.Back()
if back != nil {
return s.lst.Remove(back)
} else {
return nil
}
}

func (s *Stack) Top() interface{} {
back := s.lst.Back()
if back != nil {
return back.Value
} else {
return nil
}
}
1
2
3
4
5
6
7
8
9
10
11
12
func main() {
s := New()
s.Push(1)
s.Push(2)
s.Push(3)
fmt.Println(s.Top())
fmt.Println(s.Pop())
fmt.Println(s.Top())
fmt.Println(s.Pop())
fmt.Println(s.Top())
fmt.Println(s.Pop())
}

4.2 DONE 应用

  • State "DONE" from "TODO" [2018-03-27 Tue 22:45]

4.2.1 DONE Implement Queue using Stacks

  • State "DONE" from "TODO" [2018-03-27 Tue 22:44]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
type MyQueue struct {
ss *Stack
hs *Stack
}

/** Initialize your data structure here. */
func Constructor() MyQueue {
return MyQueue{
ss: New(),
hs: New(),
}
}

/** Push element x to the back of queue. */
func (this *MyQueue) Push(x int) {
for !this.ss.Empty() {
this.hs.Push(this.ss.Pop())
}
this.ss.Push(x)
for !this.hs.Empty() {
this.ss.Push(this.hs.Pop())
}
}

/** Removes the element from in front of queue and returns that element. */
func (this *MyQueue) Pop() int {
return this.ss.Pop().(int)
}

/** Get the front element. */
func (this *MyQueue) Peek() int {
return this.ss.Top().(int)
}

/** Returns whether the queue is empty. */
func (this *MyQueue) Empty() bool {
return this.ss.Empty()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package main



func main() {
q := Constructor()
q.Push(1)
q.Push(2)
q.Push(3)
fmt.Println(q.Peek())
fmt.Println(q.Pop())
fmt.Println(q.Peek())
fmt.Println(q.Pop())
q.Push(4)
fmt.Println(q.Peek())
fmt.Println(q.Pop())
fmt.Println(q.Peek())
fmt.Println(q.Pop())
}

5 DONE FIFO 队列

5.1 DONE 实现

  • State "DONE" from [2018-03-27 Tue 17:22]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
type Queue struct {
lst *list.List
}

func New() *Queue {
return &Queue{
lst: list.New(),
}
}

func (q *Queue) Len() int {
return q.lst.Len()
}

func (q *Queue) Empty() bool {
return q.lst.Len() == 0
}

func (q *Queue) Front() interface{} {
front := q.lst.Front()
if front != nil {
return front.Value
} else {
return nil
}
}

func (q *Queue) Peek() interface{} {
return q.Front()
}

func (q *Queue) Push(v interface{}) {
q.lst.PushBack(v)
}

func (q Queue) Back() interface{} {
back := q.lst.Back()
if back != nil {
return back.Value
} else {
return nil
}
}

func (q *Queue) Pop() interface{} {
front := q.lst.Front()
if front != nil {
return q.lst.Remove(front)
} else {
return nil
}
}

5.2 DONE 应用

  • State "DONE" from "TODO" [2018-03-27 Tue 22:44]

5.2.1 DONE Implement Stack using Queues

  • State "DONE" from "TODO" [2018-03-27 Tue 22:44]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
type MyStack struct {
q *Queue
hq *Queue
}

/** Initialize your data structure here. */
func Constructor() MyStack {
return MyStack{
q: New(),
hq: New(),
}
}

/** Push element x onto stack. */
func (this *MyStack) Push(x int) {
for !this.q.Empty() {
this.hq.Push(this.q.Pop())
}
this.q.Push(x)
for !this.hq.Empty() {
this.q.Push(this.hq.Pop())
}
}

/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
return this.q.Pop().(int)
}

/** Get the top element. */
func (this *MyStack) Top() int {
return this.q.Peek().(int)
}

/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
return this.q.Empty()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package main



func main() {
s := Constructor()
s.Push(1)
s.Push(2)
s.Push(3)
fmt.Println(s.Top())
fmt.Println(s.Pop())
fmt.Println(s.Top())
fmt.Println(s.Pop())
s.Push(4)
fmt.Println(s.Top())
fmt.Println(s.Pop())
fmt.Println(s.Top())
fmt.Println(s.Pop())
}

6 DONE 二叉堆

6.1 DONE 实现堆

  • State "DONE" from "TODO" [2018-03-23 Fri 18:10]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
type LessFunc func(int, int) bool

type Heap struct {
nums []int
size int
capacity int
lessFunc LessFunc
}

func parent(i int) int {
return (i - 1) / 2
}

func left(i int) int {
return 2*i + 1
}

func right(i int) int {
return 2*i + 2
}

func NewHeap(nums []int, lessFunc LessFunc) *Heap {
cnums := make([]int, len(nums))
copy(cnums, nums)
h := &Heap{
nums: cnums,
size: len(nums),
capacity: len(nums),
lessFunc: lessFunc,
}

for i := len(nums) / 2; i >= 0; i -= 1 {
h.down(i, len(nums)-1)
}

return h
}

func (h *Heap) down(start, end int) {
p := start
l := left(p)
for {
if l > end {
break
}

if l < end && h.lessFunc(h.nums[l], h.nums[l+1]) {
l += 1
}

if !h.lessFunc(h.nums[p], h.nums[l]) {
break
} else {
h.nums[l], h.nums[p] = h.nums[p], h.nums[l]
p = l
l = left(p)
}
}

return
}

func (h *Heap) up(start, end int) {
p := parent(end)
c := end
for {
if p < start {
break
}

if !h.lessFunc(h.nums[p], h.nums[c]) {
break
} else {
h.nums[c], h.nums[p] = h.nums[p], h.nums[c]
c = p
p = parent(p)
}
}

return
}

func (h *Heap) Push(num int) {
if h.size+1 > h.capacity {
h.capacity *= 2
cnums := make([]int, h.capacity)
copy(cnums, h.nums)
h.nums = cnums
}

h.nums[h.size] = num
h.size += 1
h.up(0, h.size-1)

return
}

func (h *Heap) Pop() (int, error) {
if h.size < 1 {
return 0, errors.New("empty")
}

h.size -= 1
h.nums[h.size], h.nums[0] = h.nums[0], h.nums[h.size]
h.down(0, h.size-1)
return h.nums[h.size], nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main

import (
"fmt"
"errors"
)



func main() {
nums := []int{2, 4, 6, 3, 5, 7, 1, 10, 8, 9}
h := NewHeap(nums, func(a, b int) bool {
if a < b {
return true
} else {
return false
}
})
h.Log()
dn, _ := h.Del()
fmt.Println(dn)
h.Log()
h.Insert(11)
h.Log()
}

6.2 DONE 堆的应用

  • State "DONE" from "TODO" [2018-03-26 Mon 14:07]

6.2.1 DONE Find Median from Data Stream

  • State "DONE" from "TODO" [2018-03-26 Mon 14:07]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
package main

import (
"container/heap"
"fmt"
)

type MyMaxHeap []int

func (h MyMaxHeap) Len() int { return len(h) }
func (h MyMaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MyMaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *MyMaxHeap) Push(e interface{}) {
*h = append(*h, e.(int))
}

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

type MyMinHeap []int

func (h MyMinHeap) Len() int { return len(h) }
func (h MyMinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MyMinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *MyMinHeap) Push(e interface{}) {
*h = append(*h, e.(int))
}

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

type MedianFinder struct {
LH *MyMaxHeap
RH *MyMinHeap
Lsize int
Rsize int
}

/** initialize your data structure here. */
func Constructor() MedianFinder {
return MedianFinder{
LH: &MyMaxHeap{},
RH: &MyMinHeap{},
}
}

func (this *MedianFinder) AddNum(num int) {
if this.Lsize == 0 {
heap.Push(this.LH, num)
this.Lsize += 1
return
}
lnum := heap.Pop(this.LH).(int)

if this.Rsize == 0 {
if num < lnum {
lnum, num = num, lnum
}

heap.Push(this.LH, lnum)
heap.Push(this.RH, num)
this.Rsize += 1
return
}

rnum := heap.Pop(this.RH).(int)
if num < lnum {
lnum, num = num, lnum
}
if rnum < num {
num, rnum = rnum, num
}

if this.Lsize < this.Rsize {
heap.Push(this.LH, lnum)
heap.Push(this.LH, num)
heap.Push(this.RH, rnum)
this.Lsize += 1
} else {
heap.Push(this.LH, lnum)
heap.Push(this.RH, num)
heap.Push(this.RH, rnum)
this.Rsize += 1
}

return
}

func (this *MedianFinder) FindMedian() float64 {
if this.Lsize == this.Rsize {
if this.Lsize == 0 {
return 0.0
} else {
return (float64((*(this.LH))[0]) + float64((*(this.RH))[0]))/2.0
}
}

if this.Lsize > this.Rsize {
return float64((*this.LH)[0])
} else {
return float64((*this.RH)[0])
}
}

func main() {
mf := Constructor()
mf.AddNum(1)
fmt.Println(mf.FindMedian())
mf.AddNum(2)
fmt.Println(mf.FindMedian())
mf.AddNum(3)
fmt.Println(mf.FindMedian())
mf.AddNum(4)
fmt.Println(mf.FindMedian())
}

7 DONE 二项堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
type BinHeapNode struct {
Parent *BinHeapNode
Child *BinHeapNode
Sibling *BinHeapNode
Key int
Degree int
}

type BinHeap struct {
Head *BinHeapNode
}

func MakeBinHeap() *BinHeap {
return &BinHeap{}
}

func BinHeapMinimum(h *BinHeap) *BinHeapNode {
var y *BinHeapNode
x := h.Head
min := math.MaxInt32
for x != nil {
if x.Key < min {
min = x.Key
y = x
}
x = x.Sibling
}

return y
}

func BinLink(y, z *BinHeapNode) {
y.Parent = z
y.Sibling = z.Child
z.Child = y
z.Degree += 1
}

func BinHeapMerge(lh, rh *BinHeap) *BinHeap {
dummyNode := &BinHeapNode{}
dummy := dummyNode
ln, rn := lh.Head, rh.Head
for ln != nil && rn != nil {
if ln.Degree < rn.Degree {
dummy.Sibling = ln
ln = ln.Sibling
} else {
dummy.Sibling = rn
rn = rn.Sibling
}
dummy = dummy.Sibling
}

if ln != nil {
dummy.Sibling = ln
}

if rn != nil {
dummy.Sibling = rn
}

h := MakeBinHeap()
h.Head = dummyNode.Sibling
return h
}

func BinHeapUnion(lh, rh *BinHeap) *BinHeap {
h := BinHeapMerge(lh, rh)
lh.Head, rh.Head = nil, nil
if h == nil {
return h
}

var prev_x *BinHeapNode
x := h.Head
next_x := x.Sibling
for next_x != nil {
if x.Degree != next_x.Degree ||
(next_x.Sibling != nil && next_x.Sibling.Degree == x.Degree) {
prev_x = x
x = next_x
} else if x.Key <= next_x.Key {
x.Sibling = next_x.Sibling
BinLink(next_x, x)
} else {
if prev_x == nil {
h.Head = next_x
} else {
prev_x.Sibling = next_x
}
BinLink(x, next_x)
x = next_x
}

next_x = x.Sibling
}
return h
}

func BinHeapInsert(h *BinHeap, x *BinHeapNode) *BinHeap {
nh := MakeBinHeap()
x.Parent, x.Child, x.Sibling = nil, nil, nil
x.Degree = 0
nh.Head = x
h = BinHeapUnion(h, nh)
return h
}

func BinHeapExtractMin(h *BinHeap) (*BinHeap, *BinHeapNode) {
var y, prev_y, prev_x *BinHeapNode
x := h.Head
min := math.MaxInt32
for x != nil {
if x.Key < min {
min = x.Key
y = x
prev_y = prev_x
}
prev_x = x
x = x.Sibling
}

if prev_y != nil {
prev_y.Sibling = y.Sibling
} else {
h.Head = y.Sibling
}

nh := MakeBinHeap()
x = y.Child
for x != nil {
z := x.Sibling
x.Sibling = nh.Head
nh.Head = x
x = z
}
h = BinHeapUnion(h, nh)

return h, y
}

func BinHeapDecrKey(h *BinHeap, x *BinHeapNode, k int) {
if k > x.Key {
panic("new key is greater than current key")
}

x.Key = k
y := x
z := y.Parent
for z != nil && y.Key < z.Key {
y.Key, z.Key = z.Key, y.Key
y = z
z = y.Parent
}
}

func BinHeapDelete(h *BinHeap, x *BinHeapNode) {
BinHeapDecrKey(h, x, math.MinInt32)
BinHeapExtractMin(h)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package main

import (
"math"
"fmt"
)



func main() {
lh := MakeBinHeap()
x := &BinHeapNode{
Key: 1,
}
y := &BinHeapNode{
Key: 2,
}
z := &BinHeapNode{
Key: 3,
}
w := &BinHeapNode{
Key: 4,
}
lh = BinHeapInsert(lh, x)
lh = BinHeapInsert(lh, y)
lh = BinHeapInsert(lh, z)
lh = BinHeapInsert(lh, w)
lh,_ =BinHeapExtractMin(lh)
fmt.Println(BinHeapMinimum(lh))
}

8 DONE 斐波那契堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
type FibHeapNode struct {
Parent *FibHeapNode
Child *FibHeapNode
Left *FibHeapNode
Right *FibHeapNode
Key int
Degree int
Mark bool
}

type FibHeap struct {
Min *FibHeapNode
Size int
}

func MakeFibHeap() *FibHeap {
return &FibHeap{}
}

func fibHeapNodeRemove(x *FibHeapNode) {
x.Left.Right = x.Right
x.Right.Left = x.Left
}

func fibHeapNodeAdd(T, x *FibHeapNode) {
T.Left.Right = x
x.Left = T.Left
x.Right = T
T.Left = x
}

func fibHeapNodeUnion(lhn, rhn *FibHeapNode) {
lhn.Left.Right = rhn.Left
rhn.Left.Left = lhn.Left
lhn.Left = rhn
rhn.Right = lhn
}

func FibHeapInsert(h *FibHeap, x *FibHeapNode) {
x.Degree = 0
x.Mark = false
x.Parent, x.Child = nil, nil
x.Left, x.Right = x, x

if h.Min == nil {
h.Min = x
} else {
fibHeapNodeAdd(h.Min, x)
}

if h.Min.Key > x.Key {
h.Min = x
}

h.Size += 1
return
}

func FibHeapMinimum(h *FibHeap) *FibHeapNode {
return h.Min
}

func FibHeapUnion(lh, rh *FibHeap) *FibHeap {
h := MakeFibHeap()
h.Min = lh.Min
if h.Min != nil && rh.Min != nil {
fibHeapNodeUnion(h.Min, rh.Min)
} else if h.Min == nil {
h.Min = rh.Min
}

if h.Min != nil && rh.Min != nil && h.Min.Key > rh.Min.Key {
h.Min = rh.Min
}

h.Size = lh.Size + rh.Size
lh.Min, rh.Min = nil, nil
lh.Size, rh.Size = 0, 0

return h
}

func FibHeapMinRemove(h *FibHeap) *FibHeapNode {
min := h.Min
if min == min.Right {
h.Min = nil
} else {
h.Min = min.Right
fibHeapNodeRemove(min)
}

min.Left, min.Right = min, min
return min
}

func FibHeapExtractMin(h *FibHeap) *FibHeapNode {
z := h.Min
if z == nil {
return z
}

x := z.Child
if x != nil {
y := x
for y.Right != x {
y.Parent = nil
y = y.Right
}
y.Parent = nil

fibHeapNodeUnion(h.Min, x)
}
fibHeapNodeRemove(z)
z.Child = nil

if z == z.Right {
h.Min = nil
} else {
h.Min = z.Right
consolidate(h)
}
h.Size -= 1

z.Left, z.Right = z, z
return z
}

func FibHeapLink(h *FibHeap, y, x *FibHeapNode) {
fibHeapNodeRemove(y)

z := x.Child
if z != nil {
fibHeapNodeAdd(z, y)
} else {
x.Child = y
y.Parent = x
}

x.Degree += 1
y.Mark = false
return
}

func consolidate(h *FibHeap) {
d := int(math.Floor(math.Log2(float64(h.Size))) + 1.0)
dArr := make([]*FibHeapNode, d)

for nil != h.Min {
x := FibHeapMinRemove(h)
degree := x.Degree
for dArr[degree] != nil {
y := dArr[degree]
if x.Key > y.Key {
x, y = y, x
}
FibHeapLink(h, y, x)
dArr[degree] = nil
degree += 1
}
dArr[degree] = x
}

h.Min = nil
for i, _ := range dArr {
if dArr[i] != nil {
x := dArr[i]
if h.Min != nil {
fibHeapNodeAdd(h.Min, x)
} else {
h.Min = x
x.Right = x
x.Left = x
}

if h.Min.Key > x.Key {
h.Min = x
}
}
}

return
}

func FibHeapDecrKey(h *FibHeap, x *FibHeapNode, key int) {
if key > x.Key {
panic("new key is greater than current key.")
}

x.Key = key
y := x.Parent
if y != nil && x.Key < y.Key {
cut(h, x, y)
cascadingCut(h, y)
}

if x.Key < h.Min.Key {
h.Min = x
}
return
}

func cut(h *FibHeap, x, y *FibHeapNode) {
fibHeapNodeRemove(x)
renewDegree(y, x.Degree)
if x == x.Right {
y.Child = nil
} else {
y.Child = x.Right
}

x.Left, x.Right = x, x
x.Parent = nil
x.Mark = false
fibHeapNodeAdd(h.Min, x)
return
}

func cascadingCut(h *FibHeap, y *FibHeapNode) {
z := y.Parent
if z != nil {
if y.Mark == false {
y.Mark = true
} else {
cut(h, y, z)
cascadingCut(h, z)
}
}
return
}

func renewDegree(y *FibHeapNode, degree int) {
y.Degree -= degree
if y.Parent != nil {
renewDegree(y.Parent, degree)
}
}

func FibHeapDelete(h *FibHeap, x *FibHeapNode) {
FibHeapDecrKey(h, x, math.MinInt32)
FibHeapExtractMin(h)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package main

import "fmt"
import "math"



func main() {
lh := MakeFibHeap()
x := &FibHeapNode{
Key: 1,
}
y := &FibHeapNode{
Key: 2,
}
z := &FibHeapNode{
Key: 3,
}
w := &FibHeapNode{
Key: 4,
}

FibHeapInsert(lh, x)
FibHeapInsert(lh, y)
FibHeapInsert(lh, z)
FibHeapInsert(lh, w)
fmt.Println(FibHeapMinimum(lh))
fmt.Println(FibHeapExtractMin(lh))
fmt.Println(lh, *y, *z, *w)
FibHeapDecrKey(lh, w, -3)
fmt.Println(FibHeapExtractMin(lh))
fmt.Println(FibHeapMinimum(lh))
}

9 WAITING 二叉查找树

  • State "WAITING" from "TODO" [2018-04-25 Wed 10:29]
    等待被测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
type TreeNode struct {
Parent *TreeNode
Left *TreeNode
Right *TreeNode
Key int
}

type Tree struct {
Root *TreeNode
}

func TreeSearch(x *TreeNode, k int) *TreeNode {
if x == nil || k == x.Key {
return x
}

if k < x.Key {
return TreeSearch(x.Left, k)
} else {
return TreeSearch(x.Right, k)
}
}

func IterativeTreeSearch(x *TreeNode, k int) *TreeNode {
for x != nil && k != x.Key {
if k < x.Key {
x = x.Left
} else {
x = x.Right
}
}

return x
}

func TreeMinimum(x *TreeNode) *TreeNode {
for x.Left != nil {
x = x.Left
}
return x
}

func TreeMaximum(x *TreeNode) *TreeNode {
for x.Right != nil {
x = x.Right
}

return x
}

func TreeSuccessor(x *TreeNode) *TreeNode {
if x.Right != nil {
return TreeMinimum(x.Right)
}

y := x.Parent
for y != nil && x == y.Right {
x = y
y = y.Parent
}

return y
}

func TreePredecessor(x *TreeNode) *TreeNode {
if x.Left != nil {
return TreeMaximum(x.Left)
}

y := x.Parent
for y != nil && x == y.Left {
x = y
y = y.Parent
}

return y
}

func TreeInsert(T *Tree, z *TreeNode) {
var y *TreeNode
x := T.Root

for x != nil {
y = x
if z.Key < x.Key {
x = x.Left
} else {
x = x.Right
}
}

z.Parent = y
if y == nil {
T.Root = z
} else {
if z.Key < y.Key {
y.Left = z
} else {
y.Right = z
}
}

return
}

func TreeDelete(T *Tree, z *TreeNode) {
var x, y *TreeNode
if z.Left == nil || z.Right == nil {
y = z
} else {
y = TreeSuccessor(z)
}

if y.Left != nil {
x = y.Left
} else {
x = y.Right
}

if x != nil {
x.Parent = y.Parent
}

if y.Parent == nil {
T.Root = x
} else {
if y == y.Parent.Left {
y.Parent.Left = x
} else {
y.Parent.Right = x
}
}

if y != z {
z.Key = y.Key
}

return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package main

import (
"fmt"
"math/rand"
)



func main() {
t := &Tree{}
numM := make(map[int]bool)
cn := 0
for cn < 50 {
num := rand.Intn(1000)
if !numM[num] {
cn += 1
numM[num] = true
tn := &TreeNode{
Key: num,
}
TreeInsert(t, tn)
}
}
fmt.Println(TreeMinimum(t.Root))
fmt.Println(TreeMaximum(t.Root))
}

10 TODO 红黑树

#+NAME left-leaning-red-black-tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
const (
RED = true
BLACK = false
)

const (
BST = iota
TD234
BU23
)

type Node struct {
Left *Node
Right *Node
Color bool
Key int
Val interface{}
}

func isRed(x *Node) bool {
if x == nil {
return false
}

return x.Color == RED
}

type LLRBTree struct {
Root *Node
}

func (t *LLRBTree) Get(key int) interface{} {
x := t.Root
for x != nil {
if key < x.Key {
x = x.Left
} else if key > x.Key {
x = x.Right
} else {
return x.Val
}
}

return nil
}

// Make a right-leaning 3-node lean to the left.
func rotateLeft(h *Node) *Node {
x := h.Right
h.Right = x.Left
x.Left = h
x.Color = x.Left.Color
x.Left.Color = RED
return x
}

// Make a left-leaning 3-node lean to the right.
func rotateRight(h *Node) *Node {
x := h.Left
h.Left = x.Right
x.Right = h
x.Color = x.Right.Color
x.Right.Color = RED
return x
}

func colorFlip(x *Node) {
x.Color = !x.Color
x.Left.Color = !x.Left.Color
x.Right.Color = !x.Right.Color
}

func insert(h *Node, key int, val interface{}) {
// insert at the bottom
if h == nil {
return &Node{Key: key, Val: val}
}

// split 4-nodes on the way down
if isRed(h.left) && isRed(h.right) {
colorFlip(h)
}

// standard BST insert code
if key < h.Key {
h.Left = insert(h.Left, key, val)
} else if key > h.Key {
h.Right = insert(h.Right, key, val)
} else {
h.Val = val
}

// fix right-leaning reds on the way up
if isRed(h.Right) {
h = rotateLeft(h)
}

// fix two reds in a row on the way up
if isRed(h.Left) && isRed(h.Left.Left) {
h = rotateRight(h)
}

return h
}

func (t *LLRBTree) Put(key int, val interface{}) {
t.Root = insert(t.Root, key, val)
root.Color = BLACK
return
}

func fixUp(h *Node) *Node {
// fix right-leaning reds on the way up
if isRed(h.Right) {
h = rotateLeft(h)
}

// fix two reds in a row on the way up
if isRed(h.Left) && isRed(h.Left.Left) {
h = rotateRight(h)
}

// split 4-nodes on the way down
if isRed(h.Left) && isRed(h.Right) {
colorFlip(h)
}

return h
}

// Assuming that h is red and both h.right and h.right.left
// are black, make h.right or one of its children red.
func moveRedRight(h *Node) *Node {
colorFlip(h)
if isRed(h.Left.Left) {
h = rotateRight(h)
colorFlip(h)
}
return h
}

func deleteMax(h *Node) *Node {
// lean 3-nodes to the right
if isRed(h.Left) {
h = rotateRight(h)
}

// remove node on bottom level
if h.Right == nil {
return nil
}

// push red link down if necessary
if !isRed(h.Right) && !isRed(h.Right.Left) {
h = moveRedRight(h)
}

// move down one level
h.Right = deleteMax(h.Right)

// fix right-leaning red links and eliminate 4-nodes on the way up
return fixUp(h)
}

func (t *LLRBTree) deleteMax() {
t.Root = deleteMax(t.Root)
t.Root.Color = BLACK
}

// Assuming that h is red and both h.left and h.left.left
// are black, make h.left or one of its children red.
func moveRedLeft(h *Node) *Node {
colorFlip(h)
if isRed(h.Right.Left) {
h.Right = rotateRight(h.Right)
h = rotateLeft(h)
colorFlip(h)
}

return h
}

func deleteMin(h *Node) *Node {
// remove node on bottom level
if h.Left == nil {
return nil
}

// push red link down if necessary
if !isRed(h.Left) && !isRed(h.Left.Left) {
h = moveRedLeft(h)
}

// move down one level
h.Left = deleteMin(h.Left)

// fix right-leaning red links and eliminate 4-nodes on the way up
return fixUp(h)
}

func (t *LLRBTree) deleteMin() {
t.Root = deleteMin(t.Root)
t.Root.Color = BLACK
}

func (t *LLRBTree) min() *Node {
x := t.Root
y := x
for x != nil {
y = x
x = x.Left
}

return y
}

func del(h *Node, key int) *Node {
if key < h.Key { // LEFT
// push red link down if necessary
if !isRed(h.Left) && !isRed(h.Left.Left) {
h = moveRedLeft(h)
}

// move down(left)
h.Left = del(h.Left, key)
} else { // RIGHT or EQUAL
// lean 3-nodes to the right
if isRed(h.Left) {
h = rotateRight(h)
}

// EQUAL(at bottom) delete node
if cmp == 0 && h.Right == nil {
return nil
}

// push red right if necessary
if !isRed(h.Right) && !isRed(h.Right.Left) {
h = moveRedRight(h)
}

if key == h.Key {
successor := t.min(h.Right)
h.Key = successor.Key
h.Val = successor.Val
h.right = deleteMin(h.Right)
} else {
// move down(right)
h.Right = del(h.Right, key)
}
}

return fixUp(h)
}

func (t *LLRBTree) Delete(key int) {
t.Root = del(t.Root, key)
t.Root.Color = BLACK
return
}

11 TODO B树

12 DONE

  • State "DONE" from "TODO" [2018-04-15 Sun 16:49]

12.1 DONE 定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
type ArcNode struct {
AdjVex int
Info interface{}
}

type VNode struct {
Data interface{}
ArcNodeArr []ArcNode
}

type AdjList []VNode

func MakeDot(vertices AdjList) string {
var ans string
for u, _ := range vertices {
for i := 0; i < len(vertices[u].ArcNodeArr); i += 1 {
v := vertices[u].ArcNodeArr[i].AdjVex
ans += fmt.Sprintf("%v -> %v;\n", u, v)
}
}
return ans
}

func makeDotScb(scb [][]int, vertices AdjList) string {
var clusters string
for i, _ := range scb {
arr := scb[i]
var node_str string
for _, u := range arr {
node_str += fmt.Sprintf("%v; ", u)
}
cluster_str := fmt.Sprintf("subgraph \"cluster-%v\" {\n\t label=\"scb-%v\";\n\t %v \n}\n", i, i, node_str)
clusters += cluster_str
}
return MakeDot(vertices) + clusters
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package main

import "fmt"



func main() {
vertices := AdjList{
VNode{
Data: 0,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1},
ArcNode{AdjVex: 2},
},
},
VNode{
Data: 1,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 2},
ArcNode{AdjVex: 3},
},
},
VNode{
Data: 2,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1},
},
},
VNode{
Data: 3,
ArcNodeArr: []ArcNode{},
},
VNode{
Data: 4,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 2},
ArcNode{AdjVex: 3},
},
},
}

fmt.Println("{rank=same; 2 3;}\n"+ MakeDot(vertices))
}
digraph {
 $input
}
1
2
3
4
5
6
7
type Edge struct {
Start int
End int
Weight int
}

type EdgeList []Edge

12.2 DONE 广度优先搜索(BFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func bfs(vertices AdjList, u int, visitFunc func(interface{})) {
q := New()
visited := make([]int, len(vertices))

visitFunc(vertices[u].Data)
q.Push(u)
visited[u] = 1

for !q.Empty() {
v := q.Pop().(int)

for j := 0; j < len(vertices[v].ArcNodeArr); j += 1 {
if visited[vertices[v].ArcNodeArr[j].AdjVex] != 1 {
visitFunc(vertices[v].ArcNodeArr[j].AdjVex)
q.Push(vertices[v].ArcNodeArr[j].AdjVex)
visited[vertices[v].ArcNodeArr[j].AdjVex] = 1
}
}
}

return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package main

import "fmt"
import "container/list"





func main() {
vertices := AdjList{
VNode{
Data: 1,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1},
ArcNode{AdjVex: 2},
},
},
VNode{
Data: 2,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 2},
ArcNode{AdjVex: 3},
},
},
VNode{
Data: 3,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1},
ArcNode{AdjVex: 2},
},
},
VNode{
Data: 4,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0},
},
},
VNode{
Data: 5,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 2},
ArcNode{AdjVex: 3},
},
},
}

bfs(vertices, 0, func(data interface{}) {
fmt.Println(data)
})
}

12.3 DONE 深度优先搜索(DFS)

  • State "DONE" from "TODO" [2018-04-09 Mon 11:52]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func dfs(vertices AdjList, visitFunc func(interface{})) {
visited := make([]int, len(vertices))

for u := 0; u < len(vertices); u += 1 {
if visited[u] != 1 {
dfsVisit(vertices, u, visited, visitFunc)
}
}
return
}

func dfsVisit(vertices AdjList, u int, visited []int, visitFunc func(interface{})) {
visited[u] = 1
visitFunc(vertices[u].Data)
for i := 0; i < len(vertices[u].ArcNodeArr); i += 1 {
v := vertices[u].ArcNodeArr[i].AdjVex
if visited[v] != 1 {
dfsVisit(vertices, v, visited, visitFunc)
}
}
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package main

import "fmt"




func main() {
vertices := AdjList{
VNode{
Data: 1,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1},
ArcNode{AdjVex: 2},
},
},
VNode{
Data: 2,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 2},
ArcNode{AdjVex: 3},
},
},
VNode{
Data: 3,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1},
ArcNode{AdjVex: 2},
},
},
VNode{
Data: 4,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0},
},
},
VNode{
Data: 5,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 2},
ArcNode{AdjVex: 3},
},
},
}

dfs(vertices, func(data interface{}) {
fmt.Println(data)
})
}

12.4 DONE Union-Find算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func hasCycle(edges EdgeList, vexNum int) bool {
var findFunc func([]int, int) int
findFunc = func(parent []int, i int) int {
if parent[i] == -1 {
return i
}
return findFunc(parent, parent[i])
}

unionFunc := func(parent []int, i, j int) {
iSet := findFunc(parent, i)
jSet := findFunc(parent, j)
parent[iSet] = jSet
}

parent := make([]int, vexNum)
for i, _ := range parent {
parent[i] = -1
}

for _, edge := range edges {
i := findFunc(parent, edge.Start)
j := findFunc(parent, edge.End)

if i == j {
return true
}

unionFunc(parent, i, j)
}

return false
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package main

import "fmt"





func main() {
edges := []Edge{
Edge{Start: 0, End: 1},
Edge{Start: 1, End: 2},
Edge{Start: 2, End: 3},
}

fmt.Println(hasCycle(edges, 4))
}

12.5 DONE 拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
func TopologicalSort(vertices AdjList) ([]int, bool) {
q := New()
visited := make([]int, len(vertices))
indegree := make([]int, len(vertices))

for u := 0; u < len(vertices); u += 1 {
if visited[u] != 1 {
q.Push(u)
visited[u] = 1
for !q.Empty() {
v := q.Pop().(int)
for j := 0; j < len(vertices[v].ArcNodeArr); j += 1 {
indegree[vertices[v].ArcNodeArr[j].AdjVex] += 1
if visited[vertices[v].ArcNodeArr[j].AdjVex] != 1 {
q.Push(vertices[v].ArcNodeArr[j].AdjVex)
visited[vertices[v].ArcNodeArr[j].AdjVex] = 1
}
}
}
}
}

ans := make([]int, 0)
q = New()
for u := 0; u < len(vertices); u += 1 {
if indegree[u] == 0 {
q.Push(u)
}
}

for !q.Empty() {
u := q.Pop().(int)
ans = append(ans, u)

for j := 0; j < len(vertices[u].ArcNodeArr); j += 1 {
v := vertices[u].ArcNodeArr[j].AdjVex
indegree[v] -= 1
if indegree[v] == 0 {
q.Push(v)
}
}
}

return ans, len(vertices) == len(ans)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package main

import "fmt"
import "container/list"





func main() {
vertices := AdjList{
VNode{
Data: 0,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 4},
},
},
VNode{
Data: 1,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0},
},
},
VNode{
Data: 2,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0},
ArcNode{AdjVex: 3},
},
},
VNode{
Data: 3,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1},
},
},
VNode{
Data: 4,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0},
ArcNode{AdjVex: 1},
},
},
VNode{
Data: 5,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0},
ArcNode{AdjVex: 2},
},
},
}

fmt.Println(TopologicalSort(vertices))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
func TopologicalSort(vertices AdjList) ([]int, bool) {
s := New()
visited := make([]int, len(vertices))
father := make([]int, len(vertices))
for i, _ := range father {
father[i] = -1
}

var dfsVisit func(int)
dfsVisit = func(u int) {
visited[u] = 1
for i := 0; i < len(vertices[u].ArcNodeArr); i += 1 {
v := vertices[u].ArcNodeArr[i].AdjVex
if visited[v] == 1 {
tmp := u
for tmp != v && tmp > 0 {
fmt.Print(tmp, "->")
tmp = father[tmp]
}
fmt.Println(tmp)
} else if visited[v] != 2 {
father[v] = u
dfsVisit(v)
}
}
visited[u] = 2
s.Push(u)
return
}

for u := 0; u < len(vertices); u += 1 {
if visited[u] != 1 {
dfsVisit(u)
}
}

ans := make([]int, 0)
for !s.Empty() {
ans = append(ans, s.Pop().(int))
}

return ans, true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
     package main

import "fmt"
import "container/list"





func main() {
vertices := AdjList{
VNode{
Data: 0,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 4},
},
},
VNode{
Data: 1,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0},
},
},
VNode{
Data: 2,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0},
ArcNode{AdjVex: 3},
},
},
VNode{
Data: 3,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1},
},
},
VNode{
Data: 4,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0},
ArcNode{AdjVex: 1},
},
},
VNode{
Data: 5,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0},
ArcNode{AdjVex: 2},
},
},
}

fmt.Println(TopologicalSort(vertices))
}

12.6 DONE 强连通分支

  • State "DONE" from "TODO" [2018-04-15 Sun 16:49]

12.6.1 DONE Kosaraju算法

  • State "DONE" from "TODO" [2018-04-15 Sun 11:26]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
func reverse(vertices AdjList) AdjList {
rv := make(AdjList, len(vertices))
for u := 0; u < len(rv); u += 1 {
rv[u].Data = u
rv[u].ArcNodeArr = make([]ArcNode, 0)
}

for u := 0; u < len(vertices); u += 1 {
for j := 0; j < len(vertices[u].ArcNodeArr); j += 1 {
v := vertices[u].ArcNodeArr[j].AdjVex
rv[v].ArcNodeArr = append(
rv[v].ArcNodeArr,
ArcNode{
AdjVex: u,
})
}
}

return rv
}

func kosaraju(vertices AdjList) [][]int {
visited := make([]int, len(vertices))
dsfArr := make([]int, 0)
finArr := make([]int, 0)
var dfs func(AdjList, int)
dfs = func(vertices AdjList, u int) {
visited[u] = 1
dsfArr = append(dsfArr, u)
for i := 0; i < len(vertices[u].ArcNodeArr); i += 1 {
v := vertices[u].ArcNodeArr[i].AdjVex
if visited[v] != 1 {
dfs(vertices, v)
}
}
finArr = append(finArr, u)
}

for u := 0; u < len(vertices); u += 1 {
if visited[u] != 1 {
dfs(vertices, u)
}
}

rv := reverse(vertices)
visited = make([]int, len(vertices))
c_finArr := finArr
ans := make([][]int, 0)
for i := len(c_finArr) - 1; i >= 0; i -= 1 {
u := c_finArr[i]
if visited[u] != 1 {
dsfArr = make([]int, 0)
dfs(rv, u)
ans = append(ans, dsfArr)
}
}

return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package main

import "fmt"




func main() {
vertices := AdjList{
VNode{
Data: 0,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1},
ArcNode{AdjVex: 2},
},
},
VNode{
Data: 1,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 3},
},
},
VNode{
Data: 2,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 3},
ArcNode{AdjVex: 4},
},
},
VNode{
Data: 3,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0},
ArcNode{AdjVex: 5},
},
},
VNode{
Data: 4,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 5},
},
},
VNode{
Data: 5,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 4},
},
},
}

fmt.Println(makeDotScb(kosaraju(vertices), vertices))
}
digraph G {
$input
}

12.6.2 DONE Tarjan算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
func tarjan(vertices AdjList) [][]int {
dsfArr := make([]int, len(vertices))
lowArr := make([]int, len(vertices))
inStack := make([]bool, len(vertices))
for i, _ := range dsfArr {
dsfArr[i] = -1
}

index := 0
s := New()
ans := make([][]int, 0)

var strongconnect func(int)
strongconnect = func(u int) {
dsfArr[u] = index
lowArr[u] = index
index += 1
inStack[u] = true
s.Push(u)

for i := 0; i < len(vertices[u].ArcNodeArr); i += 1 {
v := vertices[u].ArcNodeArr[i].AdjVex
if dsfArr[v] == -1 {
strongconnect(v)
if lowArr[v] < lowArr[u] {
lowArr[u] = lowArr[v]
}
} else if inStack[v] && lowArr[v] < lowArr[u] {
lowArr[u] = lowArr[v]
}
}

if dsfArr[u] == lowArr[u] {
arr := make([]int, 0)
v := s.Pop().(int)
for u != v {
inStack[v] = false
arr = append(arr, v)
v = s.Pop().(int)
}
inStack[v] = false
arr = append(arr, v)
ans = append(ans, arr)
}
}

for u := 0; u < len(vertices); u += 1 {
if dsfArr[u] == -1 {
strongconnect(u)
}
}

return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 package main

import "fmt"
import "container/list"







func main() {
vertices := AdjList{
VNode{
Data: 0,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1},
ArcNode{AdjVex: 2},
},
},
VNode{
Data: 1,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 3},
},
},
VNode{
Data: 2,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 3},
ArcNode{AdjVex: 4},
},
},
VNode{
Data: 3,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0},
ArcNode{AdjVex: 5},
},
},
VNode{
Data: 4,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 5},
},
},
VNode{
Data: 5,
ArcNodeArr: []ArcNode{},
},
}

fmt.Println(makeDotScb(tarjan(vertices), vertices))
}
digraph G {
$input
}

12.6.3 DONE Gabow算法

  • State "DONE" from "TODO" [2018-04-15 Sun 16:49]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
func gabow(vertices AdjList) [][]int {
dsfArr := make([]int, len(vertices))
partArr := make([]int, len(vertices))
for i, _ := range dsfArr {
dsfArr[i] = -1
partArr[i] = -1
}
partIndex := 0
index := 0
ps := New()
rs := New()

var strongconnect func(int)
strongconnect = func(u int) {
dsfArr[u] = index
index += 1
ps.Push(u)
rs.Push(u)

for i := 0; i < len(vertices[u].ArcNodeArr); i += 1 {
v := vertices[u].ArcNodeArr[i].AdjVex
if dsfArr[v] == -1 {
strongconnect(v)
} else if partArr[v] == -1 {
for dsfArr[rs.Top().(int)] > dsfArr[v] {
rs.Pop()
}
}
}

if u == rs.Top().(int) {
rs.Pop()
partIndex += 1
v := ps.Pop().(int)
for u != v {
partArr[v] = partIndex
v = ps.Pop().(int)
}
partArr[v] = partIndex
}
}

for u := 0; u < len(vertices); u += 1 {
if dsfArr[u] == -1 {
strongconnect(u)
}
}

ans := make([][]int, 0)
for i := 1; i < partIndex+1; i += 1 {
arr := make([]int, 0)
for j := 0; j < len(partArr); j += 1 {
if partArr[j] == i {
arr = append(arr, j)
}
}
ans = append(ans, arr)
}

return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package main

import "fmt"
import "container/list"







func main() {
vertices := AdjList{
VNode{
Data: 0,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1},
ArcNode{AdjVex: 2},
},
},
VNode{
Data: 1,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 3},
},
},
VNode{
Data: 2,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 3},
ArcNode{AdjVex: 4},
},
},
VNode{
Data: 3,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0},
ArcNode{AdjVex: 5},
},
},
VNode{
Data: 4,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 5},
},
},
VNode{
Data: 5,
ArcNodeArr: []ArcNode{},
},
}

fmt.Println(makeDotScb(gabow(vertices), vertices))
}
digraph G {
$input
}

12.7 DONE 关键路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
func CriticalPath(vertices AdjList) []int {
q := New()
visited := make([]int, len(vertices))
indegree := make([]int, len(vertices))
earlyStart := make([]int, len(vertices))
lateStart := make([]int, len(vertices))

for u := 0; u < len(vertices); u += 1 {
if visited[u] != 1 {
q.Push(u)
visited[u] = 1
for !q.Empty() {
v := q.Pop().(int)
for j := 0; j < len(vertices[v].ArcNodeArr); j += 1 {
w := vertices[v].ArcNodeArr[j].AdjVex
weight := vertices[v].ArcNodeArr[j].Info.(int)
indegree[w] += 1

if earlyStart[v]+weight > earlyStart[w] {
earlyStart[w] = earlyStart[v] + weight
}

if visited[w] != 1 {
q.Push(w)
visited[w] = 1
}
}
}
}
}

tsArr := make([]int, 0)
q = New()
for u := 0; u < len(vertices); u += 1 {
if indegree[u] == 0 {
q.Push(u)
}
}

for !q.Empty() {
u := q.Pop().(int)
tsArr = append(tsArr, u)

for j := 0; j < len(vertices[u].ArcNodeArr); j += 1 {
v := vertices[u].ArcNodeArr[j].AdjVex
indegree[v] -= 1
if indegree[v] == 0 {
q.Push(v)
}
}
}

for i, _ := range lateStart {
lateStart[i] = -1
}
e := tsArr[len(tsArr)-1]
lateStart[e] = earlyStart[e]

for i := len(tsArr) - 2; i >= 0; i -= 1 {
u := tsArr[i]
for j := 0; j < len(vertices[u].ArcNodeArr); j += 1 {
v := vertices[u].ArcNodeArr[j].AdjVex
weight := vertices[u].ArcNodeArr[j].Info.(int)
if lateStart[u] == -1 || lateStart[v]-weight < lateStart[u] {
lateStart[u] = lateStart[v] - weight
}
}
}

ans := make([]int, 0)
for i := 0; i < len(vertices); i += 1 {
if earlyStart[i] == lateStart[i] {
ans = append(ans, i)
}
}

return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package main

import "fmt"
import "container/list"





func main() {
vertices := AdjList{
VNode{
Data: 0,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1, Info: 3},
ArcNode{AdjVex: 2, Info: 4},
},
},
VNode{
Data: 1,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 3, Info: 5},
ArcNode{AdjVex: 4, Info: 6},
},
},
VNode{
Data: 2,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 3, Info: 8},
ArcNode{AdjVex: 5, Info: 7},
},
},
VNode{
Data: 3,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 4, Info: 3},
},
},
VNode{
Data: 4,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 6, Info: 9},
ArcNode{AdjVex: 7, Info: 4},
},
},
VNode{
Data: 5,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 7, Info: 6},
},
},
VNode{
Data: 6,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 9, Info: 2},
},
},
VNode{
Data: 7,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 8, Info: 5},
},
},
VNode{
Data: 8,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 9, Info: 3},
},
},
VNode{
Data: 9,
ArcNodeArr: []ArcNode{},
},
}

fmt.Println(CriticalPath(vertices))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
func CriticalPath(vertices AdjList) ([]int, bool) {
s := New()
var bCycle bool
visited := make([]int, len(vertices))
earlyStart := make([]int, len(vertices))
lateStart := make([]int, len(vertices))

var dfsVisit func(int)
dfsVisit = func(u int) {
visited[u] = 1
for i := 0; i < len(vertices[u].ArcNodeArr); i += 1 {
v := vertices[u].ArcNodeArr[i].AdjVex
weight := vertices[u].ArcNodeArr[i].Info.(int)
if earlyStart[u]+weight > earlyStart[v] {
earlyStart[v] = earlyStart[u] + weight
}
if visited[v] == 1 {
bCycle = true
return
} else if visited[v] != 2 {
dfsVisit(v)
}
}
visited[u] = 2
s.Push(u)
return
}

for u := 0; u < len(vertices); u += 1 {
if visited[u] != 1 {
dfsVisit(u)
}
}

for i, _ := range lateStart {
lateStart[i] = -1
}
e := s.Pop().(int)
lateStart[e] = earlyStart[e]

for !s.Empty() {
u := s.Pop().(int)
for j := 0; j < len(vertices[u].ArcNodeArr); j += 1 {
v := vertices[u].ArcNodeArr[j].AdjVex
weight := vertices[u].ArcNodeArr[j].Info.(int)
if lateStart[u] == -1 || lateStart[v]-weight < lateStart[u] {
lateStart[u] = lateStart[v] - weight
}
}
}

ans := make([]int, 0)
for i := 0; i < len(vertices); i += 1 {
if earlyStart[i] == lateStart[i] {
ans = append(ans, i)
}
}

return ans, bCycle
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
package main

import "fmt"
import "container/list"





func main() {
vertices := AdjList{
VNode{
Data: 0,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1, Info: 3},
ArcNode{AdjVex: 2, Info: 4},
},
},
VNode{
Data: 1,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 3, Info: 5},
ArcNode{AdjVex: 4, Info: 6},
},
},
VNode{
Data: 2,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 3, Info: 8},
ArcNode{AdjVex: 5, Info: 7},
},
},
VNode{
Data: 3,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 4, Info: 3},
},
},
VNode{
Data: 4,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 6, Info: 9},
ArcNode{AdjVex: 7, Info: 4},
},
},
VNode{
Data: 5,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 7, Info: 6},
},
},
VNode{
Data: 6,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 9, Info: 2},
},
},
VNode{
Data: 7,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 8, Info: 5},
},
},
VNode{
Data: 8,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 9, Info: 3},
},
},
VNode{
Data: 9,
ArcNodeArr: []ArcNode{},
},
}

fmt.Println(CriticalPath(vertices))
}

12.8 DONE 最小生成树

12.8.1 DONE Prim算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
func mstPrim(vertices AdjList, s int) EdgeList {
visited := make([]int, len(vertices))
dist := make([]int, len(vertices))
parent := make([]int, len(vertices))
for i, _ := range dist {
dist[i] = math.MaxInt32
parent[i] = -1
}
dist[s] = 0

for i := 0; i < len(vertices)-1; i += 1 {
minDist := math.MaxInt32
minIndex := -1
for j := 0; j < len(dist); j += 1 {
if visited[j] == 0 && dist[j] < minDist {
minDist = dist[j]
minIndex = j
}
}

visited[minIndex] = 1

u := minIndex
for j := 0; j < len(vertices[u].ArcNodeArr); j += 1 {
v := vertices[u].ArcNodeArr[j].AdjVex
if visited[v] == 0 {
d := vertices[u].ArcNodeArr[j].Info.(int)
if d < dist[v] {
dist[v] = d
parent[v] = u
}
}
}
}

edges := make(EdgeList, 0)
for i := 0; i < len(parent); i += 1 {
if parent[i] != -1 {
edge := Edge{
Start: i,
End: parent[i],
Weight: dist[i],
}
edges = append(edges, edge)
}
}

return edges
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package main

import "fmt"
import "math"







func main() {
vertices := AdjList{
VNode{
Data: 0,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 1, Info: 3},
ArcNode{AdjVex: 2, Info: 4},
ArcNode{AdjVex: 3, Info: 5},
},
},
VNode{
Data: 1,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0, Info: 3},
ArcNode{AdjVex: 2, Info: 5},
ArcNode{AdjVex: 3, Info: 6},
},
},
VNode{
Data: 2,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0, Info: 4},
ArcNode{AdjVex: 1, Info: 5},
ArcNode{AdjVex: 3, Info: 8},
},
},
VNode{
Data: 3,
ArcNodeArr: []ArcNode{
ArcNode{AdjVex: 0, Info: 5},
ArcNode{AdjVex: 1, Info: 6},
ArcNode{AdjVex: 2, Info: 8},
},
},
}

fmt.Println(mstPrim(vertices, 0))
}

12.8.2 DONE Kruskal算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
func mstKruskal(edges EdgeList, vexNum int) EdgeList {
var findFunc func([]int, int) int
findFunc = func(parent []int, i int) int {
if parent[i] == -1 {
return i
}
return findFunc(parent, parent[i])
}

unionFunc := func(parent []int, i, j int) {
iSet := findFunc(parent, i)
jSet := findFunc(parent, j)
parent[iSet] = jSet
}

sort.Slice(edges, func(i, j int) bool {
return edges[i].Weight <= edges[j].Weight
})

parent := make([]int, vexNum)
for i, _ := range parent {
parent[i] = -1
}

vcn := 0
ans := make(EdgeList, 0)
for _, edge := range edges {
u := findFunc(parent, edge.Start)
v := findFunc(parent, edge.End)

if u == v {
continue
}

unionFunc(parent, u, v)
ans = append(ans, edge)
vcn += 1
if vcn == vexNum-1 {
break
}
}

return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
package main

import "fmt"
import "sort"





func main() {
edges := []Edge{
Edge{Start: 0, End: 1, Weight: 4},
Edge{Start: 0, End: 7, Weight: 8},
Edge{Start: 1, End: 2, Weight: 8},
Edge{Start: 1, End: 7, Weight: 11},
Edge{Start: 2, End: 3, Weight: 7},
Edge{Start: 2, End: 5, Weight: 4},
Edge{Start: 8, End: 2, Weight: 2},
Edge{Start: 3, End: 4, Weight: 9},
Edge{Start: 3, End: 5, Weight: 14},
Edge{Start: 5, End: 4, Weight: 10},
Edge{Start: 6, End: 5, Weight: 2},
Edge{Start: 8, End: 6, Weight: 6},
Edge{Start: 7, End: 6, Weight: 1},
Edge{Start: 7, End: 8, Weight: 7},
}

fmt.Println(mstKruskal(edges, 9))
}

12.9 DONE 最短路径

12.9.1 DONE 单源最短路径

  • State "DONE" from "TODO" [2018-04-11 Wed 22:41]
  1. DONE Dijkstra算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    func dijkstra(vertices AdjList, s int) []int {
    visited := make([]bool, len(vertices))
    dis := make([]int, len(vertices))
    for i, _ := range dis {
    dis[i] = math.MaxInt32
    }
    dis[s] = 0

    for {
    min := math.MaxInt32
    t := -1
    for u := 0; u < len(vertices); u += 1 {
    if !visited[u] && dis[u] < min {
    min = dis[u]
    t = u
    }
    }

    if t == -1 {
    break
    }
    visited[t] = true

    for j := 0; j < len(vertices[t].ArcNodeArr); j += 1 {
    v := vertices[t].ArcNodeArr[j].AdjVex
    d := vertices[t].ArcNodeArr[j].Info.(int)

    if !visited[v] && dis[t]+d < dis[v] {
    dis[v] = dis[t] + d
    }
    }

    }

    return dis
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    package main

    import "fmt"
    import "math"




    func main() {
    vertices := AdjList{
    VNode{
    Data: 0,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 1, Info: 10},
    ArcNode{AdjVex: 2, Info: 5},
    },
    },
    VNode{
    Data: 1,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 2, Info: 2},
    ArcNode{AdjVex: 3, Info: 1},
    },
    },
    VNode{
    Data: 2,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 1, Info: 3},
    ArcNode{AdjVex: 3, Info: 9},
    ArcNode{AdjVex: 4, Info: 2},
    },
    },
    VNode{
    Data: 3,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 4, Info: 4},
    },
    },
    VNode{
    Data: 4,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 0, Info: 7},
    ArcNode{AdjVex: 3, Info: 6},
    },
    },
    }

    fmt.Println(dijkstra(vertices, 0))
    }
  2. DONE Bellman–Ford算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    func bellmanFord(vertices AdjList, s int) ([]int, bool) {
    dist := make([]int, len(vertices))
    for i, _ := range dist {
    dist[i] = math.MaxInt32
    }
    dist[s] = 0

    for i := 1; i < len(vertices); i += 1 {
    for u := 0; u < len(vertices); u += 1 {
    for j := 0; j < len(vertices[u].ArcNodeArr); j += 1 {
    v := vertices[u].ArcNodeArr[j].AdjVex
    d := vertices[u].ArcNodeArr[j].Info.(int)
    if dist[u]+d < dist[v] {
    dist[v] = dist[u] + d
    }
    }
    }
    }

    for u := 0; u < len(vertices); u += 1 {
    for j := 0; j < len(vertices[u].ArcNodeArr); j += 1 {
    v := vertices[u].ArcNodeArr[j].AdjVex
    d := vertices[u].ArcNodeArr[j].Info.(int)
    if dist[u]+d < dist[v] {
    return dist, true
    }
    }
    }

    return dist, false
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    package main

    import "fmt"
    import "math"





    func main() {
    vertices := AdjList{
    VNode{
    Data: 0,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 1, Info: 10},
    ArcNode{AdjVex: 2, Info: 5},
    },
    },
    VNode{
    Data: 1,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 2, Info: 2},
    ArcNode{AdjVex: 3, Info: 1},
    },
    },
    VNode{
    Data: 2,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 1, Info: 3},
    ArcNode{AdjVex: 3, Info: 9},
    ArcNode{AdjVex: 4, Info: 2},
    },
    },
    VNode{
    Data: 3,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 4, Info: 4},
    },
    },
    VNode{
    Data: 4,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 0, Info: 7},
    ArcNode{AdjVex: 3, Info: 6},
    },
    },
    }

    fmt.Println(bellmanFord(vertices, 0))
    }

12.9.2 DONE 每对顶点间的最短路径

  • State "DONE" from "TODO" [2018-04-11 Wed 22:43]
  1. DONE Floyd-Warshall算法
    • State "DONE" from "TODO" [2018-04-11 Wed 17:18]
    1. DONE 原理描述
      • State "DONE" from "TODO" [2018-04-11 Wed 16:47]

      Floyd-Warshall算法的原理是动态规划。 设 D{i,j,k}为从 i到 j的只以 (1..k)集合中的节点为中间节点的最短路径的长度。

      若最短路径经过点k,则 D{i,j,k}=D{i,k,k-1}+D{k,j,k-1}; 若最短路径不经过点k,则 D{i,j,k}=D{i,j,k-1}。 因此, D{i,j,k}=min(D{i,j,k-1},D{i,k,k-1}+D{k,j,k-1})。

      在实际算法中,为了节约空间,可以直接在原来空间上进行迭代,这样空间可降至二维。

    2. DONE 算法实现
      • State "DONE" from "TODO" [2018-04-11 Wed 17:18]
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      func floydWarshall(vertices AdjList) [][]int {
      dist := make([][]int, len(vertices))
      for i, _ := range dist {
      dist[i] = make([]int, len(vertices))
      for j, _ := range dist[i] {
      dist[i][j] = math.MaxInt32
      }
      dist[i][i] = 0
      }

      for u := 0; u < len(vertices); u += 1 {
      for j := 0; j < len(vertices[u].ArcNodeArr); j += 1 {
      v := vertices[u].ArcNodeArr[j].AdjVex
      d := vertices[u].ArcNodeArr[j].Info.(int)
      dist[u][v] = d
      }
      }

      for k := 0; k < len(vertices); k += 1 {
      for i := 0; i < len(vertices); i += 1 {
      for j := 0; j < len(vertices); j += 1 {
      if dist[i][j] > dist[i][k]+dist[k][j] {
      dist[i][j] = dist[i][k] + dist[k][j]
      }
      }
      }
      }

      return dist
      }
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      package main

      import "fmt"
      import "math"




      func main() {
      vertices := AdjList{
      VNode{
      Data: 0,
      ArcNodeArr: []ArcNode{
      ArcNode{AdjVex: 1, Info: 10},
      ArcNode{AdjVex: 2, Info: 5},
      },
      },
      VNode{
      Data: 1,
      ArcNodeArr: []ArcNode{
      ArcNode{AdjVex: 2, Info: 2},
      ArcNode{AdjVex: 3, Info: 1},
      },
      },
      VNode{
      Data: 2,
      ArcNodeArr: []ArcNode{
      ArcNode{AdjVex: 1, Info: 3},
      ArcNode{AdjVex: 3, Info: 9},
      ArcNode{AdjVex: 4, Info: 2},
      },
      },
      VNode{
      Data: 3,
      ArcNodeArr: []ArcNode{
      ArcNode{AdjVex: 4, Info: -4},
      },
      },
      VNode{
      Data: 4,
      ArcNodeArr: []ArcNode{
      ArcNode{AdjVex: 0, Info: 7},
      ArcNode{AdjVex: 3, Info: 6},
      },
      },
      }

      fmt.Println(floydWarshall(vertices))
      }
  2. DONE Johnson算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    func johnson(vertices AdjList) ([][]int, bool) {
    v := VNode{
    Data: len(vertices),
    ArcNodeArr: make([]ArcNode, len(vertices)),
    }

    for i, _ := range vertices {
    v.ArcNodeArr[i] = ArcNode{
    AdjVex: i,
    Info: 0,
    }
    }
    vertices = append(vertices, v)

    hDist, bCycle := bellmanFord(vertices, len(vertices)-1)
    if bCycle {
    return [][]int{}, bCycle
    }

    for u := 0; u < len(vertices); u += 1 {
    for j := 0; j < len(vertices[u].ArcNodeArr); j += 1 {
    v := vertices[u].ArcNodeArr[j].AdjVex
    d := vertices[u].ArcNodeArr[j].Info.(int)
    d = d + (hDist[u] - hDist[v])
    vertices[u].ArcNodeArr[j].Info = d
    }
    }

    vertices = vertices[:len(vertices)-1]
    dist := make([][]int, len(vertices))
    for i, _ := range vertices {
    dist[i] = dijkstra(vertices, i)
    for j, _ := range dist[i] {
    dist[i][j] = dist[i][j] + (hDist[j] - hDist[i])
    }
    }

    return dist, false
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    package main

    import "fmt"
    import "math"









    func main() {
    vertices := AdjList{
    VNode{
    Data: 0,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 1, Info: 10},
    ArcNode{AdjVex: 2, Info: 5},
    },
    },
    VNode{
    Data: 1,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 2, Info: 2},
    ArcNode{AdjVex: 3, Info: 1},
    },
    },
    VNode{
    Data: 2,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 1, Info: 3},
    ArcNode{AdjVex: 3, Info: 9},
    ArcNode{AdjVex: 4, Info: 2},
    },
    },
    VNode{
    Data: 3,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 4, Info: -4},
    },
    },
    VNode{
    Data: 4,
    ArcNodeArr: []ArcNode{
    ArcNode{AdjVex: 0, Info: 7},
    ArcNode{AdjVex: 3, Info: 6},
    },
    },
    }

    fmt.Println(johnson(vertices))
    }

13 DONE Cache

  • State "DONE" from "TODO" [2018-03-23 Fri 17:46]

13.1 DONE LRU

  • State "DONE" from "TODO" [2018-03-23 Fri 17:45]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
type MyListNode struct {
Key int
Value int
Next *MyListNode
}

type LRUCache struct {
Capacity int
Head *MyListNode
}

func Constructor(capacity int) LRUCache {
return LRUCache{
Capacity: capacity,
Head: nil,
}
}

func (this *LRUCache) Get(key int) int {
dummyNode := &MyListNode{
Next: this.Head,
}

pre := dummyNode
curr := dummyNode.Next
for curr != nil {
if curr.Key == key {
pre.Next = curr.Next
curr.Next = dummyNode.Next
dummyNode.Next = curr
this.Head = dummyNode.Next
return dummyNode.Next.Value
}

pre = curr
curr = curr.Next
}

return -1
}

func (this *LRUCache) Put(key int, value int) {
newNode := &MyListNode{
Key: key,
Value: value,
}
if this.Head == nil {
this.Head = newNode
return
}

dummyNode := &MyListNode{
Next: this.Head,
}

var length int
pre := dummyNode
curr := dummyNode.Next
for curr != nil {
if curr.Key == key {
pre.Next = curr.Next
curr.Next = dummyNode.Next
dummyNode.Next = curr
curr.Value = value
this.Head = dummyNode.Next
return
}

pre = curr
curr = curr.Next
length += 1
}

if length == this.Capacity {
curr = dummyNode
for length > 1 {
curr = curr.Next
length -= 1
}
curr.Next = nil
}

newNode.Next = dummyNode.Next
dummyNode.Next = newNode
this.Head = dummyNode.Next
return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
type MyListNode struct {
Key int
Value int
Pre *MyListNode
Next *MyListNode
}

type LRUCache struct {
Capacity int
Length int
Head *MyListNode
Tail *MyListNode
K2NodeMap map[int]*MyListNode
}

func Constructor(capacity int) LRUCache {
return LRUCache{
Capacity: capacity,
Length: 0,
K2NodeMap: make(map[int]*MyListNode),
}
}

func (this *LRUCache) Get(key int) int {
targetNode := this.getNode(key)
if targetNode != nil {
return targetNode.Value
} else {
return -1
}
}

func (this *LRUCache) getNode(key int) *MyListNode {
if this.Length == 0 {
return nil
}

if targetNode, ok := this.K2NodeMap[key]; ok {
if targetNode == this.Head {
return targetNode
}

if targetNode.Pre != nil {
targetNode.Pre.Next = targetNode.Next
}
if targetNode.Next != nil {
targetNode.Next.Pre = targetNode.Pre
}

if this.Tail == targetNode {
this.Tail = targetNode.Pre
if this.Tail != nil {
this.Tail.Next = nil
}
}

targetNode.Next = this.Head
if this.Head != nil {
this.Head.Pre = targetNode
}
this.Head = targetNode
targetNode.Pre = nil
if this.Length == 1 {
this.Tail = targetNode
}
return targetNode
} else {
return nil
}
}

func (this *LRUCache) Put(key int, value int) {
if this.Capacity == 0 {
return
}

targetNode := this.getNode(key)
if targetNode != nil {
targetNode.Value = value
return
}

newNode := &MyListNode{
Key: key,
Value: value,
}
if this.Head == nil {
this.Length = 1
this.Head = newNode
this.Tail = newNode
this.K2NodeMap[newNode.Key] = newNode
return
}

if this.Length == this.Capacity {
delete(this.K2NodeMap, this.Tail.Key)
if this.Tail.Pre != nil {
this.Tail = this.Tail.Pre
this.Tail.Next = nil
} else {
this.Head, this.Tail = nil, nil
}
} else {
this.Length += 1
}

this.K2NodeMap[newNode.Key] = newNode
newNode.Next = this.Head
if this.Head != nil {
this.Head.Pre = newNode
}
this.Head = newNode
if this.Length == 1 {
this.Tail = newNode
}

return
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package main

import "fmt"



func main() {
lru := Constructor(2)
lru.Put(2, 1)
lru.Put(3, 2)
fmt.Println(lru.Get(2))
fmt.Println(lru.Get(3))
fmt.Println(lru.Get(3))
lru.Put(4, 3)
fmt.Println(lru.Get(2))
fmt.Println(lru.Get(3))
fmt.Println(lru.Get(4))
return
}

13.2 DONE LFU

  • State "DONE" from "TODO" [2018-03-23 Fri 13:54]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
type MyListNode struct {
Key int
Value int
Counter int
Next *MyListNode
}

type LFUCache struct {
Capacity int
Head *MyListNode
}

func Constructor(capacity int) LFUCache {
return LFUCache{
Capacity: capacity,
Head: nil,
}
}

func (this *LFUCache) Get(key int) int {
if this.Capacity == 0 {
return -1
}

dummyNode := &MyListNode{
Next: this.Head,
}

pre := dummyNode
curr := this.Head
for curr != nil {
if curr.Key == key {
curr.Counter += 1
pre.Next = curr.Next
curr.Next = dummyNode.Next
dummyNode.Next = curr
this.Head = dummyNode.Next
return dummyNode.Next.Value
}

pre = curr
curr = curr.Next
}

return -1
}

func (this *LFUCache) Put(key int, value int) {
if this.Capacity == 0 {
return
}

newNode := &MyListNode{
Key: key,
Value: value,
Counter: 1,
}
if this.Head == nil {
this.Head = newNode
return
}

dummyNode := &MyListNode{
Next: this.Head,
}

var length int
pre := dummyNode
curr := dummyNode.Next
min_pre, min_curr := pre, curr
for curr != nil {
if curr.Key == key {
curr.Counter += 1
curr.Value = value
pre.Next = curr.Next
curr.Next = dummyNode.Next
dummyNode.Next = curr
curr.Value = value
this.Head = dummyNode.Next
return
}

if min_curr.Counter >= curr.Counter {
min_pre, min_curr = pre, curr
}

pre = curr
curr = curr.Next
length += 1
}

if length == this.Capacity {
min_pre.Next = min_curr.Next
}

newNode.Next = dummyNode.Next
dummyNode.Next = newNode
this.Head = dummyNode.Next
return
}
Last Updated 2018-04-26 Thu 18:42.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)