Showing posts with label 算法小结. Show all posts
Showing posts with label 算法小结. Show all posts

Wednesday, January 18, 2017

算法小结 -- BFS Graph的解法

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

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

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

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