leetcode: Jump Game

Algorithm: greedy.
All nodes with in jumping range can be used as stepping stones. Take the stepping stone which can help you reach farther.

Example:
A = [2,3,1,1,4,0,1]

1. At A[0], can jump at most 2, so A[1], A[2]  are all possible intermediate stepping stone
2. If take A[1] as stepping stone, at most can jump to A[4]; If take A[2], at most can jump to A[3]; So take A[1] as stepping point and jump to A[4] ; [Greedy]
3. At A[4], can jump at most 4, so A[5], A[6] are all in jumping range. Can Reach the end;

Code:
public class Solution {
    public boolean canJump(int[] A) {
        int current = 0;
        while(current < A.length -1){
            if(A[current] == 0) return false;
         
            int max = current+1;//best stepping stone; initialized as the one right after current node
            for(int i = current+1; i <= current + A[current] && i < A.length; i++)
            {
                if(i + A[i] > max + A[max]){
                    max = i;
                }
            }
            current = max;//take the best stepping stone 
        }
        return true;
    }
}

leetcode: Word Break II

Instead of returning true or false, word break II asks to record all possible breakings.

By modifying word break I, it is not hard to get the solution. The major differences are:

1. Don't return when finding a possible solution. Keep trying other cases.
2. A boolean variable to record whether a breaking point is possible or not;

Code:

public class Solution {
 public ArrayList wordBreak(String s, Set dict) {
  Set impossible = new HashSet();
  ArrayList res = new ArrayList();

  recursion(s, dict, 0, impossible, res, "");
  return res;

 }

 public boolean recursion(String s, Set dict, int current,
   Set impossible, ArrayList res, String breaks) {
  if (current == s.length()) {
   res.add(breaks.substring(0, breaks.length() - 1));
   return true;
  }

  boolean possible = false;
  for (int i = current + 1; i <= s.length(); i++) {
   if (impossible.contains(i))
    continue;
   if (dict.contains(s.substring(current, i))) {
    String newBreaks = new String(breaks);
    newBreaks = newBreaks + s.substring(current, i) + " ";
    if (recursion(s, dict, i, impossible, res, newBreaks)) {
     possible = true;
    }
   }
  }
  if (!possible) {
   impossible.add(current);
   return false;
  } else
   return true;
 }

}

leetcode: Word Break

Very basic recursion gives time limit exceeded.

The remedy is: using a hashSet to remember impossible breaking points which have been tried.

public class Solution {
    public boolean wordBreak(String s, Set dict) {
      
       return recursion(s, dict, 0);
    }
    
    public boolean recursion(String s, Set dict, int current){
         if(current == s.length()) return true;//base case
         
         for(int i = s.length(); i>current; i--){
             if(dict.contains(s.substring(current, i)))
             {
                 dict.add(s.substring(0, i));
                 if(recursion(s, dict, i))
                    return true;
             }
         }
         return false;
    }
}

leetcode: Copy List with Random Pointer

Question specification:
A linked list is given such that each node contains an additional random pointer which should point to any node in the list or all.

More: Do not assume the label value of each node is distinct.

Solution1: (2 pass)

1. start from head, follow next pointer, create a list via new.
2. start from head, point random pointer to correct node.

Analysis: Step2 is quite time consuming. For each node, in order to find its correct random, need to start checking from the very beginning--head. In worst case, for node whose position is n in the list, it takes n movement to find its random.

Solution2: 

The difficulty is how to point random to correct node.  Two imagination can help improving step2:

• If we can quickly know which node should the random node point to...
• If we have random access to all the node in the list...

Using HashMap and ArrayList together can help realizing these two imaginations. When iterate over the original list, we can put each node into HashMap, and assign unique identifier--increasing integer--to each node. At the same time,  add the newly created/cloned node into an ArrayList. 

• HashMap: <Original node, integerValue>
• ArrayList: <Clone of original node>

The relationship between the HashMap and the ArrayList is:  the index for cloned node (in ArrayList)  equals to the integerValue of original node (in HashMap).

Now for each random node,we can find its associated integer value by query HashMap. Then the clone of this random node can be found by indexing ArrayList.

Also, we do not need to separate the two steps mentioned in Solution1.

public class Solution {
    
