算法小结--各种算法

Heap (new PriorityQueue<>())
-complete binary tree, 通常会用到comparator来sort specific data class
-parent node val is greater or smaller than  child's value
-Complexity: 
   find min/max: O(1)
   insert: O(lgN) - max height of tree 
   remove(only min/max):O(lgn) - use the last one to put in tree and rearramge
O(1) get
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(10(optional initial capacity), Collections.reverseOrder()); --max 
insert 是O(logK) by height of tree;  最小（default）最大的在上面
 
EX:
» 23. Merge k Sorted Lists (heap or Divide&Conquer) 各大家
http://rainykat.blogspot.com.tr/2017/01/leetcode-23-merge-k-sorted-lists-heap.html
» 451. Sort Characters By Frequency(HashMap + Heap) G家亚麻
http://rainykat.blogspot.com.tr/2017/01/leetcodeg-451-sort-characters-by.html
 
Math
»  202.258. Happy Number (Math+HashSet), Add Digits(Math)各大家
http://rainykat.blogspot.com.tr/2017/01/leetcode-202-happy-number-mathhashset.html 
»  415. Add Strings G家Airbnb
http://rainykat.blogspot.com/2017/01/leetcode-ga-415-add-stringsmath.html 
»  43. Multiply Strings F家Twitter
http://rainykat.blogspot.com/2017/01/leetcodef-43-multiply-stringsmath.html
»  168. Excel Sheet Column Title 各大家
http://rainykat.blogspot.com/2017/01/leetcode-168-excel-sheet-column-title.html 
»  311. Sparse Matrix Multiplication F家LinkedIn
http://rainykat.blogspot.com/2016/12/leetcodeflinkedin-sparse-matrix.html 
»  13. Roman to Integer 各大家
String 倒着读
http://rainykat.blogspot.com.tr/2017/01/leetcode-13-roman-to-integer-math.html 

Array  
EX: 
» 334. Increasing Triplet Subsequence (初始值) F家
initialize min with Integer.MAX_VALUE to be overwritten
http://rainykat.blogspot.com.tr/2017/01/leetcodef-334-increasing-triplet.html
» 238. Product of Array Except Self 各大家
双向遍历法
http://rainykat.blogspot.com/2017/01/leetcode-238-product-of-array-except.html
» 277. Find the celebrity F家，LinkedIn 
2 pass loop array(1 for find candidates, 1 for validate candidates)
http://rainykat.blogspot.com/2017/01/leetcodeflinkedin-277-find.html
» 189. Rotate Array 微软, bloomberg
reverse array 3 parts (0-k-1,k-end,0-end)
http://rainykat.blogspot.com/2017/01/leetcodebloomberg-189-rotate-array.html
» 57. Insert Interval F家G家LinkedIn
http://rainykat.blogspot.com/2017/01/leetcode-57-insert-intervalarray-sort.html
» 387. First Unique Character in a String高频
巧用 int[] arr= new int[26], arr[c-'a'] 字母对应
https://leetcode.com/problems/plus-one/#/description 
» 66. Plus One 高频
思路： - add 1 from tail, track increment by inc
           - once inc = 0, return. Else in the pattern of 100...., 巧用inc
https://leetcode.com/problems/plus-one/#/description


String
常用代码
1.考虑substring str = s.substring(i,len) //str[i,len)
    - s.substring(i, i+len)//get substring of length = len starting from i
2. char to int: int a = charA-'0';
    int to char: char a = (char) b;
    int to string: Integer.toString(a);
    String to Int: int foo = Integer.parseInt("1234");
3. str.trim();//remove extra space in the start & end of string (LC151)
4. sb.setCharAt(index,c)//string builder to replace char
5. str.split("//s+") or  str.split(" +")//in split, regular expression

EX:
» 273. Integer to English Words F家微软
tricky, string with recursion and math sense
http://rainykat.blogspot.com/2017/01/leetcodef-273-integer-to-english-words.html 
» 434. Number of Segments in a String
watch the words start with ' '
http://rainykat.blogspot.com.tr/2017/01/leetcode-434-number-of-segments-in.html 
» 67. Add Binary F家
char to num convert: int a = charA - '0';
http://rainykat.blogspot.com/2016/12/leetcodef-add-binary.html  
» 161. One Edit Distance 各大家
用substring 来check是否剩余的string相同 
http://rainykat.blogspot.com/2017/01/leetcode-161-one-edit-distancesubstring.html 
» 5. Longest Palindromic Substring 
保持且只查大于当前长度的substring
http://rainykat.blogspot.com/2017/04/leetcode-5-longest-palindromic.html 


 
Stack--Deque (new LinkedList<>())
» 20. Valid Parentheses 各大家 巧用stack来存starting part of 括号， check括号是否match closing part
http://rainykat.blogspot.com/2017/01/leetcode-20-valid-parentheses.html
» 71. Simplify Path 微软，脸家
http://rainykat.blogspot.com/2017/01/leetcodef-71-simplify-pathstack.html 
» 66. Basic Calculator II 高频
http://rainykat.blogspot.com/2017/04/leetcode-227-basic-calculator-ii-stack.html

 Window 

1. fix length window
2. put one in, remove one out
» 567. Permutation in String