01/02/2019
Kadane's Algorithm

#解决什么问题?

Maximum subarray sum

#思想

dp[i] represents the maximum subarray sum ending with i-th element

dp[i] = Math.max(dp[i - 1] + A[i], A[i])

#应用

  • LeetCode 53 Maximum Subarray
  • LeetCode 918 Maximum Sum Circular Array

08/05/2018
Boyer-Moore Majority Voting Algorithm

#Problem

给一个一维的数组, 找出出现次数大于⌊ n/2 ⌋的数. 比如 LeetCode 169 Majority Element.

#Algorithm

算法步骤很简单, 维护一个candidate和一个counter. 遍历数组,

1
2
3
4
5
6
7
8
if (num == candidate) {
counter++;
} else if (counter == 0) {
candidate = num;
counter = 1;
} else {
counter--;
}

#Assumption

这个算法的前提是input的数组中一定存在一个majority (出现次数大于⌊ n/2 ⌋).

  • 如果这个前提可以保证, 那么最后的candidate就是这个majority.

  • 如果不能保证一定有majority, 需要在遍历一遍数组, 统计一下最后的candidate在整个数组中出现了几次, 是否真的是majority.

#Proof

以下是wikipedia给出的证明:

Correctness
If there is a majority element, the algorithm will always find it. For, supposing that the majority element is m, let c be a number defined at any step of the algorithm to be either the counter, if the stored element is m, or the negation of the counter otherwise. Then at each step in which the algorithm encounters a value equal to m, the value of c will increase by one, and at each step at which it encounters a different value, the value of c may either increase or decrease by one. If m truly is the majority, there will be more increases than decreases, and c will be positive at the end of the algorithm. But this can be true only when the final stored element is m, the majority element.


还有一种证明方法, 可以这么想:

每当counter在一系列increase或decrease之后变为了0, 那么我们可以把整个array从这个当前的position一分为二.

前面一部分表示有x个majority和x个non-majority正好把counter给抵消掉了. 那么你可以认为前面这一部分没有什么卵用. 如果整个数组中真的存在一个majority, 那么有没有前面这一部分对结果没有任何影响, 因为后面还没有处理的那部分必定有一个majority的出现次数会大于non-majority出现的次数.

因此可以根据这个思路不断的对array进行划分(一旦counter变为0之后). 那么最极端的情况就是majority出现(n/2+1)次, 并且整个数组的最后一个element就是majority.
这种情况下在处理到倒数第二个element的时候, counter必然会变为0, 进行划分之后右边的部分就只剩下一个数, 就是我们要找的majority.

#Generalization

这个算法还可以扩展成:

  • 找出2个出现次数大于⌊ n/3 ⌋的数
  • 找出3个出现次数大于⌊ n/4 ⌋的数
  • 找出k个出现次数大于⌊ n/(k+1) ⌋的数

比如LeetCode229 Majority Elements II. 需要切记的就是无论扩展到几个majorities, 这个算法的前提是一定要有majorities. 如果遇到的问题中没有明确的说明input是否有majority, 都需要一个extra遍历来统计candidates的出现次数.

03/06/2018
Sorting

Partially ordered arrays: Insertion sort cost nearly linear time

Duplicate keys: 3-way quick sort might be faster

03/04/2018
Shortest Path Algorithm

Algorithms

  1. Dijkstra (Non-negative weights)
  2. Topological Sort (No directed cycles)
  3. Bellman-Ford (No negative cycles)
Read More

03/04/2018
Prim's Algorithm

Problem

Find MST by Prim’s Algorithm

Read More

03/04/2018
Kruskal Algorithm

Problem

Find MST

利用Union Find.

  1. Sort all edges by weight
  2. Add next edge to Tree unless its creating a cycle (Union-Find)
Read More

02/20/2018
Strongly Connected Components

Strongly Connected Component

  1. What is connected graph ?

    • A graph is connected if there is a path between each pair of vertices.
  2. What is strongly connected graph ?

    • A directed graph is strongly connected if there is a path between each pair of vertices.
    • Strongly connected的概念只存在于Directed Graph

Strongly connected components in G are the same as they are in reversed G!

Read More

02/18/2018
Hamilton Cycle

Hamilton Cycle: A cycle with each vertex exactly once.

Hamilton Cycle是一个Backtracking问题!

NP Complete Problem

Read More

02/18/2018
Euler Cycle

欧拉回路: A Cycle with each edge exactly once.

Read More

© 2019 ReeeStart with help from Hexo and Twitter Bootstrap. Theme by Freemind.