Palindrome Pairs

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
解法：
对于每一个word， 拆分成前后两部分， 如果其中任意一部分本身是palindrome， 查看另一部分的reverse是否存在。 存在即可连接成为palindrome。
需要注意的是如果有word为空，因为会跳过最内层for循环，因此要单独处理。

public class Solution {
  public List<List<Integer>> palindromePairs(String[] words) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    Map<String, Integer> wordToIndex = new HashMap<String, Integer>();;
    for (int i = 0; i < words.length; i++) {
      wordToIndex.put(words[i], i);
    }
    for (int i = 0; i < words.length; i++) {
      String word = words[i];
      if (word.length() == 0) {
        for (int j = 0; j < words.length; j++) {
          if (isPalindrome(words[j]) && j != i) {
            List<Integer> pair = new ArrayList<Integer>();
            pair.add(i);
            pair.add(j);
            result.add(pair);      
          }
        }
      }
      for (int index = 0; index < word.length(); index++) {
        String firstHalf = word.substring(0, index);
        String secondHalf = word.substring(index, word.length());
        String reversedSecond = new StringBuilder(secondHalf).reverse().toString();
        String reversedFirst = new StringBuilder(firstHalf).reverse().toString();
        if (isPalindrome(firstHalf) && wordToIndex.containsKey(reversedSecond) && wordToIndex.get(reversedSecond) != i) {
          List<Integer> pair = new ArrayList<Integer>();
          pair.add(wordToIndex.get(reversedSecond));
          pair.add(i);
          result.add(pair);
        }
        if (isPalindrome(secondHalf) && wordToIndex.containsKey(reversedFirst) && wordToIndex.get(reversedFirst) != i) {
          List<Integer> pair = new ArrayList<Integer>();
          pair.add(i);
          pair.add(wordToIndex.get(reversedFirst));
          result.add(pair);
        }
      }
    }
    return result;
  }
    
  private boolean isPalindrome(String a) {
    for (int i = 0, j = a.length() - 1; i <= j; i++, j--) {
      if (a.charAt(i) != a.charAt(j)) {
        return false;
      }
    }
    return true;
  }
}

Lintcode: Nuts & Bolts Problem

quick sort非常好的题。用bolts[start]将nuts partition成两部分，得到中间值pivot，再用nuts[pivot]将bolts分成两部分。再对pivot两边进行recursion

public class Solution {
    public void sortNutsAndBolts(int[] nuts, int[] bolts) {
        if (nuts == null || nuts.length <= 1) {
            return;
        }
        sub(nuts, bolts, 0, bolts.length - 1);
    }
    private void sub(int[] nuts, int[] bolts, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = bolts[start];
        //sort nuts using bolt as pivot
        int index = sortNuts(nuts, pivot, start, end);
        //sort bolts using nuts[j-1] as pivot
        pivot = nuts[index];
        sortBolts(bolts, pivot, start, end);
        sub(nuts, bolts, start, index - 1);
        sub(nuts, bolts, index+1, end);
    }
    private int sortNuts(int[] nuts, int pivot, int start, int end) {
        int i = start-1, j = end+1;
        for (int index = start; index < j; index++) {
            if (Compare.cmp(nuts[index], pivot) == -1) {
                int tmp = nuts[++i];
                nuts[i] = nuts[index];
                nuts[index] = tmp;
            } else if (Compare.cmp(nuts[index], pivot) == 1) {
                int tmp = nuts[--j];
                nuts[j] = nuts[index];
                nuts[index] = tmp;
                index--;
            }
        }
        return j-1;
    }
    private int sortBolts(int[] bolts, int pivot, int start, int end) {
        int i = start-1, j = end+1;
        for (int index = start; index < j; index++) {
            if (Compare.cmp(pivot, bolts[index]) == -1) {
                int tmp = bolts[--j];
                bolts[j] = bolts[index];
                bolts[index] = tmp;
                index--;
            } else if (Compare.cmp(pivot, bolts[index]) == 1) {
                int tmp = bolts[++i];
                bolts[i] = bolts[index];
                bolts[index] = tmp;
            }
        }
        return j-1;
    }
};

Leetcode: Contains Duplicate III

用BST来维护前k个数，因此对于每个数，删除第i-k-1个数是lgn，得到ceiling和lower key分别是lgn，最后将当前数加入BST是lgn。

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null) {
            return false;
        }
        TreeMap<Long, Integer> map = new TreeMap<Long, Integer>();//pair: value-index
        for (int i = 0; i < nums.length; i++) {
            if (i > k) {
                map.remove((long)nums[i-k-1]);
            }
            long val = (long)nums[i];
            Long greater = map.ceilingKey(val);
            if (greater != null && greater - val <= t) {
                return true;
            }
            Long smaller = map.lowerKey(val);
            if (smaller != null && val - smaller <= t) {
                return true;
            }
            map.put(val, i);
        }
        return false;
    }
}

Leetcode: The Skyline Problem & Lintcode: Building Outline

