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:

Next Permutation

The logic is not very hard. However it is easy to make mistake at several places.

General example: 1 3 5 4 2
Step1: scan from right to left, locate the first decreasing number. 1 3 5 4 2
Step2: swap it with the smallest-larger-number (1 3 5 4 2) on the right.  1 4 5 3 2
Step3: reverse all the numbers on the right. 1 4 2 3 5


Need to pay attention to two test cases:
1) repeated value: 5 1 1   
2) reverse order: 5 4 3 2 1

Leetcode Insertion Sort List

For insertion sort, the insertion is usually performed in a backward fashion:
start from the node just ahead, move left one by one, until find the correct insertion point (first left-node which is smaller than the insertee).

However, for single linked list, moving backwards is very hard since pointers to node's previous node is not available.  So each time we have to seek for insert-position from the list-head.

Then what? After find the insert-position, what should we do next?

Take the example of   0  3  4  5  1,  where 1 is the node to be inserted.
It is easy to identify that we need to insert in front of 3. In order to do this in place, I break this action into the following steps:

1. move the sub-sequence 3  4  5  to the right by one:  0  _  3  4  5 
2. insert 1 to the places which held 3 before: 0  1  3  4  5 

Talking about the implementation of the above, the choice can either be: just modify the values of related ListNode , or break the link and insert the nodes into the correct position.

I implemented via modifying values.

Linked List Cycle II

Notation:

1. From head to cycleStartPoint:  a
2. From cycleStartPoint to encounter point: b
3. Number of nodes in in cycle: r
4. Total length of the list: L

First step: start fast runner and slow runner, stop when then encounter each other.

• slower runner move:  s = a + b; (eq1)
• fast runner move: S = 2s = s + kr; (eq2)

      From eq1 and eq2, we can get: s = kr = a + b;

• From kr = a + b
• (k-1)r + r = a + b
• (k-1)r + (L - a) = a + b
• (k-1)r + (L - a - b) = a

So: a = (k-1) cycles + (distance between encounter-point and cycle-start-point)

Step2: Move fast runner to head. Start both fast-runner and slow-runner, both move one node each step.

They will encounter each other again at cycle-start-point.