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

难点:三要素的理解:定义,拆解,出口

定义和拆解:进入这层recursion要做什么?

回溯

出口:用来回到上一层recursion;若没有return (若用for循环进行recursion,则最后的花括号也是return,不写return也可以)

有一些条件要满足:在进下一次recursion前做判断,找代表,若不满足,则continue掉此轮循环
其实和traverse是有关系的,有一些问题可以理解为树的traverse,比如subsets,就可以理解为traverse a tree, whose nodes are the subsets.

LINKED LIST

  1. 基本功?:scratch a linked list, 遍历,增create删delete查read改update (two pointer:在list上数数)
  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 ArrayListcapture                               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

“stack”的图片搜索结果

  • Properties: Last In First Out (LIFO)
  • Operations: push, pop, peek, isEmpty, clear
  • Implementation: linked list
  • 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: capture1                                                                 capture2traverse的解法,一般都是从root出来,带着结果往下遍历,一般是自顶向下的做法。
    divide & conquer 一般是求出子树(子问题)的解后,合并出当前子树(当前规模的问题)的解。这是一个自底向上合并的过程。遍历”是一个小人带着一本记事本游走整个二叉树。
    “分治”是一个大王呆着两个小弟,让两个小弟分别去搞定左右子树的结果汇报给大王,大王做最后的整理和拍板

边走边处理;处理完左右再处理根

需要维护path(root to leaf,需判断leaf是leaf)时用traverse,进下一次recursion时需要判断是不是null; 只要记录某一个statistics时,可用DC,进

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

难点:选好算法,需要维护什么量,需不需要resulttype,里面放什么

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

使用队列作为主要的数据结构 Queue 思考:用栈(Stack)是否可行?为什么行 or 为什么不行?

是否需要实现分层? 需要分层的算法比不需要分层的算法多一个循环

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

这个没有懂!!!

图的遍历和树的遍历的区别

如何实现图的遍历(graph traverse),有分层和没有分层

最短路径即使对graph进行分层的bfs的层数

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

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

  1. 5. 单序列型DPCapture.PNG
  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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s