基础算法和数据结构

发表于 | 分类于 | |

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)