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;
 }

}