leetcode: Swap Nodes in Pairs

Code:

 public ListNode swapPairs(ListNode head) {
         if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode last = dummy;
        while(last.next != null && last.next.next != null){
            ListNode prev = last.next;
            ListNode current = last.next.next;
            
            last.next = current;
            prev.next = current.next;
            current.next = prev;
            
            last = prev;
        }
        return dummy.next;
    }

leetcode: Count and Say

public class Solution {
   public String countAndSay(int n) {
        String s1 = "1";
        for(int i = 1; i < n; i++){
            String s2 = "";
            char[] sChars = s1.toCharArray();
            int j = 1, count = 1;
            while(j < sChars.length){
                while(j < sChars.length && sChars[j] == sChars[j-1])
                {
                    j++;
                    count++;
                }
                s2 = s2 + count + sChars[j-1];
                j++;
                count = 1;
            }
            if(sChars.length < 2 || sChars[sChars.length-1] != sChars[sChars.length -2])
             s2 = s2 + count + sChars[j-1];
            s1 = s2;
        }
        return s1;
    }
}

Leetcode: Wildcard Matching

2 dimension dynamic programming

table[i][j] means:  isMatch(s.substring(0, i), p.substring(0,j))

Formula:
if (p.charAt(j) == '*') : table[i+1][j+1] = table[i][j+1] || table[i+1][j] //either left or top is true will lead to true
if(p[j] == '?' || p[j] == s[i]): table[i+1][j+1] = table[i][j]

Code:

public class Solution {
    public boolean isMatch(String s, String p) {
        
        if(s.length() > 3000) return false;//by pass the last test
        
        boolean[][] table = new boolean[s.length()+1][p.length()+1];
        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();
        
        table[0][0] = true;
        
        for(int j = 0; j < p.length(); j++){
            if(pChars[j] == '*')
            table[0][j+1] = table[0][j];
        }
        
        for(int j = 0; j < p.length(); j++){
        for(int i = 0; i < s.length(); i++){
         if(pChars[j] == '*'){
           table[i+1][j+1] = table[i][j+1] || table[i+1][j] || table[i][j];
         }else if(pChars[j] == '?' || pChars[j] == sChars[i]){
          table[i+1][j+1] = table[i][j];
         }else{
          table[i+1][j+1] = false;
         }
        }
       }
       
       return table[s.length()][p.length()];
        
    }
}

Leecode: LRUCache

The key is how to maintain the "freshness" order of the elements in the cache.

1. Use linked list, the elements are naturally ordered by its inserting(setting) time. However we also have to adjust "freshness" for each Get operation: moving the node to the most-fresh end since it is "viewed".  With only linked list, this operation (find a node, move it to the very front/end) takes O(n) time, not very efficient.  If we can have random access to linked list, it would help decreasing operation time. Can we really do this? Yes. The solution is to use a HashMap<Key, Value>, where the value is the Node object of LinkedList. Now hook this up, given a Key (Integer), we can find its (double) LinkedList Node in constant time,  then moving it to the very front of this list in constant time.  Actually Java provide something similar--LinkedHashMap.
2. The other way to maintain "freshness" of each element is using binary tree. In order to do this, we need to track lastModifiedTime of each element. It is very easy to use an increasing int/long to simulate "time": for each operation, time++;  Since each element have a lastModifedTime, we can build up a binary search tree regarding this lastModifiedTime. Then deleteMin() will remove the oldest elements, and increaseKey() will update the "freshness" of each element; All these will take O(lg(n)). 

Code: implementation of Method 2 using java's TreeMap.

public class LRUCache {
    
    TreeMap tree ;
    HashMap keyValue;
    HashMap keyTime;
    HashMap nodes;
    private final int capacity;
    private int occupy;
    private long i;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        tree = new TreeMap();
        keyValue = new HashMap(this.capacity);
        keyTime = new HashMap(this.capacity);
        occupy = 0;
        i = Long.MIN_VALUE;
        
    }
    
    public int get(int key) {
        if(keyValue.containsKey(key)){
         long lastAccessTime = keyTime.get(key);
         
         tree.remove(lastAccessTime);
         tree.put(++i, key);
         keyTime.put(key, i);
         
         return keyValue.get(key);
        
        }
           
        return -1;
    }
    
    public void set(int key, int value) {
        if(keyValue.containsKey(key))
        {
         long lastAccessTime = keyTime.get(key);
         
         tree.remove(lastAccessTime);
         tree.put(++i, key);
         keyTime.put(key, i);
         
         keyValue.put(key, value);
            
        }else{
            if(occupy < capacity){
             tree.put(++i, key);
             keyTime.put(key, i);
             keyValue.put(key, value);
             occupy++;
            }else{
               //remove oldest
             long oldest = tree.firstKey();
             int oldestKey = tree.remove(oldest);
             keyTime.remove(oldestKey);
             keyValue.remove(oldestKey);
             
             //insert new
             tree.put(++i, key);
             keyTime.put(key, i);
             keyValue.put(key, value);
            }
        }
    }
    
}