     public RandomListNode copyRandomList(RandomListNode head) {
        
        if(head == null) return null;
        
        RandomListNode current = head;
        RandomListNode head2 = new RandomListNode(head.label);
        RandomListNode current2 = head2;
        
        HashMap  all = new HashMap();
        ArrayList  list = new ArrayList ();
        
        all.put(head, 0);
        list.add(head2);
        
        //copy list 
        int i = 1;
        while(current.next != null){
            //copy current.random
            if(current.random != null){
                if(!all.containsKey(current.random)){
                    all.put(current.random, i++);
                    RandomListNode tempRandom = new RandomListNode(current.random.label);
                    current2.random = tempRandom;
                    list.add(tempRandom);
                }
                else{
                    int pos = all.get(current.random);
                    current2.random = list.get(pos);
                }
            }
            //copy current.next;
            
            if(!all.containsKey(current.next))
            {
                all.put(current.next, i++);
                RandomListNode temp = new RandomListNode(current.next.label);
                current2.next = temp;
                list.add(temp);
            }else{
                int pos = all.get(current.next);
                current2.next = list.get(pos);
            }
            current = current.next;
            current2 = current2.next;
        }
        
        if(current.random != null){
                if(!all.containsKey(current.random)){
                    all.put(current.random, i++);
                    RandomListNode tempRandom = new RandomListNode(current.random.label);
                    current2.random = tempRandom;
                    list.add(tempRandom);
                }
                else{
                    int pos = all.get(current.random);
                    current2.random = list.get(pos);
                }
            }
        
        return head2;
    }
    
}

leetcode: Candy

The idea is simple:

1. look for local minimum, assign 1 candy to local minimum.
2. Scanning from left to right, start from each local minimum, increase the candy by 1 if the rating increase. Cover all ascending "edge" from left to right;
3. Scanning form right to left, start from each local minimum, increase the candy by 1 if the rating increase. For local maximum, the candy number should be max of step2 and step3. After this, all ascending "edge" from right to left is covered.

How to find local minimum:

(no-bigger-than-left && no-bigger-than-right)

Note: Ratings can be equal so there can be some "flat" cases. 

In the requirement, it only says "higher rating, more candy than neighbors". What about "same rated neighbors"? Not necessarily same candies. Just make the total candies as less as possible!

Code

public class Solution {
    public int candy(int[] ratings) {
        
         int len = ratings.length;
        int[] candies = new int[len];
        
        if(len == 0) return 0;
        if(len == 1) return 1;
        //step1: find local minimum
        int i = 0;
        for(i = 0; i < len; i++)
        {
         if(i == 0 && ratings[i] <= ratings[i+1]) candies[i] = 1;
         if(i == len-1 && ratings[i] <= ratings[i-1]) candies[i] = 1;
         if(i > 0 && i < len-1 && ratings[i] <= ratings[i+1] && ratings[i] <= ratings[i-1]) candies[i] = 1;
        }
        
        //step2: assign candies
        for(i = 0; i < len-1; i++){
            if(candies[i] != 0 && ratings[i+1] > ratings[i]) candies[i+1] = candies[i] +1;
        }
        for(i = len-1; i > 0; i--)
        {
            if(candies[i] != 0 && ratings[i-1] > ratings[i])
                candies[i-1] = Math.max(candies[i-1], candies[i] + 1);
        }
        
        int total = 0;
        for(i = 0; i < len; i++)
            total += candies[i];
            
        return total;
    }
}

Binary tree inorder, preorder, postorder iteratively traversal

in-order: left, parent, right
pre-order: parent, left, right
post-order: left, right parent

Comparatively, in-order traversal is easier to think through.

Simplified iteratively steps for in-order traversal:

1. Starting from  node A,  firstly looks for the left-most node (call it B) and print it, 
2. then print node B's parent,  
3. then the same process (step 1 and 2)  is applied to this parent node's right node.

The implementation of these steps are straight forward. 

Now lets think about the overall control of iterations. How to start? When to terminate?

Since the brute-force solution is recursion, intuitively we need to use stack to simulate the recursion function-call stack.

Initialization: push root node into stack;

Termination: when the stack is empty (every node get processed)

Here is the modification of each step:

1. Starting from a node (poped out from stack), push each non-left-most node into stack; print left-most node
2. pop out a node from stack (left-most-node's parent) and print out; 
3. keep poping while the node (which is just poped out from stack) does not have right node; If it has right node, push the right node into stack and start a new iteration.

code:
pre-order:
The idea is very similar. The major difference is:

• in-order: print node when poping the node out
• pre-order: print node before pushing to stack

Code:

post-order:

Post-order can be done utilizing pre-order. The observation is:

• pre-order: parent, left, right
• post-order: left, right, parent

If we modify pre-order traversal slightly, visiting right node first instead of left node, it will be:

• (right node first) pre-order: parent, right, left
• post-order: left, right, parent

post-order is the reverse of (right-node-first) pre-order.

Code: