programming

# LintCode Diary

JAVA PROBLEM

1. 全局变量，常量在函数间地传递(376,381的区别)
2. String.valueOf(node.val),  把数字加到字符串里面
3. comparator(compare, equal)
4. Collections.sort(ascending and descending)
5. 如果class只有class没有Public，什么意思

1. subsets模板

OTHER PROBLEM

1. graph coloring

ATTENTION!

1. Think about exceptions before starting: capitalized characters, repeated elements in an array/vector.
2. Check special cases at the beginning: null strings/arrays, empty strings/arrays (one of them is empty or both of them are empty, LintCode13), two variables are the same. If the input is a two-dimensional vector, check both dimension (unique path). Check 0 and 1 (climbing stairs) because of the loop index below.
3. Check the upper bound of a loop index, in case of stack overflow. For example, if we have  x[i+a] in loops,if a is an integer,  bound(i) = len(x)-a, because max(i+a) = len(x)-1, max(i) = len(x)-a-1, bound(i) = max(i)+1 = len(x)-a+1-1 = len(x)-a ; if a is an index of another loop, bound(i) = len(x) -a +1
4. check “;”;  check index and branket;
5. initialization: type, initial value (when use break lat0er, when do max or min) ( jump game)
6. Use INT_MAX/INT_MIN
7. Use break
8. 切几刀和最后分几串差1
9. 字符串不仅要检查空串，还要检查长度上的问题（interleaving string)
10. 如果程序中只有if，最后还要返回一个值

TIPS

1. Draw if this helps you. If the input data is not straight forward, draw it.
2. 分情况讨论！！！细节！！！
3. 做了每一个决定时，都问自己一句，这样就够了吗，这样对吗

REVIEW

1. Recursion:  definition of a recursion; skeleton; exit, LintCode 15,16,17,18

TIME COMPLEXITY

1. Tips: we can conduct algorithm by the required time complexity
2. T(n) = T(n/2) + O(1)       T(n) = O(log n)
3. T(n) = T(n/2) + O(n)       T(n) = O(n)
4. T(n) = 2T(n/2) + O(1)      T(n) = O(n)
5. T(n) = 2T(n/2) + O(n)     T(n) = O(nlogn)

RECURSION

find all possible …→ search→ DFS→ recursion

2. Attention: 注意越界，throw new ArrayIndexOutOfBoundsError(“invalid location”); use for loop or while loop to traverse a linked list, remember to check null list in both loops. 如果有取node.next.next情况，while里/for外面要是判断到node.next!=null，否则会取到list外面, NullPointerException (middle of linked list)
3. Tips: create dummy nodes when we are changing the structure of the linked list, and let the next node of the dummy node point to the head node
4. relation with reference: for example, node1.next = node2; after doing this, node1.next points to the Node object that node2 points to. If we want to change the structure of the list, we have to use “next” to change it! Or to delete the head node.
5. Time complexity compared with ArrayList                               Add(first position)                                      O(n)           O(1)
6. 如果结束在node.next！=null，则结束在null前一个节点；如果结束在node!=null，则结束在null这一个节点
7. 总节点数奇偶考虑
8. reverse swap掌握的不好，swap其他情况？不知道改变后到底怎样的
9. Check whether the node and the next one is null, let the end of the list point to null
10. 有一个dummy node, 有一个在移动的node pointer；先操作，再移动这个node pointer
11. 让一个节点指向另一个节点前，先把它指向的当前值存下来

STACK

• Properties: Last In First Out (LIFO)
• Operations: push, pop, peek, isEmpty, clear
• Application: Operating system. In most modern computer systems, each thread has a reserved region of memory referred to as its stack. When a function executes, it may add some of its state data to the top of the stack; when the function exits it is responsible for removing that data from the stack.
• What is stack overflow:a stack overflow occurs if the call stack pointer exceeds the stack bound. The call stack may consist of a limited amount of address space, often determined at the start of the program. The size of the call stack depends on many factors, including the programming language, machine architecture, multi-threading, and amount of available memory. Reasons: infinite recursion, very deep recursion, very large stack variables (local variable)
• Attention: check null/empty before pop up an element, check empty before peek the stack
• Problems: 423

QUEUE

• check first == null (546)

BINARY SEARCH