把每一个building拆成两个edge，一个入一个出。所有的edge加入到一个list中。再对这个list进行排序，排序顺序为：如果两个边的position不一样，那么按pos排，否则根据edge是入还是出来排。
根据position从前到后扫描每一个edge，将edge根据是入还是出来将当前height加入或者移除heap。再得到当前最高点来决定是否加入最终结果。非常巧妙，值得思考。

public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> res = new ArrayList<int[]>();
        if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
            return res;
        }
        List<Edge> edges = new ArrayList<Edge>();
        for (int[] building : buildings) {
            Edge startEdge = new Edge(building[0], building[2], true);
            edges.add(startEdge);
            Edge endEdge = new Edge(building[1], building[2], false);
            edges.add(endEdge);
        }
        //sort edges according to position, height, and if the edge is start or end
        edges.sort(new Comparator<Edge>(){
            public int compare(Edge l1, Edge l2) {
                if (l1.pos != l2.pos)
                    return Integer.compare(l1.pos, l2.pos);
                if (l1.isStart && l2.isStart) {
                    return Integer.compare(l2.height, l1.height);
                }
                if (!l1.isStart && !l2.isStart) {
                    return Integer.compare(l1.height, l2.height);
                }
                return l1.isStart ? -1 : 1;
            }
        });
        //heap of height
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(10, Collections.reverseOrder());
        for (Edge edge : edges) {
            if (edge.isStart) {
                if (heap.isEmpty() || edge.height > heap.peek()) {
                    res.add(new int[]{edge.pos, edge.height});
                }
                heap.add(edge.height);
            } else {
                heap.remove(edge.height);
                if (heap.isEmpty() || edge.height > heap.peek()) {
                    res.add(heap.isEmpty() ? new int[]{edge.pos,0} : new int[]{edge.pos, heap.peek()});
                }
            }
        }
        return res;
    }
    class Edge implements Comparable<Edge>{
        int pos;
        int height;
        boolean isStart;
        public Edge(int pos, int height, boolean isStart) {
            this.pos = pos;
            this.height = height;
            this.isStart = isStart;
        }
    }
}

Lintcode: Kth Smallest Number in Sorted Matrix

最后一个testcase 过不了，memory limit exceeded

public class Solution {
    public int kthSmallest(final int[][] matrix, int k) {
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        PriorityQueue<int[]> heap = new PriorityQueue<int[]>(k, new Comparator<int[]>(){
            public int compare(int[] a, int[] b) {
                return Integer.compare(matrix[a[0]][a[1]], matrix[b[0]][b[1]]);
            }
        });
        heap.add(new int[]{0,0});
        visited[0][0] = true;
        while (k > 1) {
            int[] res = heap.remove();
            int x = res[0];
            int y = res[1];
            
            
            if (x+1 < matrix.length && visited[x+1][y] == false) {
                visited[x+1][y] = true;
                heap.add(new int[]{x+1, y});
            }
            if (y+1 < matrix[0].length && visited[x][y+1] == false) {
                visited[x][y+1] = true;
                heap.add(new int[]{x, y+1});
            }
            k--;
        }
        int[] res = heap.remove();
        return matrix[res[0]][res[1]];
    }
}

Lintcode: Maximum Subarray III

很难得dp题，值得多思考。
d[i][j] = max{d[p][j-1]+maxSubArray(p+1,i)}

public class Solution {
    public int maxSubArray(ArrayList<Integer> nums, int k) {
        if (nums == null || nums.size() < k) {
        	return 0;
        }
        int store[][] = new int[nums.size()+1][k+1];
        for (int sub = 1; sub <= k; sub++) {
        	for (int i = sub; i <= nums.size(); i++) {
        		long maxSum = Integer.MIN_VALUE;
        		long localSum = 0;
        		store[i][sub] = Integer.MIN_VALUE;
        		for (int j = i-1; j >= sub - 1; j--) {
        			localSum = Math.max(nums.get(j), localSum + nums.get(j));
        			maxSum = Math.max(maxSum, localSum);
        			store[i][sub] = (int) Math.max(store[j][sub-1] + maxSum, store[i][sub]);
        		}
        	}
        }
        return store[nums.size()][k];
    }
}

Lintcode: Longest Increasing Continuous subsequence II

非常好的DP + DFS题。值得多思考

public class Solution {
    public int longestIncreasingContinuousSubsequenceII(int[][] A) {
        int res = 0;
        if (A == null || A.length == 0 || A[0].length == 0) {
        	return res;
        }
        int[][] store = new int[A.length][A[0].length];
        for (int i = 0; i < A.length; i++) {
        	for (int j = 0; j < A[0].length; j++) {
        		if (store[i][j] == 0) {
        			res = Math.max(res, dfs(A, store, i, j));
        		}
        	}
        }
        return res;
    }
    private int dfs(int[][] a, int[][] store, int i, int j) {
    	if (store[i][j] != 0) {
    		return store[i][j];
    	}
    	int left = 0, right = 0, up = 0, down = 0;
    	if (j + 1 < a[0].length && a[i][j+1] > a[i][j]) {
    		right = dfs(a, store, i, j+1);
    	}
    	if (j > 0 && a[i][j-1] > a[i][j]) {
    		left = dfs(a, store, i, j-1);
    	}
    	if (i + 1 < a.length && a[i+1][j] > a[i][j]) {
    		down = dfs(a, store, i+1, j);
    	}
    	if (i > 0 && a[i-1][j] > a[i][j]) {
    		up = dfs(a, store, i-1, j);
    	}
    	store[i][j] = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
    	return store[i][j];
    }
}

