Onsite talk
1.了解自己的項目細節(jié)
Question:
1.思考BST level order traverse 什么時候不用記錄size？
- HashTable 有啥用來著？
Note :
String[] array = new String[] {"lint", "intl","code"};
arraylist.set(index , Element);
Str.startsWith（string） 【Return true/false】
list.indexof(返回的是index啊
?。。。?br>
list.get()返回的才是值?。?！
時刻謹記：substring的用法！
str.substring(start, length)
Chars beginning at start
Up to but not including end
神句！
map.put( c , map.getOrDefault(c , 0) + 1);
//遍歷
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//遍歷map中的鍵
for (Integer key : map.keySet()) {
System.out.println("Key = " + key);
}
//遍歷map中的值
for (Integer value : map.values()) {
System.out.println("Value = " + value);
}
int i = Arrays.binarySearch(dp, 0, len, x)；
returns the index if contains. else return:
【it returns (-(insertion point) - 1) 】
int count = Character.getNumericValue(char c); =========》char
Integer.parseInt() ========》String
private Queue<Long> small = new PriorityQueue();
默認出的是最小的，有null的時候感覺會出null，因為system.out.print 會報錯
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
Character.isLowerCase
HashSet 真是個好東西，只記錄有無這個值，不管重復多少次。
ArrayList: .size()
String : .length()
int[]num: .length
hashTable.length;
Integer.MAX_VALUE;
Integer.MIN_VALUE;
Arrays.sort(num);
Arrays.fill( num, i);
Collections.reverse(result);
HashSet<Node> set = new HashSet<>(); set.size(); set.add(); set.contains();
HashMap<node，node> map = new HashMap<>(); map.put(); map.containsKey();
map.keySet(); 返回一套key！！~
HashTABLE : ListNode[] hashtable = new ListNode[newCapacity];
char[] array= str.toCharArray();
Queue<Integer> q = new LinkedList<Integer>();
Stack<Integer> s = new Stack<>();
s.pop();
s.push(1);
s.peek();
q.add(1);
q.offer(1);
q.poll();
q.peek();
位運算操作：
A&B ： 都是1則為1，否則為0 ========> 可以得到A和B中所有該進位的地方（都是1才進位）
進位： A&B << 1
<< :移位運算符，所有的二進制像左移一個，末尾舔0.（相當于十進制乘以了2）
byte的取值范圍為-128~127，占用1個字節(jié)（-2的7次方到2的7次方-1）
short的取值范圍為-32768~32767，占用2個字節(jié)（-2的15次方到2的15次方-1）
int的取值范圍為（-2147483648~[2147483647](https://www.baidu.com/s?wd=2147483647&tn=44039180_cpr&fenlei=mv6quAkxTZn0IZRqIHckPjm4nH00T1YvPjR4mWuWnHnvPjuhPHbk0ZwV5Hcvrjm3rH6sPfKWUMw85HfYnjn4nH6sgvPsT6KdThsqpZwYTjCEQLGCpyw9Uz4Bmy-bIi4WUvYETgN-TLwGUv3ErHb4PHDznWT)），占用4個字節(jié)（-2的31次方到2的31次方-1）
long的取值范圍為（-9223372036854774808~9223372036854774807），占用8個字節(jié)（-2的63次方到2的63次方-1）
Easy
1.Sort Integers
2.Binary Tree Maximum node
3.Fibonacci
4.Rectangle Area
5.Remove LinkedList Element
6.A+B problem
7.Guess Number Game
8.Intersection of Two Arrays
9.Intersection of Two Arrays II
Chapter 1 Sort
Jun 19
1.Median (Quick sort)
July 3
2.StrStr(自己的方法。有時間再復習答案的方法)
Chapter 2 Binary Search
1.First Position of Target
3.Search Insert Position (注意end+1的情況)
4.Search a 2D Matrix
5.Find Peak Element（以mid為最低點看兩邊+1的趨勢即可。但是要考慮else的情況，隨便分配給start或者end 都可以。不分配的話死循環(huán)了。）
6.First Bad Version
July 16
1.Search in Rotated Sorted Array
2.Search in Rotated Sorted Array II
3.Find Minimum in Rotated Sorted Array(一定是nums[mid] > nums[end]
而不是nums[mid] >= nums[start] )
4.Find Minimum in Rotated Sorted Array II
5.Search for a Range
6.Binary Search Tree Iterator(用stack)
7.Insert Node in a Binary Search Tree
8.Remove Node in Binary Search Tree
9.Search Range in Binary Search Tree
10.Convert BST to Greater Tree
Chapter 3 Binary Search Tree
Binary Search Tree 的定義： 左< 中 < 右
25.Binary Tree Inorder Traversal
26.Binary Tree Postorder Traversal
27.Binary Tree preorder Traversal
28.Binary Tree level order Traversal
29.Binary Tree Level Order Traversal II
30.Binary Tree Paths(String的相加：直接用加號相加)
31.Binary Tree Path Sum(1.考慮負數(shù)情況 2.題目說了要到達leaf)
Jun 19
5.Count of Smaller Number (Segement Tree 的解法？？？！)
6.Segment Tree Build（ Segment Tree）
7.Segment Tree Modify
Jun 20
1.Segment Tree Query
2.Segment Tree Query II
Jun 23
1.Maximum Depth of Binary Tree
2.Minimum Depth of Binary Tree （Path 一定是要到達leaf的）
3.Validate Binary Search Tree
4.Lowest Common Ancestor
5.Binary Tree Zigzag Level Order Traversal
July 11
6.Balanced Binary Tree
Chapter 4 D&Q
July 6
1.Triangle : (自上而下遍歷的時候呢，注意第一條不能算進去，而且，最后一條也不能算呀)
O(n) 的方法：自下而上，res[0][0] = res[0][0+1]+ res[0+1][0+1] +triangle[0][0]。。。遞歸每次只保留最小值
2.Minimum Path Sum
July7
3.Climbing Stairs
4.Unique Paths
5.Unique Paths II
July10
1.Binary Tree Maximum Path Sum (簡潔優(yōu)雅的leetcode)
2.Jump Game
3.Jump Game II
4.Longest Increasing Subsequence( Arrays.BinarySearch() )
5.Longest Common Subsequence (用二維數(shù)組來做，你敢信嗎 或許有圖的概念在里面？)
6.Longest Common Substring（思考這一題dp的推導公式）
7.valid Palindrome
8.Palindrome Partitioning
July11
1.Palindrome Partitioning II (又用了二維格子，interesting )
2.word break（注意i和j ，不要用最簡單的從前往后，而是從j到i）
July14
3.Distinct Subsequences(用二維格子)
4.Edit Distance(用二維格子)
5.Interleaving String （(用二維格子，這是目前最難的）
Chapter 7 Graph
Graph 掌握重點：
- clone graph
- Topological Sorting
- Search:
A. DFS : 遞歸，（二叉樹，D&Q : DP問題是試圖把2^n或者n！===> n^2, n^3）
O（2^n）,O(n!)
find all possible solutions : Permutations / subsets
B. BFS：level order （while）
O(n)====> Binary Search Tree, O(m) ====>Graph
//n 是點，m 是邊
graph traversal
find shortest path in a simple graph
6.clone Graph
7.classical binary search
8.Topological Sorting
9.Permutations
10.subsets
11.N-Queens
12.Valid Palindrome
13.Palindrome Partitioning
14.Combinations
15.Combination Sum
16.word ladder
17.word Ladder2
Chapter 8 Data Structure
1. Stack
18.Minstack
19.Implement Queue by two Stacks
20.Largest Rectangle in Histogram
21.max Tree (!)
2. Hash
Operations:
Insert/ Delete/ Search : O(1)
Collision :
Open Hashing(LinkedList)
Closed Hashing(Array)
因此為了避免collision，要盡量離散
Java differences of :
HashTable / HashSet / HashMap
HashTable is thread Safe
22.rehashing
23.Longest Consecutive Sequence (不用考慮array是否sort，在hashset里找到一個刪去一個就好了。hashset 的意義本身就是記錄是否contain的)
Jun.7
24.LRU Cache （#DataStructure： LInkedHashMAp）
Chapter 9 High Frequence
33.Single Number (異或運算 ^ : 不進位的二進制加法)
34.Single Number 2
35.Single Number 3
40.Majority Number
Jun.19
2.Majority Number 2
3.Majority Number 3
Jun.30
1.Data Stream Median (Heap : log(n) )
2.Best Time to Buy and Sell Stock
3.Maximum Subarray
4.Minimum Subarray
5.Maximum Subarray 2
6.Best Time to Buy and Sell Stock 2
7.Best Time to Buy and Sell Stock 3
8.Two sum( Return index 基本上只能用hash表 )
（** 返回數(shù)值的話，是Two pointer問題** ）
9.Maximum Subarray Difference（只通過了百分之64，要參考求min時的做法）10.3_SUM(Two Pointer)（未跑通）
July.1
1.4_SUM(未做)
2.3-SUM closet （未做）
July.3
1.Partition Array (背誦)
2.Sort Letters by Case
3.sort color 1
4.sort color 2
5.Interleaving positive and negative
6.Sqrt(二分法。變量是long)
7.Fast Power （二分法。不是很明白這個數(shù)學運算，背誦）
