One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#”, where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character ‘#’ representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as “1,,3”.

Example 1:
“9,3,4,#,#,1,#,#,2,#,6,#,#”
Return true

Example 2:
“1,#”
Return false

Example 3:
“9,#,#,1”
Return false

Thinking:

Accroding to the correct answer given, we can find the pattern. We should start from # and use stack to store it. When get two #, we should get another element from the string.

Solution:

public boolean isValidSerialization(String preorder) {
    String[] strlist = preorder.split(",");
    Stack<String> stack = new Stack<String>();
    Stack<String> tempstack = new Stack<String>();

    for (String s: strlist) {
        stack.push(s);
    }
    while (!stack.isEmpty()) {
        while (!stack.isEmpty() && stack.peek().equals("#")){
            tempstack.push(stack.pop());
        }
        if (tempstack.size() < 2)
            break;
        while (tempstack.size() >= 2 && !stack.isEmpty() && !stack.peek().equals("#")){
            tempstack.pop();
            tempstack.pop();
            if (!stack.isEmpty() && !stack.peek().equals("#")){
                stack.pop();
                tempstack.push("#");
            }
        }
    }

    if (tempstack.size() == 1 && stack.isEmpty())
        return true;
    else
        return false;
}

There is another simpler solution:

public boolean isValidSerialization(String preorder) {
    String[] p = preorder.split(",");
    int idx = 0; // stack
    for (int i = 0; i < p.length; i++) {
    if (p[i].equals("#")) {
        idx--;
    } else {
        if (idx < 0) { // check
          return false;
        }
        p[idx++] = p[i];
      }
    }
    return idx == -1; // check
  }

Reference: https://leetcode.com/discuss/83903/share-my-java-solution

And another much simplier solution which caculate the indegree and outdegree:

public boolean isValidSerialization2(String preorder) {
    String[] nodes = preorder.split(",");
    int diff = 1;
    for (String node: nodes) {
        if (--diff < 0) return false;
        if (!node.equals("#")) diff += 2;
    }
    return diff == 0;
}

Reference: https://www.hrwhisper.me/leetcode-algorithm-solution/

Lecture 1:

Lecture 2:

1. What’s Agent?
2. PEAS

Lecture 3:

1. Difference between tree search and graph search:
   Graph search will record the explored nodes, and won’t explore them again.

Lecture 4:

1. DFS, BFS, uniform-cost search, interative deepening search, evaluating search performance about completeness, optimality, time and space complexity
2. BFS:
   Completeness: Yes(When b is finite)
   Optimality: Yes(If path is nondecreasing)
   Time: O(b^d)
   Space: O(b^d)
3. DFS:
   Completeness: Yes(If graph search version)
   Optimality: No
   Time: O(b^m)
   Space: O(b*m)
4. Uniform-cost search:
   Completeness: Yes
   Optimality: Yes(If path is nondecreasing)
   Uniform-cost search not optimal if it is terminated when some node in the queue has goal state.
5. Iterative deepening search:
   Completeness: Yes
   Optimality: Yes
   Time: O(b^d)
   Space: O(bd)

Lecture 5:

1. Uniformed search, bi-directional search, informed search, greedy best first search, A*, interative deepening A*, recursive best first search, simplified memory-bounded A*
2. Bidirectional search:
   Search forward from initial state, and backward from goal.
   Completeness: Yes
   Optimality: Yes
   Time: O(b^(d/2)
   Space: O(b^(d/2)
3. Greedy best first search:
   Greedy BFS keeps all the nodes generated in the
   Frontier, which is sorted based on h(n).
   Completeness: No
   Optimality: No
   Time: O(b^m)
   Space: O(b^m)
4. A* Search:
   Use (approximate) total path cost to guide search
   Admissible Heurisitic: A heuristic is admissible if it never overestimates the cost to reach the goal
   e.g. hSLD(n) is admissible because it never overestimates the actual road distance
   Admissible heuristics does not guarantee that the chosen path is optimal
   A heuristic is consistent if for every node n and every successor n’ of n generated by any action a
   h(n) ≤ c(n,a,n’) + h(n’)
   That is, f(n) is nondecreasing along every path.
   Completeness: Yes
   Optimality: Yes(if admissible in tree search or consistent in graph search)
5. Recursive Best-Frist Search:
   Keep track of f value (f-limit) of best sibling of path currently exploring
   Space: O(bd)
6. Memory-Bounded A*:
   I.e., expand best leaves until available memory is full;When full, SMA* drops worst leaf node (highest f-value);Like RBFS, backup forgotten node value to its parent

Question:

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Thinking:

There are three ways to solve this problem:

1. The first one is to build a max heap with size n, and get the top of the heap k times.
2. The second one is to build a min heap with size k, and keep the biggest top k elements of this array. Finally, get the top of it.
3. The third one is to use a method called quickselect which uses function partition. It first use a pivot to split the array into two parts, then accroding to this index, choose which part to select.

Solution:

Max heap:

public int findKthLargest1(int[] nums, int k) {
    int len = nums.length;
    PriorityQueue<Integer> heap = new PriorityQueue<Integer>(len, new HeapComparator());
    for (int i = 0; i < len; i++){
        heap.add(nums[i]);
    }
    for (int i = 0; i < k-1; i++){
        heap.poll();
    }
    return heap.peek();
}

class HeapComparator implements Comparator {

    @Override
    public int compare(Object o1, Object o2) {
        // TODO Auto-generated method stub
        int i1 = (int)o1;
        int i2 = (int)o2;
        if (i1 > i2)
            return -1;
        else if (i1 == i2)
            return 0;
        else
            return 1;
    }

}

Min heap:

public int findKthLargest2(int[] nums, int k) {
    int len = nums.length;
    PriorityQueue<Integer> heap = new PriorityQueue<Integer>(k);
    for (int i = 0; i < k; i++){
        heap.add(nums[i]);
    }
    for (int i = k; i < len; i++){
        if (nums[i] > heap.peek()){
            heap.poll();
            heap.add(nums[i]);
        }
    }
    return heap.peek();
}

Quickselect:

public int findKthLargest3(int[] nums, int k) {
    int len = nums.length;
    return quickselect(nums, 0, len-1, k);
}

private int quickselect(int[] nums, int left, int right, int k){
    int pivotIndex = partition(nums, left, right, left);
    if (pivotIndex == k-1){
        return nums[pivotIndex];
    }
    else if(pivotIndex < k){
        return quickselect(nums, pivotIndex+1, right, k);
    }
    else{
        return quickselect(nums, left, pivotIndex-1, k);
    }
}

private int partition(int[] nums, int left, int right, int index){
    int pivotvalue = nums[index];
    int storeindex = left;
    nums[index] = nums[right];
    for (int i = left; i < right; i++){
        if (nums[i] > pivotvalue){
            int temp = nums[i];
            nums[i] = nums[storeindex];
            nums[storeindex++] = temp;
        }
    }
    nums[right] = nums[storeindex];
    nums[storeindex] = pivotvalue;
    return storeindex;
}

Question:

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Thinking:

It’s very similiar with the question permutation, we should use backtracing to go through all the possibilities. For example, we pick the first element of the array, and get the permutation of the rest of this array, and put the first element in every possible position. The only difference bewteen the permutation is that we don’t allow duplicate. We can use hashset to solve this problem.

By the way, I made a mistake this time which I used to make. It’s that in the loop of this:

for (List<Integer> list: backtracing(nums, index+1)){
    for (int i = 0; i <= list.size(); i++){
        List<Integer> tempres = new ArrayList<Integer>(list);
        tempres.add(i, nums[index]);
        tres.add(tempres);
    }
}

I shouldn’t use the temporary variable list to operate, because
1) the size of it will change;
2) we should use it several times instead of once.
Then that means we should build another temporary variable. In this case, it’s tempres.

Solution:

public List<List<Integer>> permuteUnique(int[] nums) {
    return backtracing(nums, 0);
}

private List<List<Integer>> backtracing(int[] nums, int index) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    HashSet<List<Integer>> tres = new HashSet<List<Integer>>();
    int len = nums.length;

    if (index >= len){
        return res;
    }

    if (index == len - 1){
        List<Integer> tempres = new ArrayList<Integer>();
        tempres.add(nums[index]);
        res.add(tempres);
        return res;
    }

    for (List<Integer> list: backtracing(nums, index+1)){
        for (int i = 0; i <= list.size(); i++){
            List<Integer> tempres = new ArrayList<Integer>(list);
            tempres.add(i, nums[index]);
            tres.add(tempres);
        }
    }

    res.addAll(tres);
    return res;
}

There is another solution is much faster than me. Because it use extra space to record which element is used and use sort to reduce the extra cost to make sure unique. What’s more, the process of adding first and removing after dfs is usually used by people. I suppose I should learn from it.

Code:

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(nums==null || nums.length==0) return res;
    boolean[] used = new boolean[nums.length];
    List<Integer> list = new ArrayList<Integer>();
    Arrays.sort(nums);
    dfs(nums, used, list, res);
    return res;
}

public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
    if(list.size()==nums.length){
        res.add(new ArrayList<Integer>(list));
        return;
    }
    for(int i=0;i<nums.length;i++){
        if(used[i]) continue;
        if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
        used[i]=true;
        list.add(nums[i]);
        dfs(nums,used,list,res);
        used[i]=false;
        list.remove(list.size()-1);
    }
}

1. Chapter 3 Exercises 6中有两个点， 一个是如果一个图的DFS树中没有出现的边，边的两个顶点一定是祖先与孩子的关系；一个是如果一个图的BFS树的BFS树中没有出现的边，边的两个顶点在BFS树中的层数差不会大于1.
2. 如果一个图的DFS树，或者BFS树和图相同，那么原图就没有环，否则就找他们最低的祖先，构成一个环。