1. Tips:                                                                                                                                                         1.1 Classic binary search: find what is the start, end, middle in this problem (in wood cut, end is the max) 1.2 Binary search on index: transform the problem into binary search: find the first/last/any position that meets the requirement in the source (clear about the description about the target)  when to return; when not to return？？？？（do not have the lines for returning when nums[mid] == target while doing search, after go through the searching array, then make the final decision???）
2. When to stop: start+1<end
3. How to compare:                                                                                                                                    if (target < A[mid]) { end = mid; } else if (target > A[mid]) {
start = mid; }                                                                                                                                       else if( target==A[mid]) {                                                                                                                   end = mid; // find the first  position                                                                                                   start = mid; // find the last position}
4. How to decide:                                                                                                                                         if (A[end] == target) {
return end;
}
if (A[start] == target) {
return start;
}                                                                                                                                                                 Be careful about the order of these two statements: check start first if asking for first position, check end first if asking for last position
5. 难点：找到target的描述

BINARY TREE (什么时候用写helper)

1. Question: helper里面要不要传最后的result的参数; 要不要写helper；什么时候有返回值
2. Depth First Search (DFS) :                                                                                                         Preorder: root, left, right(根左右); Inorder: left, root, right(左根右);  postorder: left, right, root(左右根)   Review traverse without recursion
3. Divide and conquer vs. traverse:                                                                  traverse的解法，一般都是从root出来，带着结果往下遍历，一般是自顶向下的做法。
divide & conquer 一般是求出子树（子问题）的解后，合并出当前子树（当前规模的问题）的解。这是一个自底向上合并的过程。遍历”是一个小人带着一本记事本游走整个二叉树。
“分治”是一个大王呆着两个小弟，让两个小弟分别去搞定左右子树的结果汇报给大王，大王做最后的整理和拍板

DC有return value traverse没有， 因为traverse是在进行的过程中更新返回的result

1.  When we use divide and conquer to search in a binary tree for some tasks, we throw the task to the left node and throw the task to the right node, which is “divide”. So the task will start to be dealt with from the bottom of the tree in recursion, and when doing backtracking, we will do “conquer”.
2. Tips:                                                                                                                                                         Be aware of minus values if we are dealing with numerical tasks.                               Nodes not existing: infinity (+/-)                                                                                                 When doing conquer, check the task of two sibling nodes, then check the task of the root node                                                                                                                                                 Be aware of null nodes all the time

BINARY SEARCH TREE

1. left < root, right > root; inorder:升序
2. 为了一个任务，维护一个全局变量和一个局部变量，先在recursion内部更新好局部变量（即divide），再将其和全局变量比较(即conquer)
3. 基本操作1插入：1从零开始把节点一个一个地插入从而创建一棵树，每进行一次插入，要维护BST的性质。
2查找：给定一个数据，查找是否有节点包含此书
3最大节点：返回当前树的的最大节点，即最右的右儿子。
4最小节点：返回当前树的的最小节点，即最左的左儿子。
5前驱：在中序遍历下，当前节点的前一个节点。
6后继：在中序遍历下，当前节点的后一个节点。
7删除：删除一个指定节点，每进行一次删除，要维BST的性质。

BFS（不熟，着重反复）

If we have a very large tree and want to be prepared to quit when we get too far from the original node

size=queue.size() 如果直接 for (int i = 0; i < queue.size(); i++) 会怎么样？如果需要分层，则要在循环外定义size

traverse时要注意，是否已经抓全了所有的点，两个节点之间是否连同（build post office）

DFS (找到所有方案)

Want to visit every node in the graph, or at least visit every node until we find whatever we’re looking for

HASH MAP

1. 要考虑到它set的nature，可以直接用contain search到一个元素，不用遍历 (two sum)

DYNAMIC PROGRAMMING:解决完第J个问题后，剩下的子问题是什么？

1. When to use DP: 最大值，最小值，方案个数，可行性
2. When not to use DP：求具体方案而不是方案个数（DFS）；输入数据是一个集合（set）而不是序列（sequence）；brute force已是polynomial
3. DP 四要素：state, function, initialization, answer
4. 坐标型DP

Tips: function中的循环，不再计算在初始化过程中计算过的点

1. 5. 单序列型DP
2. 双序列型：初始化时，不仅要看最左，最上，最后要查[0][0] (distinct subsequence)
3. 区间型动态规划
4. 划分型
5. 背包型

SORTING

• Quick Sort (divide and conquer, 先整体有序，再局部有序)
1. Expected time complexity: O(nlogn), not stable sort; space complexity: O(1), in place
2.  pivot is the value, not the index
3. left <= right, 否则左右两个部分有交集，会stack overflow
4. left < pivot; right > pivot，否则当数组都是相同的数，两个指针会一直移动，无法做到均分
• Merge Sort(divide and conquer, 先局部有序，再整体有序)
1. time complexity: O(nlogn), stable sort; space complexity: O(n),
• Heap Sort

tree map, priority queue