Lintcode: Coins in a Line III

dp题，主要是要推导出公式：
dp[i][j]=max(A[i]+sum[i+1][j]-dp[i+1][j], A[j]+sum[i][j-1]-dp[i][j-1])
A[i]+sum[i+1][j] 和 A[j]+sum[i][j-1]都等于sum[i][j],因此最后公式成为：
dp[i][j]=sum[i][j]-min(dp[i+1][j],dp[i][j-1])
比较特别的dp题。game theory。

public class Solution {
    public boolean firstWillWin(int[] values) {
        int len = values.length;
        if (len <= 1) {
            return true;
        }
        int[][] store = new int[len][len];
        int[][] sum = new int[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                sum[i][j] = i == j ? values[j] : sum[i][j-1] + values[j];
            }
        }
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (i == j) {
                    store[i][j] = values[i];
                } else {
                    int cur = Math.min(store[i+1][j], store[i][j-1]);
                    store[i][j] = sum[i][j] - cur;
                }
            }
        }
        return store[0][len - 1] > sum[0][len-1] - store[0][len - 1];
    }
}

Lintcode: Longest Substring with At Most K Distinct Characters

解法是维护一个sliding window，以及一个hash map， key是char，value是这个char在当前window中得出现次数。
start和end是当前字符串的起始和终止index。
当当前window 字符数超过k的时候，从start开始remove，只要遇到一个char的个数降为0的时候，可以跳出，因为说明当前window的char个数已经为k-1,满足条件。
如果字符集比较小的话可以维护一个int[]来对char计数。

public class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (s == null || s.length() == 0 || k <= 0) {
            return 0;
        }
        int start = 0;
        int res = 1;
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        map.put(s.charAt(0), 1);
        for (int end = 1; end < s.length(); end++) {
            char ch = s.charAt(end);
            if (map.containsKey(ch)) {
                map.put(ch, map.get(ch)+1);
            } else {
                if (map.size() == k) {
                    res = Math.max(res, end - start);
                    //full map, need to remove the first character in ths substring
                    for (int index = start; index < end; index++) {
                        map.put(s.charAt(index), map.get(s.charAt(index))-1);
                        start++;
                        if (map.get(s.charAt(index)) == 0) {
                            //have removed all occurance of a char
                            map.remove(s.charAt(index));
                            break;
                        }
                    }
                }
                map.put(ch, 1);
            }
        }
        res = Math.max(res, s.length() - start);
        return res;
    }
}

Lintcode: Sliding Window Maximum

Solution 1: 用heap保存对。虽然能通过OJ，但是复杂度并不对

public class Solution {
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
    	ArrayList<Integer> res = new ArrayList<Integer>();
    	if (nums == null || nums.length == 0 || k <= 0) {
    		return res;
    	}
    	PriorityQueue<Pair> heap = new PriorityQueue<Pair>();
    	for (int i = 0; i < k; i++) {
    		heap.add(new Pair(nums[i], i));
    		//res.add(heap.peek().val);
    	}
    	for (int i = k; i < nums.length; i++) {
    	    res.add(heap.peek().val);
    		Pair toRemove = heap.peek();
    		while (!heap.isEmpty() && heap.peek().index <= i - k) {
    			heap.remove();
    		}
    		heap.add(new Pair(nums[i], i));
    	}
    	res.add(heap.peek().val);
    	return res;
    }
    class Pair implements Comparable<Pair> {
    	int val;
    	int index;
    	public Pair(int val, int index) {
    		this.val = val;
    		this.index = index;
    	}
    	@Override
		public int compareTo(Pair p) {
			return Integer.compare(p.val, val);
		}
    }
}

Solution 2: 用double end queue– Deque.将当前元素加在queue的最后，但是加之前把所有比当前值小的元素从后往前删掉，这样就保证了一个按照index顺序维护的降序queue。非常好的思路。

public class Solution {
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
    	ArrayList<Integer> res = new ArrayList<Integer>();
    	if (nums == null || nums.length == 0 || k <= 0) {
    		return res;
    	}
    	Deque<Integer> dQueue = new LinkedList<Integer>();
    	for (int i = 0; i < k; i++) {
    		while (!dQueue.isEmpty() && nums[dQueue.peekLast()] <= nums[i]) {
    			dQueue.removeLast();
    		}
    		dQueue.addLast(i);
    	}
    	for (int i = k; i < nums.length; i++) {
    	    res.add(nums[dQueue.peekFirst()]);
    		while (!dQueue.isEmpty() && dQueue.peek() <= i - k) {
    			dQueue.removeFirst();
    		}
    		while (!dQueue.isEmpty() && nums[dQueue.peekLast()] <= nums[i]) {
    			dQueue.removeLast();
    		}
    		dQueue.addLast(i);
    	}
    	res.add(nums[dQueue.peekFirst()]);
    	return res;
    }
}