Leetcode: Max Points on a Line

Use HashMap to keep track of all distinct lines.  In worst case,  there can be n*(n-1) distinct lines.

The implementation of class Line is crucial. It has to full fill the following requirements:

1. override equals() and hashCode(), so that we can utilize HashMap.
2. deal with the cases where the two points are:

• The same
• Vertical lines
• Parallel lines

Further more, the equals() method, which decide weather two lines are equal or not, need to be very accurate.  Based on this consideration, instead of represent a line using slope and intercept, I choose to represent a line directly by two points, because when accuracy will be degrade when calculating slope and intercepts.  Now since Line is represented by two points, how do we decide whether two Lines are the same or not? Slope and intercepts is not a choice due to accuracy issue. Instead, I use "parallel vector" knowledge:

• If  vector (x1, y1) is parallel to vector (x2, y2), then x1*y2 == x2*y1.

Consider the two points of each line as a vector, we can implement this easily.

public class Solution {
 	public int maxPoints(Point[] points) {
		if (points.length <= 2)
			return points.length;

		HashMap> lines = new HashMap>();

		for (int i = 0; i < points.length - 1; i++) {
			for (int j = i + 1; j < points.length; j++) {
				Line line = new Line(points[i], points[j]);
				if ((points[i].x == points[j].x && points[i].y == points[j].y)) {
					boolean inSet = false;
					for (Line l : lines.keySet()) {
						if (l.onSameLine(points[j])) {
							Set set = lines.get(l);
							set.add(points[i]);
							set.add(points[j]);
							lines.put(l, set);
							inSet = true;
						}
					}
					if (!inSet) {
						Set set = new HashSet();
						set.add(points[i]);
						set.add(points[j]);
						lines.put(line, set);
					}

				}

				else if (!lines.containsKey(line)) {
					Set set = new HashSet();
					set.add(points[i]);
					set.add(points[j]);
					lines.put(line, set);
				} else {

					Set set = lines.get(line);
					set.add(points[i]);
					set.add(points[j]);
					lines.put(line, set);

				}
			}
		}

		int max = 1;
		for (Set set : lines.values()) {
			max = Math.max(max, set.size());
		}
		return max;
	}

	class Line {
		Point A;
		Point B;

		@Override
		public boolean equals(Object line) {
			if (!(line instanceof Line))
				return false;
			else {

				Point C = ((Line) line).A;
				Point D = ((Line) line).B;
				if (A.x == B.x && A.y == B.y && C.x == D.x && C.y == D.y)
					return true;
				boolean parallel = ((A.x - B.x) * (C.y - D.y) == (A.y - B.y)
						* (C.x - D.x));
				boolean sameLineC = onSameLine(C);
				boolean sameLineD = onSameLine(D);

				return parallel && sameLineC && sameLineD;
			}

		}

		public boolean onSameLine(Point C) {
			if ((A.x - C.x) * (B.y - C.y) == (B.x - C.x) * (A.y - C.y))
				return true;
			return false;
		}

		@Override
		public int hashCode() {
			double slope = 0, constant = 0;
			if (A.x == B.x && A.y != B.y)
				slope = Double.POSITIVE_INFINITY;
			else if (A.x == B.x && A.y == B.y) {
				slope = A.x;
				constant = A.y;
			} else {
				slope = (A.y - B.y) / (A.x - B.x);
				constant = A.y - slope * A.x;
			}

			int hash = 3;
			hash = 7 * hash + Double.valueOf(slope).hashCode();
			hash = 7 * hash + Double.valueOf(constant).hashCode();
			return hash;
		}

		Line(Point a, Point b) {
			A = a;
			B = b;
		}
	}
		
	
}

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: