BFS -- O(V+E) Time O(V)space
用queue, define graph 里面的level概念。
» 133. Clone Graph(BFS) 各大家
level为current node's negihbors
http://rainykat.blogspot.com/2017/01/leetcode-133-clone-graphbfs.html
» 127. Word Ladder(BFS) 各大家
level focus on queue size.
http://rainykat.blogspot.com/2017/01/leetcode-127-word-ladderbfs.html
» 269. Alien Dictionary 各大家
level is defined before loop, add to queue when meeting requirements
http://rainykat.blogspot.com/2017/01/leetcode-269-alien-dictionarybfs.html
Showing posts with label 算法小结. Show all posts
Showing posts with label 算法小结. Show all posts
Wednesday, January 18, 2017
Monday, January 16, 2017
算法小结--Desgin集合
OO/Class 设计
» 157.158. Read N Characters Given Read4 I/ II - Call multiple times F家
第二题考class variable概念,一个obj的class var value是会被keep住的
http://rainykat.blogspot.com.tr/2017/01/leetcodef-157158-read-n-characters.html
» 341. Flatten Nested List Iterator (Recursion) G家F家
Use recursion to traverse the nested list.
http://rainykat.blogspot.com/2017/02/leetcodegf-341-flatten-nested-list.html
» 146. LRU Cache(HashMap + Doubly LinkedList) 各大家
http://rainykat.blogspot.com/2017/02/leetcode-146-lru-cachehashmap-doubly.html
» 398. Random Pick Index(Reservoir Sampling - Random) F家
http://rainykat.blogspot.com/2017/01/leetcodef-398-random-pick-indexdesgin.html
» 380. Insert Delete GetRandom O(1) (Map + List + Random) 各大家
http://rainykat.blogspot.com/2017/02/leetcode-380-insert-delete-getrandom-o1.html
➤Trie (use for prefix tree, eg: string match, spell check)
» 208. Implement Trie (Prefix Tree)
http://rainykat.blogspot.com/2017/01/leetcode-208-implement-trie-prefix-tree.html
» 211. Add and Search Word - Data structure design (Trie+ Backtracking) F家
http://rainykat.blogspot.com/2017/01/leetcodef-211-add-and-search-word-data.html
➤Queue应用
» 297. Serialize and Deserialize Binary Tree 各大家
http://rainykat.blogspot.com.tr/2017/01/leetcode-297-serialize-and-deserialize.html
» 346. Moving Average from Data Stream (queue) G家
http://rainykat.blogspot.com/2017/01/leetcodeg-346-moving-average-from-data.html
» 157.158. Read N Characters Given Read4 I/ II - Call multiple times F家
第二题考class variable概念,一个obj的class var value是会被keep住的
http://rainykat.blogspot.com.tr/2017/01/leetcodef-157158-read-n-characters.html
» 341. Flatten Nested List Iterator (Recursion) G家F家
Use recursion to traverse the nested list.
http://rainykat.blogspot.com/2017/02/leetcodegf-341-flatten-nested-list.html
» 146. LRU Cache(HashMap + Doubly LinkedList) 各大家
http://rainykat.blogspot.com/2017/02/leetcode-146-lru-cachehashmap-doubly.html
» 398. Random Pick Index(Reservoir Sampling - Random) F家
http://rainykat.blogspot.com/2017/01/leetcodef-398-random-pick-indexdesgin.html
» 380. Insert Delete GetRandom O(1) (Map + List + Random) 各大家
http://rainykat.blogspot.com/2017/02/leetcode-380-insert-delete-getrandom-o1.html
➤Trie (use for prefix tree, eg: string match, spell check)
Complexity: O(M=key_length) for insertion & search, M is the length of key
Space: O(alphabet(26)*M*N) N is number of keys in trie
class TrieNode { //R links to node children private TrieNode[] links = new TrieNode[26];//simplified to save code private boolean isEnd; } private TrieNode root = new TrieNode(); public void insert(String word) { TrieNode node = root;
» 208. Implement Trie (Prefix Tree)
http://rainykat.blogspot.com/2017/01/leetcode-208-implement-trie-prefix-tree.html
» 211. Add and Search Word - Data structure design (Trie+ Backtracking) F家
http://rainykat.blogspot.com/2017/01/leetcodef-211-add-and-search-word-data.html
➤Queue应用
» 297. Serialize and Deserialize Binary Tree 各大家
http://rainykat.blogspot.com.tr/2017/01/leetcode-297-serialize-and-deserialize.html
» 346. Moving Average from Data Stream (queue) G家
http://rainykat.blogspot.com/2017/01/leetcodeg-346-moving-average-from-data.html
Monday, January 9, 2017
算法小结 -- Union Find的套路
Union Find
Good for graph problem, like finding cycles in edge, largest components, etc
O(M) for union find, M operations
M quick union + path compression on N objects should be N + MlgN
-make set
-union
-find set
思路:-- for n nodes from 0 to n-1, create roots[n] to track each root's parents.
-- initialize parent with -1(point to null), roots = [-1,-1,-1,...-1],
eg: n nodes from 0 to n-1, edges[0,1] [0,2] [2,3] will be [1,2,3,-1...]
-- recursively find root1 and root2 (edge[root1,root2])check if they are in the same set
if found in two sets, then union: roots[root1] = root2;
-- middle roots can be dirty, keep updating&maintain top parents or boundaries.
-- use path compression(point child root directly to top parent) to save time
应用: Undirected Graph
EX:
» 323. Number of Connected Components in an Undirected Graph(Union Find) G家Twitter
http://rainykat.blogspot.com/2017/01/leetcodegtwitter-323-number-of.html
» 261. Graph Valid Tree(Union Find)G家F家
http://rainykat.blogspot.com/2017/01/leetcodegf-261-graph-valid-treeunion.html
» 128. Longest Consecutive Sequence G家F家
http://rainykat.blogspot.com/2017/01/leetcodefg-128-longest-consecutive.html
Good for graph problem, like finding cycles in edge, largest components, etc
O(M) for union find, M operations
M quick union + path compression on N objects should be N + MlgN
-make set
-union
-find set
思路:-- for n nodes from 0 to n-1, create roots[n] to track each root's parents.
-- initialize parent with -1(point to null), roots = [-1,-1,-1,...-1],
eg: n nodes from 0 to n-1, edges[0,1] [0,2] [2,3] will be [1,2,3,-1...]
-- recursively find root1 and root2 (edge[root1,root2])check if they are in the same set
if found in two sets, then union: roots[root1] = root2;
-- middle roots can be dirty, keep updating&maintain top parents or boundaries.
-- use path compression(point child root directly to top parent) to save time
应用: Undirected Graph
EX:
» 323. Number of Connected Components in an Undirected Graph(Union Find) G家Twitter
http://rainykat.blogspot.com/2017/01/leetcodegtwitter-323-number-of.html
» 261. Graph Valid Tree(Union Find)G家F家
http://rainykat.blogspot.com/2017/01/leetcodegf-261-graph-valid-treeunion.html
» 128. Longest Consecutive Sequence G家F家
http://rainykat.blogspot.com/2017/01/leetcodefg-128-longest-consecutive.html
Thursday, January 5, 2017
算法小节--algorithm analysis
algorithm efficiency due to input size
Asymptotic Analysis: for real time programming, to conclude the worst cost.(grow array is O(n), need shift whole array)
Amortized Analysis: measure average performance and consider time to grow for longer time
(scripting to grow array will be O(1) bc do it rarely)
worst case: most time, index get to upper bound
Asymptotic Analysis: for real time programming, to conclude the worst cost.(grow array is O(n), need shift whole array)
Amortized Analysis: measure average performance and consider time to grow for longer time
(scripting to grow array will be O(1) bc do it rarely)
worst case: most time, index get to upper bound
average case: sometimes, uniformly distributed, sum cases/size (n*n-1....)/(n+1)
best case: bogus
Θ(g(n)), it means that the running time of the algorithm as n (input size) gets larger is proportional to g(n).(tight bound) - best case & worst case is same
O(g(n)), it means that the running time of the algorithm as n gets larger is at most proportional to g(n).(upper bound)
Ω(1)- best case
→ Rank:
log(n) <sqrt(n)< n <n^2 < n^log(n)<2^n
Master Theorem (recursion analysis)

→ Quick sort:
good for large size of number, no need extra space
Time: Average O(nlgn) Worstcase O(n^2)
Space: O(lgn) - stack
http://rainykat.blogspot.com/2017/01/quicksort.html
General:
Time: T(n) = T(k) + T(n-k-1) + Θ(n)
Best:middle element as pivot
T(n) = 2T(n/2) + \theta(n)
Worst: smallest or largest pivot,O(n^2), array already sorted
T(n) = T(0) + T(n-1) + Θ(n)
which is equivalent to
T(n) = T(n-1) +Θ(n)
Average
T(n) = T(n/9) + T(9n/10) +Θ(n)
→ Merge Sort: T(n) = 2T(n/2) + Θ(n),
Time: Θ(NlogN) Space: O(n) - merge array
→ Heap Sort: Time O(NlogN) Space O(1)
→ Bubble sort-
worst case: O(n^2)//pass through 2(at most n-1) times for n[3,2,1]
- each time 1 element is sorted at left
→ Selection sort-Split into 2 part
Time O(n^2) -- n + (n-1) + ..+2+1, Ω(n^2)
Sorted | Unsorted
- find min in unsorted
- swap with the 1st of unsorted part
- increase the sorted part
→ Insertion sort-Split into 2 part
-Time Complexity: 1+2+...(comparison for nth element)
n(n-1)/2 = O(n^2)
OMEGA(n) - Sorted list best case
Sorted | Unsorted
- Maintain sorted list, so move left
- grab unsorted element and put into sorted portion
- double ptr: i, j(end of sorted list)
- array是由尾向头(左), list则是从dummy head开始比较再插入
相关题:
http://rainykat.blogspot.com/2017/03/leetcode-147-insertion-sort-list.html
➤ Recursion
- 讲解: https://www.youtube.com/watch?v=t4MSwiqfLaY
- ex: factorial
base: just return 1
each step: return n*(n-1)!
which is return n*factorial(n-1)
- pretend it works, treat like variable
➤ Backtracking
Hamiltonian cycle - time O(N!) space O(N) recursion stack
round trip visited every nodes (n edges used to cover n nodes) from a node in graph
X1, X2,X3, ... ,Xn, X1
[2 - N]
(N - 1)! order permutation, dfs try all these possibilities
O(g(n)), it means that the running time of the algorithm as n gets larger is at most proportional to g(n).(upper bound)
Ω(1)- best case
→ Rank:
log(n) <sqrt(n)< n <n^2 < n^log(n)<2^n
Master Theorem (recursion analysis)
→ Quick sort:
good for large size of number, no need extra space
Time: Average O(nlgn) Worstcase O(n^2)
Space: O(lgn) - stack
http://rainykat.blogspot.com/2017/01/quicksort.html
General:
Time: T(n) = T(k) + T(n-k-1) + Θ(n)
Best:middle element as pivot
T(n) = 2T(n/2) + \theta(n)
Worst: smallest or largest pivot,O(n^2), array already sorted
T(n) = T(0) + T(n-1) + Θ(n)
which is equivalent to
T(n) = T(n-1) +Θ(n)
Average
T(n) = T(n/9) + T(9n/10) +Θ(n)
→ Merge Sort: T(n) = 2T(n/2) + Θ(n),
Time: Θ(NlogN) Space: O(n) - merge array
→ Heap Sort: Time O(NlogN) Space O(1)
→ Bubble sort-
- each time 1 element is sorted at left
→ Selection sort-Split into 2 part
Time O(n^2) -- n + (n-1) + ..+2+1, Ω(n^2)
Sorted | Unsorted
- find min in unsorted
- swap with the 1st of unsorted part
- increase the sorted part
→ Insertion sort-Split into 2 part
-Time Complexity: 1+2+...(comparison for nth element)
n(n-1)/2 = O(n^2)
OMEGA(n) - Sorted list best case
Sorted | Unsorted
- Maintain sorted list, so move left
- grab unsorted element and put into sorted portion
- double ptr: i, j(end of sorted list)
- array是由尾向头(左), list则是从dummy head开始比较再插入
相关题:
http://rainykat.blogspot.com/2017/03/leetcode-147-insertion-sort-list.html
➤ Recursion
- 讲解: https://www.youtube.com/watch?v=t4MSwiqfLaY
- ex: factorial
base: just return 1
each step: return n*(n-1)!
which is return n*factorial(n-1)
- pretend it works, treat like variable
if ( base case 1 ) // return some simple expression else if ( base case 2 ) // return some simple expression else if ( base case 3 ) // return some simple expression else if ( recursive case 1 ) { // some work before // recursive call // some work after } else if ( recursive case 2 ) { // some work before // recursive call // some work after } else // recursive case 3 { // some work before // recursive call // some work after }
➤ Backtracking
Hamiltonian cycle - time O(N!) space O(N) recursion stack
round trip visited every nodes (n edges used to cover n nodes) from a node in graph
X1, X2,X3, ... ,Xn, X1
[2 - N]
(N - 1)! order permutation, dfs try all these possibilities
Subscribe to:
Posts (Atom)



