Best Time to Buy and Sell Stock I, II, III @LeetCode

Say you have an array for which the ith element is the price of a given stock on day i.

I. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

II. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

III. Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

	package leetcode;
	/**
	* Sotck III Solution: DP.
	* First, consider O(n^2) solution. Find a midmpoint i, [0,i] [i+1, n-1] find two profit of each range. --> Best Stock I solution
	* then, i could starts from 0 to n-1, in each loop, there's two O(n). the final merge part will be O(n)
	* O(2n^2) + O(n) -> O(n^2), now we consider optimization.
	*
	* DP:
	* calculate price[0..i] --> price[0..i+1], we could use O(1) time like Stock I way but not use calculate using O(n) again.
	* What about price[i..n-1] --> price[i+1..n-1]? Same, easy get profit[i,n-1] from profit[i+1,n-1].
	* left[i] stores most profit from price[0..i]
	* right[i] stores most profit form price[i+1, n-1]. we can only calculate right[] from right to left.
	* We use O(n) to find out the max(left[i] + right[i])
	*
	* Reference: http://blog.csdn.net/fightforyourdream/article/details/14503469
	*
	* Test case:
	* prices = {1, 2, 5, 9, 4, 3, 7, 8, 5} result = 13
	* left = [0, 1, 4, 8, 8, 8, 8, 8, 8]
	* right = [8, 7, 5, 5, 5, 5, 1, 0, 0]
	* @author jeffwan
	* @date Mar 31, 2014
	*/
	public class MaxProfit {
	// Best Time to Buy and Sell Stock III
	public int maxProfit3(int[] prices) {
	if (prices == null || prices.length == 0) {
	return 0;
	}
	int[] left = new int[prices.length]; // left[i] means highest profit in (0..i)
	int[] right = new int[prices.length];
	// DP from left to right
	left[0] = 0; // DP initial state
	int min = prices[0];
	for (int i = 1; i < prices.length; i++) {
	min = Math.min(min, prices[i]);
	left[i] = Math.max(left[i - 1], prices[i] - min);
	}
	// DP from right to left
	right[prices.length - 1] = 0; // DP initial state
	int max = prices[prices.length - 1];
	for (int i = prices.length - 2; i >= 0; i--) {
	max = Math.max(max, prices[i]);
	right[i] = Math.max(right[i + 1], max - prices[i]);
	}
	int profit = 0;
	for (int i = 0; i < prices.length; i++) {
	profit = Math.max(profit, left[i] + right[i]);
	}
	return profit;
	}
	// Best Time to Buy and Sell Stock I
	/**
	* Solution: Find the increasing pair(lowest, highest), Only need to record lowest prices, and profit.
	*/
	public int maxProfit1(int[] prices) {
	if (prices == null || prices.length == 0) {
	return 0;
	}
	int lowest = Integer.MAX_VALUE;
	int profit = 0;
	for (int currentPrice : prices) {
	lowest = Math.min(lowest, currentPrice);
	profit = Math.max(profit, currentPrice - lowest);
	}
	return profit;
	}
	// Best Time to Buy and Sell Stock II
	/**
	* Solution: Add all increasing pairs.
	*
	* Myway: 5 7 9 3 6 4 (5,9) (3,6) only prices[i+1] < prices[i] add profit to result; but it's meaningless.
	* just add (5,7) (7,9) (3,6) make it easy
	*
	*/
	public int maxProfit2(int[] prices) {
	if (prices == null || prices.length == 0) {
	return 0;
	}
	int profit = 0;
	for (int i = 0; i < prices.length - 1; i++) {
	int signleProfit = prices[i + 1] - prices[i];
	if (signleProfit > 0) {
	profit += signleProfit;
	}
	}
	return profit;
	}
	// Stock I : Brute Force O(n^2) Time Limit Exceeded -- Wrong. sale at highest first, and buy at lowest are not accepted.
	// Arrays.sort(prices). return prices[length - 1] - prices[0] also doesn't work.
	// My mistake: (highest, lowest) doesn't mean profit!
	public int maxProfitWrongWay(int[] prices) {
	if (prices == null || prices.length == 0) {
	return 0;
	}
	int result = Integer.MIN_VALUE;
	for (int i = 0; i < prices.length; i++) {
	for (int j = 0; j < prices.length; j++) {
	result = Math.max(result, Math.abs(prices[i] - prices[j]));
	}
	}
	return result;
	}
	}

view raw MaxProfit.java hosted with ❤ by GitHub

4Sum @LeetCode

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

	package leetcode;
	import java.util.ArrayList;
	import java.util.Arrays;
	/**
	* Solution: Same to 3Sum, 2Sum
	* O(n^3)
	* @author jeffwan
	* @date Mar 23, 2014
	*/
	public class FourSum {
	public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	if (num == null || num.length < 4) {
	return result;
	}
	Arrays.sort(num);
	int start, end, sum;
	for (int i = 0; i < num.length - 3; i++) {
	if (i != 0 && num[i] == num[i - 1]) {
	continue;
	}
	for (int j = i + 1; j < num.length - 2; j++) {
	if (j != i + 1 && num[j] == num[j - 1]) {
	continue;
	}
	start = j + 1;
	end = num.length - 1;
	while(start < end) {
	sum = num[i] + num[j] + num[start] + num[end];
	if (sum == target) {
	ArrayList<Integer> temp = new ArrayList<Integer>();
	temp.add(num[i]);
	temp.add(num[j]);
	temp.add(num[start]);
	temp.add(num[end]);
	result.add(temp);
	start++;
	end--;
	while (start < end && num[start] == num[start - 1]) {
	start++;
	}
	while (start < end && num[end] == num[end + 1]) {
	end--;
	}
	} else if (sum < target) {
	start++;
	} else {
	end--;
	}
	}
	}
	}
	return result;
	}
	}

view raw FourSum.java hosted with ❤ by GitHub

3Sum Closest @LeetCode

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

	package leetcode;
	import java.util.Arrays;
	/**
	* Solution: Same to 3Sum
	*
	* Compare Math.abs(x - target) to see which one is more closest.
	*
	* Test case: target = -1.
	* Integer.MAX_VALUE - target = Integer.MIN_VALUE. Math.abs(Integer.MIN_VALUE) < 0 ! Math.abs(Integer.MIN_VALUE + 1) > 0
	* So we can't give MAX_VALUE to closest as it may overflow. We use MAX_VALUE/2
	*
	* @author jeffwan
	* @date Mar 23, 2014
	*/
	public class ThreeSumClosest {
	public int threeSumClosest(int[] num, int target) {
	if (num == null || num.length < 3) {
	return Integer.MAX_VALUE;
	}
	Arrays.sort(num);
	int closest = Integer.MAX_VALUE / 2;
	int start, end, sum;
	for(int i = 0; i < num.length - 2; i++) {
	start = i + 1;
	end = num.length - 1;
	while (start < end) {
	sum = num[i] + num[start] + num[end];
	if (sum == target) {
	return sum;
	} else if(sum < target){
	start++;
	} else {
	end--;
	}
	closest = Math.abs(closest - target) < Math.abs(sum - target) ? closest : sum;
	}
	}
	return closest;
	}
	}

view raw ThreeSumClosest.java hosted with ❤ by GitHub

3Sum @LeetCode

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

	package leetcode;
	import java.util.ArrayList;
	import java.util.Arrays;
	/**
	* Solution: convert 3sum -> 2 sum.
	* Retrieve one number, use two pointer on last array to find num[start]+ num[end] == 0 - num[i]
	*
	* At first, I use result.contains(triple) to remove duplicates. But keys here is skip duplicate elements
	* 1. skip duplicate i
	* 2. skip duplicate start,end.
	*
	* O(nlogn) + O(n^2) = O(n^2)
	* @author jeffwan
	* @date Mar 23, 2014
	*/
	public class ThreeSum {
	public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	if (num == null || num.length < 3) {
	return result;
	}
	Arrays.sort(num);
	int start, end;
	for (int i = 0; i < num.length - 2; i++) {
	if (i != 0 && num[i] == num[i-1]) {
	continue;
	}
	start = i + 1;
	end = num.length - 1;
	while(start < end) {
	if (num[start] + num[end] == 0 - num[i]) {
	ArrayList<Integer> triplet = new ArrayList<Integer>();
	triplet.add(num[i]);
	triplet.add(num[start]);
	triplet.add(num[end]);
	start++;
	end--;
	while (start < end && num[start] == num[start - 1]) {
	start++;
	}
	while (start < end && num[end] == num[end + 1]) {
	end--;
	}
	result.add(triplet);
	} else if (num[start] + num[end] > 0 - num[i]) {
	end--;
	} else {
	start++;
	}
	}
	}
	return result;
	}
	}

view raw ThreeSum.java hosted with ❤ by GitHub

Jump Game II @LeetCode

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

	package leetcode.dp;
	import java.util.Arrays;
	/**
	* Solution: Sequence DP - a little similar to Jump Game1.
	* step[i] means total steps from start to i.
	*
	* Take care:
	* 1. step[0] = 0, from 0 to 0, 0 step is needed.
	* 2. j goes further even if we get a little result. This is a point we must optimize. if we don't time limit exceed here.
	* Example: 2,3,1,1,4. i=4,j=1, j+A[j]>=i, we don't need to calculate j=2...
	*
	* Refactor: 最短的路径一定是第一个j能够跳到i的，所以直接+1，break就可以了, 之前的思路，遍历j，求Math.min(step[i], step[j] + 1) 没必要，后面根本不用去计算
	*
	* @author jeffwan
	* @date Mar 12, 2014 || Refactor May 5
	*/
	public class Jump {
	public int jump(int[] A) {
	if (A == null || A.length == 0) {
	return -1;
	}
	int[] step = new int[A.length];
	step[0] = 0;
	for (int i = 1; i < A.length; i++) {
	for (int j = 0; j < i; j++) {
	if (j + A[j] >= i) {
	step[i] = step[j] + 1;
	break;
	}
	}
	}
	return step[A.length - 1];
	}
	}

view raw Jump.java hosted with ❤ by GitHub

Interleaving String @LeetCode

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

	package leetcode.dp;
	/**
	* Solution: Two sequence DP
	* interleave[i][j] means if (0,i) of s1, and (0,j) of s2 could from (0,i+j) of s3.
	* Three situation:
	* 1. s1(i) = s3(i+j). --> convert to interleave[i-1][j]
	* 2. s2(i) = s3(i+j). --> convert to interleave[i][j-1]
	* 3. not equal. interleave[i][j] = false
	*
	* Initialize -- Matrix we need to initialize first line and column.
	* interleave[i][0] --> s1(0,i) and s3(0,i). interleave[0][i] --> s2 (0,i) and s3(0,i)
	*
	* Test case: ab bc babc interleave[2,1] if s1[i-1] = s2[j-1] = s3[i+j-1].
	* s2[j-1] = s3[i+j-1] result may overlap previous result.
	* So we must use interleave[][] = interleave[][] || previouseValue here. can't give the value directly.
	*
	* @author jeffwan
	* @date Mar 12, 2014
	*/
	public class IsInterleave {
	public boolean isInterleave(String s1, String s2, String s3) {
	if (s1 == null || s2 == null || s3 == null) {
	return false;
	}
	if (s1.length() + s2.length() != s3.length()) {
	return false;
	}
	boolean[][] interleave = new boolean[s1.length() + 1][s2.length() + 1];
	interleave[0][0] = true;
	for (int i = 1; i <= s1.length(); i++) {
	interleave[i][0] = s1.substring(0, i).equals(s3.substring(0, i));
	}
	for (int i = 1; i <= s2.length(); i++) {
	interleave[0][i] = s2.subSequence(0, i).equals(s3.substring(0, i));
	}
	for (int i = 1; i <= s1.length(); i++) {
	for (int j = 1; j <= s2.length(); j++) {
	interleave[i][j] = false;
	if (s1.charAt(i-1) == s3.charAt(i + j -1)) {
	interleave[i][j] = interleave[i][j] || interleave[i - 1][j];
	}
	if (s2.charAt(j-1) == s3.charAt(i + j -1)) {
	interleave[i][j] = interleave[i][j] || interleave[i][j - 1];
	}
	}
	}
	return interleave[s1.length()][s2.length()];
	}
	}

view raw IsInterleave.java hosted with ❤ by GitHub

Edit Distance @LeetCode

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

	package leetcode.dp;
	/**
	* Solution: Two sequence DP
	* distance[i][j] means minimum changes that first i char in word1 associated with first j char in word2.
	*
	* Three situation: (delete is same to insert)
	* delete s[i], --> distance[i-1][j] + 1
	* delete s[j], --> distance[i][j-1] + 1
	* change: s[i] = s[j] (i=j or i!=j), --> distance[i-1][j-1], no operation, if not, --> distance[i-1][j-1] + 1
	*
	* There no relationship between delete,change operation and if i > j, i < j, i = j, it all depends on previous result.
	* Like change, i may not equals j, example: ab acb, just need one step but not delete b and change again.
	* We don't need to judge which condition it is. Second one will overlap first one if it's smaller.
	*
	* @author jeffwan
	* @date Mar 12, 2014
	*/
	public class MinDistance {
	public int minDistance(String word1, String word2) {
	if (word1 == null || word2 == null) {
	return -1;
	}
	int m = word1.length() + 1;
	int n = word2.length() + 1;
	int[][] distance = new int[m][n];
	// Initialize
	for (int i = 0; i < m; i++) {
	distance[i][0] = i;
	}
	for (int i = 0 ; i < n; i++) {
	distance[0][i] = i;
	}
	for (int i = 1; i < m; i++) {
	for (int j = 1; j < n; j++) {
	distance[i][j] = Math.min(distance[i - 1][j], distance[i][j - 1]) + 1;
	distance[i][j] = Math.min(distance[i][j],
	distance[i - 1][j - 1] + (word1.charAt(i-1) == word2.charAt(j -1) ? 0: 1));
	}
	}
	return distance[m - 1][n - 1];
	}
	}

view raw MinDistance.java hosted with ❤ by GitHub

Palindrome Partitioning II @LeetCode

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

	package leetcode.dp;
	/**
	* Palindrome Partitioning II
	* Solution: sequence DP (very classic)
	* cut[i] --> minimum cut from start to i 这里其实是可以切割的最少的段数，最后结果还要-1，转成切多少刀
	* Because we find the best value, we need j start from 1 to i.
	* cut[i] should get minimum from cut[i] (previous j loop) and cut[i-j]+1(current result)
	*
	* isPalindrome optimization: if use isPalindrome directly, time -> O(n*n*n) (Time limit exceed), we can make it O(n*n);
	* also a DP problem: isPalindrome[i,j] -> [i+1, j-1] && s[i] == s[j] (formula works for j >= i+2)
	*
	* length = 0, i = j, all single char isPalindrome.
	* length = 1, judge if s(i) == s(i+1)
	* length >=2, formula
	*
	* Update notes:
	* 1. 面试的话就写isPalindrome, 不用去直接写优化(预处理), 脑子转不过来的
	* 2. 这题跟Jump Game II, Word Break 更有一部分很像，好好理解
	*
	* @author jeffwan
	* @date Mar 12, 2014 Update May 05
	*/
	public class MinCut {
	public static void main(String[] args) {
	String s = "aab";
	System.out.println(minCut(s));
	}
	public static int minCut(String s) {
	if(s == null || s.length() == 0) {
	return 0;
	}
	int[] cut = new int[s.length() + 1];
	boolean[][] isPalindrome = getIsPalindrome(s);
	cut[0] = 0;
	for (int i = 1; i <= s.length(); i++) {
	cut[i] = Integer.MAX_VALUE;
	for (int j = 1; j <= i; j++) {
	// or use isPalindrome[i - j][i - 1] to replace isPalindrome(s.substring(i - j, i))
	if (isPalindrome(s.substring(i - j, i)) && cut[i - j] != Integer.MAX_VALUE) {
	cut[i] = Math.min(cut[i], cut[i - j] + 1);
	}
	}
	}
	return cut[s.length()] - 1;
	}
	// isPalindrome[i][j] means if s.substring(i,j+1) isPalindrome.
	private static boolean[][] getIsPalindrome(String s) {
	boolean[][] isPalindrome = new boolean[s.length()][s.length()];
	for (int i = 0; i < s .length(); i++) {
	isPalindrome[i][i] = true;
	}
	for (int i = 0; i < s.length() - 1; i++) {
	isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
	}
	// Previous codes handles length = 0 & length = 1
	for (int length = 2; length < s.length(); length++) {
	for (int i = 0; i + length < s.length(); i ++) {
	isPalindrome[i][i + length]
	= isPalindrome[i + 1][i + length - 1] && s.charAt(i) == s.charAt(i + length);
	}
	}
	return isPalindrome;
	}
	// 想不出上面优化的方法就用这个，最后总的就是O(n^3); 这样在leetcode上会Time Limit Exceed, 但是面试应该没问题
	private static boolean isPalindrome(String s) {
	int start = 0;
	int end = s.length() - 1;
	while(start < end) {
	if (s.charAt(start) != s.charAt(end)) {
	return false;
	}
	start++;
	end--;
	}
	return true;
	}
	}

view raw MinCut.java hosted with ❤ by GitHub

Word Break @LeetCode

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

	package leetcode.dp;
	import java.util.HashSet;
	import java.util.Set;
	/**
	* Solution: Sequence DP
	* canSegment[i] --> if 0 - i could be segmented.
	* canSegment[i] = true, canSegment[i-j] = true, [i-j,i] is a word
	* Here we use j goes from j goes from rear to head. to find if canSegment[i-j] is true,
	* if so, we substring the last j word to see if it is in dict, if so, 0-i can be segmented.
	*
	* 优化思路
	* 1. j 实际上是从后面切，切一个词，然后判断前面canSegment[i - j] 是不是可切，
	* 切的时候，如果超过最长的单词长度就没意义了，因为长度大于maxWordLength ，必然不在dict中
	* 2. 可以break，跟jumpGame一样思路
	*
	* @author jeffwan
	* @date Mar 12, 2014 UpdateNotes May 5 Updates Jan 5, 2015
	*/
	public class WordBreak {
	public boolean wordBreak(String s, Set<String> dict) {
	if (s == null || s.length() == 0) {
	return false;
	}
	int maxLength = getMaxLength(dict);
	boolean[] canSegment = new boolean[s.length() + 1];
	canSegment[0] = true;
	for (int i = 1; i <= s.length(); i++) {
	canSegment[i] = false;
	for (int j = 1; j <= maxLength && j <= i; j++) {
	// 1. last j char is a word
	String word = s.substring(i - j, i);
	// 2. first i -j can be segmented
	if (canSegment[i - j] && dict.contains(word)) {
	canSegment[i] = true;
	break;
	}
	}
	}
	return canSegment[s.length()];
	}
	public int getMaxLength(Set<String> dict) {
	int maxLenght = 0;
	for (String word : dict) {
	maxLenght = Math.max(maxLenght, word.length());
	}
	return maxLenght;
	}
	}

view raw WordBreak.java hosted with ❤ by GitHub

Jump Game @LeetCode

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

	package leetcode.dp;
	/**
	* Solution: Sequence DP
	* can[i] if first number could jump to i. If first node could jump to i: can[j] && j+A[j]>=i
	*
	* 1. if we could jump to the last index, all previous node could be jumped to.
	* 2. we use j from 0 to i to search which point could jump to i
	*
	* Sequence DP Conclusion: can[i] means what we want. use loop from 0 to i to check the how is last step
	*
	* @author jeffwan
	* @date Mar 12, 2014
	*/
	public class CanJump {
	public boolean canJump(int[] A) {
	if (A == null || A.length == 0) {
	return false;
	}
	boolean[] can = new boolean[A.length];
	can[0] = true;
	for(int i = 1; i < can.length; i++) {
	for (int j = 0; j < i; j++) {
	if (can[j] && j + A[j] >= i) {
	can[i] = true;
	break;
	}
	}
	}
	return can[A.length - 1];
	}
	}

view raw CanJump.java hosted with ❤ by GitHub

Minimum Path Sum @LeetCode

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

	package leetcode.dp;
	/**
	* Solution: Matrix DP (Similar to Triangle and UniquePath)
	* This problem is matrix but not triangle, they both find the minimum path.
	* As it's matrix and it's behavior are same to UniquePath, we could the similar way.
	*
	* Difference: minSum[i][j] means the minPath from (0,0) to (x,y). calculate sum.
	* So initialization will not minSum[i][0] = grid[i][0] !! don't confused with UniquePath here.
	*
	* @author jeffwan
	* @date Mar 12, 2014
	*/
	public class MinPathSum {
	public int minPathSum(int[][] grid) {
	if (grid == null || grid.length == 0 || grid[0].length == 0) {
	return 0;
	}
	int m = grid.length;
	int n = grid[0].length;
	int[][] minSum = new int[m][n];
	minSum[0][0] = grid[0][0];
	for (int i = 1; i < m; i++) {
	minSum[i][0] = minSum[i - 1][0] + grid[i][0];
	}
	for (int i = 1; i < n; i++) {
	minSum[0][i] = minSum[0][i - 1] + grid[0][i];
	}
	for (int i = 1; i < m; i++) {
	for (int j = 1; j < n; j++) {
	minSum[i][j] = Math.min(minSum[i - 1][j], minSum[i][j - 1]) + grid[i][j];
	}
	}
	return minSum[m - 1][n - 1];
	}
	}

view raw MinPathSum.java hosted with ❤ by GitHub

Unique Paths II @LeetCode

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

	package leetcode.dp;
	/**
	* Solution: Matrix DP (same to UniquePath I, just add some conditions)
	* Notice:
	* 1. if obstacle[i][0], we need to break, but not sum[i][0] = 0, all the following paths are blocked.
	* but if we set sum[i][0] = 0, it will skip this point and sum[i+1][0] = 1 again.
	*
	* 2. We only handle the first line and column obstacles in initialization but not handle other.
	* Other obstacles should be handled in for loop. if there's obstacle, sum[i][j] = 0, can't be reached.
	*
	* @author jeffwan
	* @date Mar 12, 2014
	*/
	public class UniquePathsWithObstacles {
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
	if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0].length == 0) {
	return 0;
	}
	int m = obstacleGrid.length;
	int n = obstacleGrid[0].length;
	int[][] sum = new int[m][n];
	for (int i = 0; i < m; i++) {
	if (obstacleGrid[i][0] == 1) {
	break;
	} else {
	sum[i][0] = 1;
	}
	}
	for (int i = 0; i < n; i++) {
	if (obstacleGrid[0][i] == 1) {
	break;
	} else {
	sum[0][i] = 1;
	}
	}
	for (int i = 1; i < m; i++) {
	for (int j = 1; j < n; j++) {
	if (obstacleGrid[i][j] == 1) {
	sum[i][j] = 0;
	} else {
	sum[i][j] = sum[i - 1][j] + sum[i][j - 1];
	}
	}
	}
	return sum[m - 1][n - 1];
	}
	}

view raw UniquePathsWithObstacles.java hosted with ❤ by GitHub

Unique Paths @LeetCode

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

	package leetcode.dp;
	/**
	* Solution: Matrix DP
	* sum[i][j] means all solutions start from (0,0) to (i,j).
	* sum[i][j] = sum[i-1][j] + sum[i][j-1] --> solution at (i,j) comes from left(i-1,j) and up(i,j-1)
	*
	* A little similiar to minimum path Bottom-Up iterative. (Initial sum, and calculate sum to destination)
	* Initial is very important. We must initial first line and column in Matrix DP problem. and then, i,j starts from 1
	*
	* @author jeffwan
	* @date Mar 12, 2014
	*/
	public class UniquePaths {
	public int uniquePaths(int m, int n) {
	if (m == 0 || m == 0) {
	return 0;
	}
	int[][] sum = new int[m][n];
	for (int i = 0; i < m; i++) {
	sum[i][0] = 1;
	}
	for (int i = 0; i < n; i++) {
	sum[0][i] = 1;
	}
	for (int i = 1; i < m; i++) {
	for (int j = 1; j < n; j++) {
	sum[i][j] = sum[i - 1][j] + sum[i][j - 1];
	}
	}
	return sum[m - 1][n - 1];
	}
	}

view raw UniquePaths.java hosted with ❤ by GitHub

Populating Next Right Pointers in Each Node II @LeetCode

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

My solution using level order traversal solves both I and II. please check
Populating Next Right Pointers in Each Node @LeetCode

Climbing Stairs @LeetCode

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

	package leetcode.dp;
	/**
	* Solution: DP
	* search(x) means to find how many ways x goes to n. return sum[x];
	* every point has 2 ways to go forwad, move 1 step or 2. sum[x] = search(x+1) + search (x+2);
	*
	* We could also define search(i) as solutions from 0 to i. start from n
	* search(x) = search(x-1) + search(x-2) --> a little complicated because of indexOfBound.
	*
	* @author jeffwan
	* @date Mar 12, 2014
	*/
	public class ClimbStairs {
	private int[] sum;
	private int n;
	public int climbStairs(int n) {
	this.n = n;
	this.sum = new int[n];
	for (int i = 0; i < n; i++) {
	sum[i] = Integer.MIN_VALUE;
	}
	return search(0);
	}
	public int search(int x) {
	if (x == n) {
	return 1;
	}
	if (x > n) {
	return 0;
	}
	if (sum[x] != Integer.MIN_VALUE) {
	return sum[x];
	}
	sum[x] = search(x + 1) + search(x + 2);
	return sum[x];
	}
	// Another Defination of sum[x], 还是喜欢定义sum[i] 代表从 0 到 i的状态，
	// 这里要用sum[] 来存储值，这样可以大量减少递归调用的次数，体现记忆化搜索
	public int climbStairs2(int n) {
	sum = new int[n];
	for (int i = 0; i < n; i++) {
	sum[i] = Integer.MIN_VALUE;
	}
	return search2(n - 1);
	}
	public int search2(int i) {
	if (i == 0) {
	return 1;
	}
	if (i == 1) {
	return 2;
	}
	if( i < 1){
	return 0;
	}
	if (sum[i] != Integer.MIN_VALUE) {
	return sum[i];
	}
	sum[i] = search2(i - 1) + search2(i - 2);
	return sum[i];
	}
	// 这种跟fabonacci几乎是一样的, 这是上面形式的非递归写法，每个值只参与两次计算，不用优化了
	public int climbStairs3(int n) {
	if (n == 1) {
	return 1;
	}
	if (n == 2) {
	return 2;
	}
	int[] sum = new int[n];
	sum[0] = 1;
	sum[1] = 2;
	for (int i = 2; i < n; i++) {
	sum[i] = sum[i - 1] + sum[i - 2];
	}
	return sum[n - 1];
	}
	}

view raw ClimbStairs.java hosted with ❤ by GitHub

Triangle @LeetCode

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

	package leetcode.dp;
	import java.util.ArrayList;
	/**
	* Solution:
	* 1. DP. DFS
	* search(x, y) means to find the minimum path going from point(x,y) to the end. return minSum.
	* Usually we use search(x,y) means minSum from (0,0) to (x,y), but here we change our mind.
	* every node will be calculate once, O(2^n) --> O(n2)
	* (1,1) -> (2,1),(2,2)
	* (2,1) -> (3,1),(3,2) (2,2) ->(3,2),(3,3) (3,2) will be used two time --> memory search.
	*
	* 2. Bottom-Up Iterative
	* initial last line and calculate sum of parent node sum[i][j] = Math.min(s[i+1][j], s[i+1][j+1]) + s[i][j]
	* My concern [4,1,8,2] even 1 < 2, but sum may not, if up line is [8,7,5]. 2+5 < 1+7.
	* Actually, In DP problem, we don't care the path, just minimum path value. Every bottom line will embedd in up line.
	*
	* @author jeffwan
	* @date Mar 12, 2014
	*/
	public class MinimumTotal {
	private int n;
	private int[][] minSum;
	private ArrayList<ArrayList<Integer>> triangle;
	public int search (int x, int y) {
	if (x >= n) {
	return 0;
	}
	// Memory Search (some points may be used multiple times.)
	if (minSum[x][y] != Integer.MAX_VALUE) {
	return minSum[x][y];
	}
	minSum[x][y] = Math.min(search(x + 1, y), search(x + 1, y + 1)) + triangle.get(x).get(y);
	return minSum[x][y];
	}
	public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
	if (triangle == null || triangle.size() == 0) {
	return 0;
	}
	this.n = triangle.size();
	this.triangle = triangle;
	this.minSum = new int[n][n];
	for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
	minSum[i][j] = Integer.MAX_VALUE;
	}
	}
	return search(0, 0);
	}
	// Bottom-Up Solution
	public int minimumTotal2(ArrayList<ArrayList<Integer>> triangle) {
	if (triangle == null || triangle.size() == 0) {
	return 0;
	}
	int n = triangle.size();
	int[][] sum = new int[n][n];
	for (int i = 0; i < n; i++) {
	sum[n - 1][i] = triangle.get(n - 1).get(i);
	}
	for (int i = n -2; i >= 0; i--) {
	for (int j = 0; j <= i; i++) { // j < triangle.get(i).size()
	sum[i][j] = Math.min(sum[i + 1][j], sum[i + 1][j + 1]) + triangle.get(i).get(j);
	}
	}
	return sum[0][0];
	}
	}

view raw MinimumTotal.java hosted with ❤ by GitHub

Symmetric Tree @LeetCode

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

	package leetcode.tree;
	/**
	* Solution: DFS. Need to judge subtree, if can't get result, go depth.
	* 1. Structure
	* 2. Value
	*
	* Two pairs (left.left, right.right) && (left.right, right.left)
	*
	* @author jeffwan
	* @date Mar 11, 2014
	*/
	public class IsSymmetric {
	public boolean isSymmetric(TreeNode root) {
	if (root == null) {
	return true;
	}
	return helper(root.left, root.right);
	}
	private boolean helper(TreeNode left, TreeNode right) {
	if (left == null && right == null) {
	return true;
	}
	if ((left != null && right == null) || (left == null && right != null)
	|| (left.val != right.val)) {
	return false;
	}
	return helper(left.left, right.right) && helper(left.right, right.left);
	}
	class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw IsSymmetric.java hosted with ❤ by GitHub

Roman to Integer @LeetCode

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

	package leetcode;
	/**
	* Solution: easier than intToRoman. just need to get every Roman char and map it to int.
	* Only thing need to care is situation like 'XL', 'CM'. X < L, C < M.
	* Before we add to result, we need to check if last char < current char
	*
	* Add last char first, if last < current, minus 2 * last, add current,
	* if current < next, current will be lastNode next loop.
	* Actually, no possibility pre < current < next. only happens in two pairs (we could know this from IntToRoman, every digit is individual)
	*
	* Reference: http://blog.csdn.net/wzy_1988/article/details/17057929
	* @author jeffwan
	* @date Mar 11, 2014
	*/
	public class RomanToInt {
	public int romanToInt(String s) {
	int result = charToInt(s.charAt(0));
	for (int i = 1; i < s.length(); i++) {
	int last = charToInt(s.charAt(i - 1));
	int current = charToInt(s.charAt(i));
	if (last < current) {
	result += current - 2 * last;
	} else {
	result += current;
	}
	}
	return result;
	}
	public int charToInt(char c) {
	switch (c) {
	case 'I':
	return 1;
	case 'V':
	return 5;
	case 'X':
	return 10;
	case 'L':
	return 50;
	case 'C':
	return 100;
	case 'D':
	return 500;
	case 'M':
	return 1000;
	default:
	return 0;
	}
	}
	}

view raw RomanToInt.java hosted with ❤ by GitHub

Integer to Roman @LeetCode

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

	package leetcode;
	/**
	* Solution: judge digit in different situation
	* Actually, every digit is individually that will not infect other digit.
	* So we only need to consider following five situation in every digit and then merge them together. not hard as I think.
	* Integer Tool: get digit -- > num / base. move --> num % base
	*
	* digit == 0
	* 0 < digit <=3
	* digit == 4
	* 5 <= digit < 9
	* digit == 9
	*
	* Take care of i = roman.length + 1, as I,V cross one digit(0-9). X,L(10-100). i = i-2 every time.
	* Every digit's mapping may use index i-2(0-4), i-1(5-8), i(9) **** important.
	*
	* Reference:
	* http://literacy.kent.edu/Minigrants/Cinci/romanchart.htm
	* http://blog.csdn.net/wzy_1988/article/details/17515583
	*
	* @author jeffwan
	* @date Mar 11, 2014
	*/
	public class IntToRoman {
	public String intToRoman(int num) {
	StringBuilder sb = new StringBuilder();
	int base = 1000;
	int digit = 0;
	char[] roman = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
	for(int i = roman.length + 1; i >= 0 && num > 0; i -= 2, base /= 10) {
	digit = num / base;
	if (digit == 0) {
	continue;
	}
	if(digit <= 3) {
	for (int j = 0; j < digit; j++) {
	sb.append(roman[i - 2]);
	}
	} else if(digit == 4) {
	sb.append(roman[i - 2]);
	sb.append(roman[i - 1]);
	} else if (digit <= 8) {
	sb.append(roman[i - 1]);
	for(int j = digit - 5; j > 0; j--) {
	sb.append(roman[i - 2]);
	}
	} else if (digit == 9) {
	sb.append(roman[i - 2]);
	sb.append(roman[i]);
	}
	num = num % base;
	}
	return sb.toString();
	}
	}

view raw IntToRoman.java hosted with ❤ by GitHub

Populating Next Right Pointers in Each Node @LeetCode

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

	package leetcode.tree;
	import java.util.LinkedList;
	import java.util.Queue;
	/**
	* Solution: BFS. Only difference is connect nodes.
	* if (i == size - 1) --> node.next = null. if not , node.next = queue.peek();
	*
	* Don't use queue.isEmpty as if condition, at that time, queue is not empty. Next level nodes already stores in.
	*
	* @author jeffwan
	* @date Mar 11, 2014
	*/
	public class ConnectRightPointers {
	public void connect(TreeLinkNode root) {
	if (root == null) {
	return;
	}
	Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
	queue.offer(root);
	while (!queue.isEmpty()) {
	int size = queue.size();
	for (int i = 0; i < size; i++) {
	TreeLinkNode node = queue.poll();
	if (i == size - 1) {
	node.next = null;
	} else {
	node.next = queue.peek();
	}
	if (node.left != null) {
	queue.offer(node.left);
	}
	if (node.right != null) {
	queue.offer(node.right);
	}
	}
	}
	}
	class TreeLinkNode {
	TreeLinkNode left;
	TreeLinkNode right;
	TreeLinkNode next;
	}
	}

view raw ConnectRightPointers.java hosted with ❤ by GitHub

Same Tree @LeetCode

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

	package leetcode.tree;
	/**
	* Solution: Divide and Conquer. Compare root node, left and right subtree.
	* Almost same to isValidBST, isBalanced.
	*
	* Test Case: {},{0} --> p == null || q == null must not be placed at first which will influence result.
	*
	* @author jeffwan
	* @date Mar 11, 2014
	*/
	public class IsSameTree {
	public boolean isSameTree(TreeNode p, TreeNode q) {
	if (p == null && q != null) {
	return false;
	}
	if (p != null && q == null) {
	return false;
	}
	if (p == null || q == null) {
	return true;
	}
	if (p.val != q.val) {
	return false;
	}
	boolean left = isSameTree(p.left, q.left);
	boolean right = isSameTree(p.right, q.right);
	return left && right;
	}
	class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw IsSameTree.java hosted with ❤ by GitHub

Maximum Subarray @LeetCode

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

	package leetcode.array;
	/**
	* Solution:
	*
	* 1. Sliding Window
	* sum = Math.max(sum, 0) if negative number contributes to sum and sum < 0, throws it.
	* example:4, -1, 2. 4+1>0, don't abort, if -5 replace -1, abort, max = 4 will be recorded in previous step.
	*
	* 2. Prefix Sum
	* sum[i] records sum of (1...i)
	* minSum records the minimum sum of first i.
	* sum[i] - minSum --> largest sum range
	*
	* Extention: find maximum submatrix. --> Maximal Rectangle
	*
	* @author jeffwan
	* @date Mar 11, 2014
	*/
	public class MaxSubArray {
	// Sliding Window --> O(n)
	public int maxSubArray(int[] A) {
	if (A == null || A.length == 0) {
	return 0;
	}
	int max = Integer.MIN_VALUE, sum = 0;
	for (int i = 0; i < A.length; i++) {
	sum += A[i];
	max = Math.max(max, sum);
	sum = Math.max(sum, 0);
	}
	return max;
	}
	// Prefix Sum (sum array solution) --> O(n)
	public int maxSubArray2(int[] A) {
	if (A == null || A.length == 0) {
	return 0;
	}
	int max = Integer.MIN_VALUE, sum = 0, minSum = 0;
	for (int i = 0; i < A.length; i++) {
	sum += A[i];
	max = Math.max(max, sum - minSum);
	minSum = Math.min(minSum, sum);
	}
	return max;
	}
	// Brute Force Solution o(n*n) --> Time limited Exceeded
	public int maxSubArray3(int[] A) {
	int result = 0;
	for (int i = 0; i < A.length; i++) {
	int sum = 0;
	for (int j = i; j < A.length; j++) {
	sum += A[j];
	result = Math.max(result, sum);
	}
	}
	return result;
	}
	}

view raw MaxSubArray.java hosted with ❤ by GitHub

Swap Nodes in Pairs @LeetCode

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

	package leetcode.linkedlist;
	/**
	* Solution: Use dummy node to help swap nodes, not hard
	* I use head.next.next = head; at first, should use lastNode.next instead which make every swap sentence connected.
	* it's easy to remember and not messy.
	*
	* @author jeffwan
	* @date Mar 10, 2014
	*/
	public class SwapPairs {
	public ListNode swapPairs(ListNode head) {
	if (head == null || head.next == null) {
	return head;
	}
	ListNode dummy = new ListNode(0);
	dummy.next = head;
	ListNode lastNode = dummy;
	while (head != null && head.next != null) {
	// Swap pair
	ListNode temp = head.next.next;
	head.next.next = lastNode.next;
	lastNode.next = head.next;
	head.next = temp;
	// Move nodes
	lastNode = head;
	head = head.next;
	}
	return dummy.next;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) {
	this.val = x;
	}
	}
	}

view raw SwapPairs.java hosted with ❤ by GitHub

Merge Intervals @LeetCode

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

	package leetcode.array;
	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.Comparator;
	/**
	* Solution: sort intervals, compare lastInterval and interval[i].
	* Only two situation. 1. left, add(last). 2.interact, merge as last, i++, compare again
	* Need to sort first, take care, write comparator! Original intervals are messy.
	*
	* @author jeffwan
	* @date Mar 10, 2014
	*/
	public class MergeInterval {
	public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
	if (intervals == null || intervals.size() == 0) {
	return intervals;
	}
	Collections.sort(intervals, new IntervalComparator());
	ArrayList<Interval> result = new ArrayList<Interval>();
	Interval lastInterval = intervals.get(0);
	for (int i = 1; i < intervals.size(); i++) {
	Interval current = intervals.get(i);
	if(lastInterval.end < current.start) {
	result.add(lastInterval);
	lastInterval = current;
	} else {
	lastInterval.end = Math.max(lastInterval.end, current.end);
	}
	}
	result.add(lastInterval);
	return result;
	}
	public class IntervalComparator implements Comparator<Interval> {
	@Override
	public int compare(Interval a, Interval b) {
	return a.start - b.start;
	}
	}
	public static class Interval {
	int start;
	int end;
	Interval() { start = 0; end = 0; }
	Interval(int s, int e) { start = s; end = e; }
	}
	}

view raw MergeInterval.java hosted with ❤ by GitHub

Insert Interval @LeetCode

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

	package leetcode.array;
	import java.util.ArrayList;
	/**
	* Solution: Simple Math. Use new ArrayList is much more simple than operation on original one.
	* two interval's relation: left, right, intersect(merge a new one as newInterval, go to next round);
	* Only newInterval is right to the current one, insertPosition ++. Don't forget deal with the sequence.
	*
	* @author jeffwan
	* @date Mar 10, 2014
	*/
	public class InsertInterval {
	public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
	if (intervals == null || newInterval == null) {
	return null;
	}
	ArrayList<Interval> result = new ArrayList<Interval>();
	int insertPosition = 0;
	for (Interval interval : intervals) {
	if (interval.end < newInterval.start) {
	result.add(interval);
	insertPosition ++;
	} else if (interval.start > newInterval.end) {
	result.add(interval);
	} else {
	newInterval.start = Math.min(interval.start, newInterval.start);
	newInterval.end = Math.max(interval.end, newInterval.end);
	}
	}
	result.add(insertPosition,newInterval);
	return result;
	}
	public static class Interval {
	int start;
	int end;
	Interval() { start = 0; end = 0; }
	Interval(int s, int e) { start = s; end = e; }
	}
	}

view raw InsertInterval.java hosted with ❤ by GitHub

Divide Two Integers @LeetCode

Divide two integers without using multiplication, division and mod operator.

	package leetcode.binarySearch;
	/**
	* Solution: Bit Operation. Can't use *,/,%, the rest are +, -, <<, >> (don't forget bit operation!)
	* << is same to temp += temp. No difference. This way is quicker than minus divisor itself repeatly.
	* 1. Use shift records bit operation times
	* 2. use long to prevent overflow.
	* Every loop, a - max * b
	*
	*
	* This problem, we need to take care of boundary carefully!
	* Test case: (-2147483648,1), (2147483647,1), (-1010369383,-2147483648) and so on.
	*
	* Reference:
	* http://www.cnblogs.com/lautsie/p/3229125.html
	* http://yucoding.blogspot.com/2013/01/leetcode-question-28-divide-two-integers.html
	* http://blog.csdn.net/fightforyourdream/article/details/16899675
	* @author jeffwan
	*
	*/
	public class Divide {
	// Refator April 9, 2014
	public int divide(int dividend, int divisor) {
	int result = 0;
	boolean negative = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
	long a = Math.abs((long)dividend);
	long b = Math.abs((long)divisor);
	while (a >= b) {
	int shift = 0;
	while ((b << shift) <= a) {
	shift++;
	}
	result += 1 << (shift - 1);
	a -= (b << (shift - 1));
	}
	return negative? -result: result;
	}
	public int divide1(int dividend, int divisor) {
	int result = 0;
	boolean positive = true;
	if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
	positive = false;
	}
	// use long to prevent over flow.
	long tempDividend = dividend;
	long tempDivisor = divisor;
	if (tempDividend < 0) {
	tempDividend = -tempDividend;
	}
	if (tempDivisor < 0) {
	tempDivisor = -tempDivisor;
	}
	while (tempDividend >= Math.abs(tempDivisor)) {
	int multi = 1;
	long temp = tempDivisor;
	while (tempDividend >= temp) {
	tempDividend -= temp;
	result += multi;
	temp += temp;
	multi += multi;
	}
	}
	if (positive) {
	return result;
	} else {
	return -result;
	}
	}
	}

view raw Divide.java hosted with ❤ by GitHub

Pow(x, n) @LeetCode

Implement pow(x, n).

	package leetcode.binarySearch;
	/**
	* Solution: BinarySearch
	*
	* Tricky:
	* 1. n could be negative.
	* 2. n cound be Integer.MIN_VALUE(-2147483648) and Integer.MAX_VALUE(2147483647)
	* 3. handle n == 0, 1 as terminating condition.
	*
	* @author jeffwan
	* @date Mar 10, 2014
	*/
	public class Pow {
	public double pow (double x, int n) {
	if (n == 0) {
	return 1;
	}
	if (n == 1) {
	return x;
	}
	if (n < 0) {
	// Value of pow(x, Integer.MIN_VALUE)? == pow(x, Integer.MAX_VALUE) * x
	if ( n == Integer.MIN_VALUE) {
	return 1 / (pow(x, Integer.MAX_VALUE) * x);
	} else {
	return 1 / pow(x, -n);
	}
	}
	// BinarySearch Thought
	double half = pow(x, n / 2);
	if (n % 2 == 1) {
	return half * half * x;
	} else {
	return half * half;
	}
	}
	// Brute Force
	public double pow2 (double x, int n) {
	double temp = x;
	for (int i = 1 ; i<= n; i++) {
	x *= temp ;
	}
	return x;
	}
	}

view raw Pow.java hosted with ❤ by GitHub

Single Number II @LeetCode

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

	package leetcode;
	import java.util.Arrays;
	/**
	* Solution: Bit Operation, convert a int(4 byte) to 32 bit(4 byte), calculate sum on every bit.
	* Except single number, every bit's sum % 3 == 0. We use this feature.
	*
	* To calculate if i bit has 1 or 0. --> (A[j] >> i) == ? 1 means exist, 0 means not.
	* To recover single number, left move i.
	*
	* Reference: http://www.mitbbs.com/article_t/JobHunting/32547143.html
	* @author jeffwan
	* @date Mar 10, 2014
	*/
	public class SingleNumber2 {
	public int singleNumber(int[] A) {
	int[] count = new int[32]; //auto initialized
	int result = 0;
	for (int i = 0; i < count.length; i++) {
	for (int j = 0; j < A.length; j++) {
	if (((A[j] >> i) & 1) == 1) {
	count[i] = (count[i] + 1) % 3;
	}
	}
	result |= count[i] << i;
	}
	return result;
	}
	// Same way as Single Number I
	public int singleNumber2(int[] A) {
	Arrays.sort(A);
	for (int i = 0;i < A.length - 1; i++) {
	if (A[i] == A[i + 1]) {
	i += 2; //step 3 if find treble.
	} else {
	return A[i];
	}
	}
	return A[A.length - 1];
	}
	// Extension: int -> byte[]
	public static byte[] toLH(int n) {
	byte[] b = new byte[4];
	b[0] = (byte) (n & 0xff);
	b[1] = (byte) (n >> 8 & 0xff);
	b[2] = (byte) (n >> 16 & 0xff);
	b[3] = (byte) (n >> 24 & 0xff);
	return b;
	}
	}

view raw SingleNumber.java hosted with ❤ by GitHub

SingleNumber @LeetCode

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

	package leetcode;
	import java.util.Arrays;
	import java.util.HashSet;
	/**
	* Solution: Bit Operation
	*
	* Sort --> do not meet complexity. Compare same, if so, skip 2 index (based on all pairs feature). --> not O(n)
	* HashSet --> do not meet memory.
	*
	* @author jeffwan
	* @date Mar 10, 2014
	*/
	public class SingleNumber {
	// O(NlogN) + O(N) not O(N)
	// Sort numbers form pair.it's easy to find single one. single may be last one. return A[A.length - 1]
	public int singleNumber(int[] A) {
	Arrays.sort(A);
	for (int i = 0; i < A.length - 1; i++) {
	if (A[i] == A[i + 1]) {
	i += 1; // all three pair, if A[i] = A[i+1], then A[i] = A[i+2];
	} else {
	return A[i];
	}
	}
	return A[A.length - 1];
	}
	// Bit Operation (a ^ a = 0, 0 ^ a = a)
	public int singleNumber2(int[] A) {
	int result = 0;
	for (int i = 0; i < A.length; i++) {
	result = result ^ A[i];
	}
	return result;
	}
	// Extra Space used. -- don't use hashMap to calc count and iterative again.
	public int singleNumber3(int[] A) {
	HashSet<Integer> hashSet = new HashSet<Integer>();
	for (int i = 0; i < A.length; i++) {
	if (hashSet.contains(A[i])) {
	hashSet.remove(A[i]);
	} else {
	hashSet.add(A[i]);
	}
	}
	return hashSet.iterator().next();
	}
	}

view raw SingleNumber.java hosted with ❤ by GitHub

Search a 2D Matrix @LeetCode

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

	package leetcode.binarySearch;
	/**
	* Solution: BinarySearch. it will be a sorted array if matrix expand line by line.
	* The problem is to handle the position and element value in matrix.
	* Only first and last element could be reached in last two situation.
	* element = matrix[0][0]; element = matrix[matrix.length - 1][matrix[0].length - 1]; also works but not beautiful.
	*
	* @author jeffwan
	* @date Mar 9, 2014
	*/
	public class SearchMatrix {
	public boolean searchMatrix(int[][] matrix, int target) {
	if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
	return false;
	}
	int start, end, mid, m, n, element;
	m = matrix.length;
	n = matrix[0].length;
	start = 0;
	end = m * n - 1;
	while (start + 1 < end) {
	mid = start + (end - start) / 2;
	element = matrix[mid / n][ mid % n];
	if (target == element) {
	return true;
	} else if (target < element) {
	end = mid;
	} else {
	start = mid;
	}
	}
	element = matrix[start / n][ start % n];
	if (target == element) {
	return true;
	}
	element = matrix[end / n][ end % n];
	if (target == element) {
	return true;
	}
	return false;
	}
	// Solution2: BinarySearch line first, and then search column. Use two time BinarySearch -- low efficiency.
	public boolean searchMatrix2(int[][]A, int target) {
	if(A == null || A.length == 0) {
	return false;
	}
	int start, end, mid;
	int flag;
	// 1. search target number line
	start = 0;
	end = A.length - 1;
	while (start + 1 < end) {
	mid = start + (end - start) / 2;
	if (target == A[mid][0]) {
	return true;
	} else if (target < A[mid][0]) {
	end = mid;
	} else {
	start = mid;
	}
	}
	if (target == A[start][0]) {
	return true;
	} else if (target == A[end][0]) {
	return true;
	} else if (target > A[start][0] && target < A[end][0]){
	flag = start;
	} else {
	flag = end;
	}
	// 2. search target number column
	start = 0;
	end = A[flag].length - 1;
	while (start + 1 < end) {
	mid = start + (end - start) / 2;
	if (target == A[flag][mid]) {
	return true;
	} else if (target < A[flag][mid]) {
	end = mid;
	} else {
	start = mid;
	}
	}
	if (target == A[flag][end]) {
	return true;
	}
	return false;
	}
	}

view raw SearchMatrix.java hosted with ❤ by GitHub

Search in Rotated Sorted Array II @LeetCode

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

	package leetcode.binarySearch;
	/**
	* Solution: Binary Search, consider A[start] == A[mid] based on Search a Rotated Array I
	*
	* The most important problem we need to consider the situation A[mid] = A[start] which we didn't consider in
	* search rotated sorted array I. We can't simply user A[start] <= A[mid], Actually we can't make judgment.
	* A[start] = A[mid] can't make sure, so start++. because A[start] == A[mid], it will not skip the target, just
	* skip the useless number
	*
	* @author jeffwan
	* @date Mar 9, 2014
	*/
	public class SearchRotatedArray2 {
	public boolean search(int[] A, int target) {
	if (A == null || A.length == 0) {
	return false;
	}
	int start, end, mid;
	start = 0;
	end = A.length - 1;
	while (start + 1 < end) {
	mid = start + (end - start) / 2;
	if (target == A[mid]) {
	return true;
	}
	if (A[start] < A[mid]) {
	if (target >= A[start] && target <= A[mid]) {
	end = mid;
	} else {
	start = mid;
	}
	} else if (A[start] > A[mid]){
	if (target >= A[mid] && target <= A[end]) {
	start = mid;
	} else {
	end = mid;
	}
	} else {
	start ++;
	}
	} //end while
	if (target == A[start]) {
	return true;
	}
	if (target == A[end]) {
	return true;
	}
	return false;
	}
	}

view raw SearchRotatedArray2.java hosted with ❤ by GitHub

Search in Rotated Sorted Array @LeetCode

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

	package leetcode.binarySearch;
	/**
	* Solution: BinarySearch, split Array to two part;
	* A[start] < A[mid] --> (start,end) are sorted;
	* A[start] > A[mid] --> (mid,end) are sorted.
	* target >= A[start] && target <= A[end] makes sure we moves range to a sorted range step by step.
	* That means, if not in this range, move to rest part, iteratively. if yes, like general binarySearch.
	*
	* @author jeffwan
	* @date Mar 9, 2014
	*/
	public class SearchRotatedArray {
	public int search(int[] A, int target) {
	if (A == null || A.length == 0) {
	return -1;
	}
	int start, end, mid;
	start = 0;
	end = A.length - 1;
	while (start + 1 < end) {
	mid = start + (end - start) / 2;
	if (target == A[mid]) {
	return mid;
	}
	if (A[start] < A[mid]) {
	if (target >= A[start] && target < A[mid]) {
	end = mid;
	} else {
	start = mid;
	}
	} else {
	if (target > A[mid] && target <= A[end]) {
	start = mid;
	} else {
	end = mid;
	}
	}
	}
	if (target == A[start]) {
	return start;
	}
	if (target == A[end]) {
	return end;
	}
	return -1;
	}
	}

view raw SearchRotatedArray.java hosted with ❤ by GitHub

Search Insert Position @LeetCode

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

	package leetcode.binarySearch;
	/**
	* Solution: BinarySearch, complexity is to handle different result if target could not be found.
	* target < A[0] --> 0(start)
	* target > A[start] && target < A[end] --> start + 1 or end
	* target > A[end] -- end + 1
	* target = A[start] --> start
	* target = A[end] --> end
	* We could combine these situations to following codes.
	*
	* @author jeffwan
	* @date Mar 9, 2014
	*/
	public class SearchInsert {
	public int searchInsert2(int[] A, int target) {
	if (A == null || A.length == 0) {
	return -1;
	}
	int start, end, mid;
	start = 0;
	end = A.length - 1;
	while (start + 1 < end) {
	mid = start + (end - start) / 2;
	if (target == A[mid]) {
	return mid;
	} else if (target < A[mid]) {
	end = mid;
	} else {
	start = mid;
	}
	}
	// if contains return ---> don't need to use if-else
	if (target <= A[start]) {
	return start;
	}
	if (target > A[end]) {
	return end + 1;
	}
	return end;
	}
	}

view raw SearchInsert.java hosted with ❤ by GitHub

Search for a Range @LeetCode

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

	package leetcode.binarySearch;
	/**
	* Solution: BinarySearch, two time. 2 O(logn) --> O(logn)
	* Search left bound first and then search right bound second time.
	* left: end = mid. right: start = mid. keeps we don't abandon result.
	*
	* Take care: sequence --> target == A[start] or A[end]. left bound should check start first, right check end.
	*
	* @author jeffwan
	* @date Mar 9, 2014
	*/
	public class SearchRange {
	public int[] searchRange(int[] A, int target) {
	int[] bound = new int[2];
	int start, end, mid;
	if (A == null || A.length == 0) {
	bound[0] = bound[1] = -1;
	return bound;
	}
	// search the left bound, end = mid;
	start = 0;
	end = A.length - 1;
	while(start + 1 < end) {
	mid = start + (end - start) / 2;
	if (target == A[mid]) {
	end = mid;
	} else if (target < A[mid]) {
	end = mid;
	} else {
	start = mid;
	}
	}
	if (target == A[start]) {
	bound[0] = start;
	} else if ( target == A[end]) {
	bound[0] = end;
	} else {
	bound[0] = bound[1] = -1;
	return bound;
	}
	// search the right bound, start = mid;
	start = 0;
	end = A.length - 1;
	while (start + 1 < end) {
	mid = start + (end - start) /2 ;
	if (target == A[mid]) {
	start = mid;
	} else if (target < A[mid]) {
	end = mid;
	} else {
	start = mid;
	}
	}
	// sequence is very important here! test case [2,2] 2 -- if start go first, result will be [0,0]
	if (target == A[end]) {
	bound[1] = end;
	} else if ( target == A[start]) {
	bound[1] = start;
	}
	return bound;
	}
	}

view raw SearchRange.java hosted with ❤ by GitHub

Longest Substring Without Repeating Characters @LeetCode

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

	package leetcode.array;
	import java.util.HashSet;
	/**
	* Solution: Sliding Window
	* Use hashset to check duplicates
	* [a,b,c] a --> a,[b,c,a] as s[leftBound] == s[i], don't need to remove from hashSet.
	* [a,b,c] b --> a,[b,c] b --> a,b,[c,b] shift until s[leftBound] == s[i]
	* Record the max value of window using max = Math.max(max, i-leftBound+1);
	*
	* Refactor: leftBound < i (useless) if hashSet.contains(s[i]), worst case: s[leftBound] = s[i] --> leftBound = i-1 < i
	*
	* @author jeffwan
	* @date Mar 8, 2014
	*/
	public class LengthOfLongestSubstring {
	public int lengthOfLongestSubstring(String s) {
	if (s == null || s.length() == 0) {
	return 0;
	}
	HashSet<Character> hashSet = new HashSet<Character>();
	int leftBound = 0, max = 0;
	for (int i = 0; i < s.length(); i++) {
	if (hashSet.contains(s.charAt(i))) {
	while (leftBound < i && s.charAt(leftBound) != s.charAt(i)) {
	hashSet.remove(s.charAt(leftBound));
	leftBound++;
	}
	leftBound++;
	} else {
	hashSet.add(s.charAt(i));
	max = Math.max(max, i - leftBound + 1);
	}
	}
	return max;
	}
	}

view raw LengthOfLongestSubstring.java hosted with ❤ by GitHub

Merge Sorted Array @LeetCode

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

	package leetcode.array;
	/**
	* Solution: Merge from tail to head. We can't start from head because of overlap.
	* We don't need to check if m >= 0, because we merge B to A, A's element already there.
	*
	* @author jeffwan
	* @date Mar 8, 2014
	*/
	public class MergeSortedArray {
	// Refactor of first version(mostly on index)
	public void merge(int A[], int m, int B[], int n) {
	int index = m + n;
	while (m > 0 && n > 0) {
	if (A[m - 1] > B[n - 1]) {
	A[--index] = A[--m];
	} else {
	A[--index] = B[--n];
	}
	}
	while (n > 0) {
	A[--index] = B[--n];
	}
	}
	// First Version
	public static void merge2(int A[], int m, int B[], int n) {
	int i = m - 1, j = n - 1;
	while (i >= 0 && j >= 0) {
	int index = i + j + 1;
	if (A[i] >= B[j]) {
	A[index] = A[i];
	i--;
	} else {
	A[index] = B[j];
	j--;
	}
	}
	if (j >= 0) {
	while (j >= 0) {
	A[j] = B[j];
	j--;
	}
	}
	}
	}

view raw MergeSortedArray.java hosted with ❤ by GitHub

Remove Element @LeetCode

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

	package leetcode.array;
	/**
	* Solution: Two Pointer (Same to Remove Duplicates from Sorted Array I,II and easier)
	* @author jeffwan
	* @date Mar 8, 2014
	*/
	public class RemoveElement {
	public int removeElement(int[] A, int elem) {
	if (A == null || A.length == 0) {
	return 0;
	}
	int size = 0;
	for (int i = 0; i < A.length; i++) {
	if (A[i] != elem) {
	A[size++] = A[i];
	}
	}
	return size;
	}
	}

view raw RemoveElement.java hosted with ❤ by GitHub

Remove Duplicates from Sorted Array II @LeetCode

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

	package leetcode.array;
	/**
	* Solution: Two Pointer. Almost same to Remove Duplicates from Sorted Array (need to make a little change like following)
	* 这个题目时间一长就老写错，以后统一了都从 1开始，这样不会关于0处犯迷糊
	* size > 0 && A[size - 1] == A[size] 判断是否已经有2个相同的了
	*
	* @author jeffwan
	* @date Mar 8, 2014
	*/
	public class RemoveDuplicates2 {
	public int removeDuplicates(int[] A) {
	if (A == null || A.length == 0) {
	return 0;
	}
	int size = 0;
	for (int i = 1; i < A.length; i++) {
	if (A[i] == A[size] && size > 0 && A[size - 1] == A[size]) {
	continue;
	}
	A[++size] = A[i];
	}
	return size + 1;
	}
	// Problem: Remove Duplicates from Sorted Array (I not II)
	// We change to this style to make it same to II. Usually we use if (A[i] != A[size]) directly.
	public int removeDuplicates1(int[] A) {
	if (A == null || A.length == 0) {
	return 0;
	}
	int size = 0;
	for (int i = 0; i < A.length; i++) {
	if (A[i] == A[size]) {
	continue;
	}
	A[++size] = A[i];
	}
	return size + 1;
	}
	// 只要有duplicates, 全删 算是Remove Duplicates from Sorted Array III， 跟remove duplicate list II 差不多
	public int removeDuplicates3(int[] A) {
	if (A == null || A.length == 0) {
	return 0;
	}
	int size = 0;
	for (int i = 1; i < A.length; i++) {
	if (i + 1 < A.length && A[i] == A[i + 1]) {
	//skip all duplicates nodes
	int temp = A[i];
	while ( i < A.length && A[i] == temp) {
	i++;
	}
	i--;
	} else {
	A[++size] = A[i];
	}
	}
	return size + 1;
	}
	}

view raw RemoveDuplicates2.java hosted with ❤ by GitHub

Remove Duplicates from Sorted Array @LeetCode

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

	package leetcode.array;
	/**
	* Solution: Two Pointer. one -- size store non-duplicate number, the other -- i traversal array to find non-duplicates.
	* This is not same as Sorted List, Here we find non-duplicate number and move to front.(List, we find duplicate and remove)
	* Remove is comlicated in Array, so we must change our mind.
	*
	* In addtion, A length will not change because length of array can't be changed, the problem description just means return new length,
	* So it seems like we got the new Array and abandon the rest.
	*
	* @author jeffwan
	* @date Mar 8, 2014
	*/
	public class RemoveDuplicates {
	public int removeDuplicates(int[] A) {
	if (A == null || A.length == 0) {
	return 0;
	}
	int size = 0;
	for(int i = 0; i < A.length; i++) {
	if (A[i] != A[size]) {
	A[++size] = A[i];
	}
	}
	return size + 1;
	}
	//
	/*
	In order to make it same as Remove Duplicates II. We could code as follow.
	for(int i = 0; i < A.length; i++) {
	if (A[i] == A[size]) {
	continue;
	}
	A[++size] = A[i];
	}
	Remove Duplicate II only need to add size != 0 && size[i] == size[i-1];
	*/
	}

view raw RemoveDuplicates.java hosted with ❤ by GitHub

Insertion Sort List @LeetCode

Sort a linked list using insertion sort.

	package leetcode.linkedlist;
	/**
	* Solution: just insert sort algorithm -- a little difference with int[] because we can easily insert node in LinkedList.
	* head points to the insert node.
	* Every time, we need target scan from dummy to find out the right position(target.next);
	*
	* Reference: http://zhdkn.iteye.com/blog/1136253
	*
	* @author jeffwan
	* @date Mar 6, 2014
	*/
	public class InsertionSortList {
	public ListNode insertionSortList(ListNode head) {
	if (head == null) {
	return null;
	}
	ListNode dummy = new ListNode(0);
	while (head != null) {
	ListNode target = dummy;
	while (target.next != null && target.next.val < head.val) {
	target = target.next;
	}
	ListNode temp = head.next;
	head.next = target.next;
	target.next = head;
	head = temp;
	}
	return dummy.next;
	}
	// Algorithm
	public void insertSort(int[] a) {
	for (int i = 1; i < a.length; i++) {
	int key = a[i];
	int j = i - 1;
	while (j >= 0 && a[j] > key) {
	a[j + 1] = a[j];
	j --;
	}
	a[j + 1] = key;
	}
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) {
	this.val = x;
	}
	}
	}

view raw InsertionSortList.java hosted with ❤ by GitHub

Merge k Sorted Lists @LeetCode

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

	package leetcode.linkedlist;
	import java.util.ArrayList;
	import java.util.Comparator;
	import java.util.PriorityQueue;
	/**
	* Solution: Use PriorityQueue to get the smallest node.
	* If we'd like to poll the biggest, change compare function logic;
	*
	* if heap can't be used, we need to sort all header, get smallest, remove, insert sort head.next and ..
	* if one list goes to end, remove from lists, untils lists.size() == 0
	*
	* Test case: [{}] , could be null, heap.add need to check.
	* @author jeffwan
	* @date Mar 7, 2014
	*/
	public class MergeKLists {
	public ListNode mergeKLists(ArrayList<ListNode> lists) {
	if (lists == null || lists.size() == 0) {
	return null;
	}
	PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), ListNodeComparator);
	for (int i = 0; i < lists.size(); i++) {
	if (lists.get(i) != null) {
	heap.add(lists.get(i));
	}
	}
	ListNode dummy = new ListNode(0);
	ListNode tail = dummy;
	while(!heap.isEmpty()) {
	ListNode head = heap.poll();
	tail.next = head;
	tail = tail.next;
	if (head.next != null) {
	heap.add(head.next);
	}
	}
	return dummy.next;
	}
	private Comparator<ListNode> ListNodeComparator = new Comparator<ListNode>() {
	@Override
	public int compare(ListNode left, ListNode right) {
	return left.val - right.val;
	}
	};
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) {
	this.val = x;
	}
	}
	}

view raw MergeKLists.java hosted with ❤ by GitHub

Rotate List @LeetCode

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

	package leetcode.linkedlist;
	/**
	* Solution: Two pointer(same to remove Nth from end, go n, then length - n)
	* rotate the list to the right by k places --> k starts from right, but not left!
	*
	* Test Case: n may be larger than length
	*
	* @author jeffwan
	* @date Mar 7, 2014
	*/
	public class RotateRight {
	public ListNode rotateRight(ListNode head, int n) {
	if (head == null || n == 0) {
	return head;
	}
	n = n % getLength(head);
	ListNode dummy = new ListNode(0);
	dummy.next = head;
	head = dummy;
	ListNode tail = dummy;
	for (int i = 0; i < n; i++) {
	head = head.next;
	}
	// head points to old end, tails points to new end.
	while (head.next != null) {
	head = head.next;
	tail = tail.next;
	}
	// merge list
	head.next = dummy.next;
	dummy.next = tail.next;
	tail.next = null;
	return dummy.next;
	}
	public int getLength(ListNode head) {
	int length = 0;
	while (head != null) {
	head = head.next;
	length++;
	}
	return length;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) { this.val = x; }
	}
	}

view raw RotateRight.java hosted with ❤ by GitHub

Reverse Linked List II @LeetCode

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

	package leetcode.linkedlist;
	/**
	* Solution: traversal to m, reverse m to n, concat the last n nodes.
	* Use dummy because of many add functions.
	* Here, reverse List from mNode.next(usually we begin from head). It doesn't matter.
	* In addition, we must mark mNode(rear of reverse list) because we must finish in one-pass.
	*
	* @author jeffwan
	* @date Mar 7, 2014
	*/
	public class ReverseBetween {
	public ListNode reverseBetween(ListNode head, int m, int n) {
	if ( head == null || m >= n) {
	return head;
	}
	ListNode dummy = new ListNode(0);
	dummy.next = head;
	head = dummy;
	// 1. First 0 - m-1 Part
	for (int i = 1; i < m; i++) {
	if ( head== null) {
	return null;
	}
	head = head.next;
	}
	// 2. Second m - n Part
	ListNode premNode = head;
	ListNode mNode = head.next;
	ListNode nNode = mNode, postnNode = mNode.next;
	for (int i = m; i < n; i++) {
	if (postnNode == null) {
	return null;
	}
	ListNode temp = postnNode.next;
	postnNode.next = nNode;
	nNode = postnNode;
	postnNode = temp;
	}
	// 3. Third Part last n.
	mNode.next = postnNode;
	premNode.next = nNode;
	return dummy.next;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) { this.val = x; }
	}
	}

view raw ReverseBetween.java hosted with ❤ by GitHub

Reorder List @LeetCode

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

	package leetcode.linkedlist;
	/**
	* Solution: split list into two part from middle. reverse second part, and then merge. (Almost same to SortList)
	* So this problem could be divided into findMiddle, reverse List and merge two list.
	* Left: l0, l1, l2...
	* Right: ln, ln-1, ln-2...
	* Merge: l0, ln, l1, ln-1....
	*
	* @author jeffwan
	* @date Mar 7, 2014
	*/
	public class ReorderList {
	public void reorderList(ListNode head) {
	if (head == null || head.next == null) {
	return;
	}
	ListNode mid = findMiddle(head);
	ListNode right = reverse(mid.next);
	mid.next = null;
	ListNode left = head;
	merge(left, right);
	}
	private void merge(ListNode l1, ListNode l2) {
	ListNode dummy = new ListNode(0);
	int index = 0;
	while (l1 != null && l2 != null) {
	if (index % 2 == 0) {
	dummy.next = l1;
	l1 = l1.next;
	} else {
	dummy.next = l2;
	l2 = l2.next;
	}
	dummy = dummy.next;
	index++;
	}
	if (l1 != null) {
	dummy.next = l1;
	}
	if (l2 != null) {
	dummy.next = l2;
	}
	}
	public ListNode reverse(ListNode head) {
	ListNode newHead = null;
	while (head != null) {
	ListNode temp = head.next;
	head.next = newHead;
	newHead = head;
	head = temp;
	}
	return newHead;
	}
	public ListNode findMiddle(ListNode head) {
	ListNode slow = head, fast = head.next;
	while (fast != null && fast.next != null) {
	fast = fast.next.next;
	slow = slow.next;
	}
	return slow;
	}
	// My Merge solution -- Time limit Exceeded. But I think it works...
	private void merge2(ListNode l1, ListNode l2) {
	ListNode dummy = new ListNode(0);
	ListNode head = dummy;
	while (l1 != null && l2 != null) {
	head.next = l1;
	head.next.next = l2;
	head = head.next.next;
	l1 = l1.next;
	l2 = l2.next;
	}
	if (l1 != null) {
	head.next = l1;
	}
	if (l2 != null) {
	head.next = l2;
	}
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) {
	this.val = x;
	}
	}
	}

view raw ReorderList.java hosted with ❤ by GitHub

Sort List @LeetCode

Sort a linked list in O(n log n) time using constant space complexity.

	package leetcode.linkedlist;
	/**
	* Solution: Use Merge Sort to achieve O(n*logn), Recursive
	* Split this problem into findMiddle, Merge two sortedList functions.
	*
	* @author jeffwan
	* @date Mar 7, 2014
	*/
	public class SortList {
	public ListNode sortList(ListNode head) {
	if (head == null || head.next == null) {
	return head;
	}
	ListNode mid = findMiddle(head);
	ListNode right = sortList(mid.next);
	mid.next = null;
	ListNode left = sortList(head);
	return merge(left, right);
	}
	public ListNode findMiddle(ListNode head) {
	ListNode slow = head, fast = head.next;
	while (fast != null && fast.next != null) {
	fast = fast.next.next;
	slow = slow.next;
	}
	return slow;
	}
	public ListNode merge(ListNode l1, ListNode l2) {
	ListNode dummy = new ListNode(0);
	ListNode head = dummy;
	while (l1 != null && l2 != null) {
	if (l1.val <= l2.val) {
	head.next = l1;
	l1 = l1.next;
	} else {
	head.next = l2;
	l2 = l2.next;
	}
	head = head.next;
	}
	if (l1 != null) {
	head.next = l1;
	}
	if (l2 != null) {
	head.next = l2;
	}
	return dummy.next;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) {
	this.val = x;
	}
	}
	}

view raw SortList.java hosted with ❤ by GitHub

Remove Nth Node From End of List @LeetCode

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

	package leetcode.linkedlist;
	/**
	* Solution: Iterative + two pointer --> one pass, use Math here.
	* p2 move n, so last length will be length - n, p1 p2 move together,
	* when p2 hit end, p1 move length - n where right node's location.
	*
	* Use dummy to easy handle deleting first node case.
	*
	* @author jeffwan
	* @date Mar 6, 2014
	*/
	public class RemoveNthFromEnd {
	public ListNode removeNthFromEnd(ListNode head, int n) {
	ListNode dummy = new ListNode(0);
	dummy.next = head;
	ListNode p1 = dummy;
	ListNode p2 = dummy;
	for (int i = 0; i < n; i++) {
	p2 = p2.next;
	}
	while (p2.next != null) {
	p2 = p2.next;
	p1 = p1.next;
	}
	p1.next = p1.next.next;
	return dummy.next;
	}
	// Solution2: One pointer + two pass(one for getLength, one for delete target Node).
	public ListNode removeNthFromEnd2(ListNode head, int n) {
	if (head == null) {
	return null;
	}
	// Get List Length
	int length = 0;
	ListNode runner = head;
	while (runner != null) {
	length++;
	runner = runner.next;
	}
	// Delete target node, the reason using dummy is n maybe equals to list.length
	int target = length - n;
	ListNode dummy = new ListNode(0);
	dummy.next = head;
	runner = dummy;
	for (int i = 0; i < target ; i++){
	runner = runner.next;
	}
	runner.next = runner.next.next;
	return dummy.next;
	}
	class ListNode {
	int val;
	ListNode next;
	ListNode (int x) {
	this.val = x;
	}
	}
	}

view raw RemoveNthFromEnd.java hosted with ❤ by GitHub

Valid Palindrome @LeetCode

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

	package leetcode;
	/**
	* Solution: Two pointer, need to exclude non-alphanumeric(digit, char)
	* Test Case: "" -> true
	*
	* @author jeffwan
	* @date Mar 6, 2014
	*/
	public class IsPalindrome {
	public static void main(String[] args) {
	String str = "";
	System.out.println(isPalindrome(str));
	}
	public static boolean isPalindrome(String s) {
	if (s == null) {
	return false;
	}
	int start = 0;
	int end = s.length() - 1;
	while (start < end) {
	char head = Character.toLowerCase(s.charAt(start));
	char rear = Character.toLowerCase(s.charAt(end));
	if (!Character.isLetterOrDigit(head)) {
	start++;
	continue;
	}
	if (!Character.isLetterOrDigit(rear)) {
	end--;
	continue;
	}
	if (head == rear) {
	start++;
	end--;
	} else {
	return false;
	}
	}
	return true;
	}
	}

view raw IsPalindrome.java hosted with ❤ by GitHub

Validate Binary Search Tree @LeetCode

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

	package leetcode.tree;
	/**
	* Solution: DFS Traversal
	* Middle -- lastNode.al >= root.val --> false
	* Like this kind of question, we need to use a lastNode outside of function to record lastNode value for compare.
	* (Recover BST & Flatten BT to linkedList)
	*
	* Take Care: Standard BST won't allow duplicates, but this problem contains a test case {1,1}, so we need to use >=
	*
	* @author jeffwan
	* @date Mar 6, 2014
	*/
	public class IsValidBST {
	TreeNode lastNode = new TreeNode(Integer.MIN_VALUE);
	public boolean isValidBST(TreeNode root) {
	if (root == null) {
	return true;
	}
	if (!isValidBST(root.left)) {
	return false;
	}
	if (lastNode.val > root.val) {
	return false;
	}
	lastNode = root;
	if (!isValidBST(root.right)) {
	return false;
	}
	return true;
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw IsValidBST.java hosted with ❤ by GitHub

RestoreIpAddresses @LeetCode

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

	package leetcode.combinations;
	import java.util.ArrayList;
	import java.util.List;
	/**
	* Solution: This is almost same to Palindrome Partition. The difference is we judge Ip instead of Palinedrome here.
	* User Long.parseLong() but not Integer because of 12 digits
	*
	* Termination: list size == 4 and string goed to end
	* IP: 0< ip unit< 255, remember deal with 010 situation.
	*
	* Use a util converIP but not StringBuilder here. Easy for me to deal with String "."
	*
	* @author jeffwan
	* @date Mar 5, 2014
	*/
	public class RestoreIpAddresses {
	public static void main(String[] args) {
	String str = "010010";
	// String str = "11111111111111111111";
	System.out.println(restoreIpAddresses(str));
	}
	public static ArrayList<String> restoreIpAddresses(String s) {
	ArrayList<String> result = new ArrayList<String>();
	if (s.length() > 12) {
	return result;
	}
	ArrayList<String> list = new ArrayList<String>();
	helper(result, list, s, 0);
	return result;
	}
	public static void helper(ArrayList<String> result, ArrayList<String> list, String s,
	int position) {
	// use position == s.length() to replace s.substring(position).length() == 0
	if(list.size() == 4 && position == s.length()) {
	result.add(convertIP(list));
	return;
	}
	for (int i = position; i < s.length(); i++) {
	String prefix = s.substring(position, i + 1);
	if (Long.parseLong(prefix) < 0 || Long.parseLong(prefix) > 255
	|| (prefix.startsWith("0") && prefix.length() != 1)) {
	continue;
	}
	list.add(prefix);
	helper(result, list, s, i + 1);
	list.remove(list.size() - 1);
	}
	}
	public static String convertIP(ArrayList<String> list) {
	StringBuilder sb = new StringBuilder();
	for (String ip : list) {
	sb.append(ip+".");
	}
	return sb.deleteCharAt(sb.length() - 1).toString();
	}
	}

view raw RestoreIpAddresses.java hosted with ❤ by GitHub

Palindrome Partitioning @LeetCode

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
    ["aa","b"],
    ["a","a","b"]
]

	package leetcode.combinations;
	import java.util.ArrayList;
	/**
	* Solution:
	* We use s.substring(position, i + 1) to get prefex. then recursive s!
	* At first, every partition will be one char. After that, i++, interval will be 2, 3, 4 ...
	* First time use position as termination condition.
	*
	* Difficulty: How to partition a string?
	* I confused about the possibilities partitioning has and the termination condition.
	* a b a, ab a What I think is starting from head after interval increase, but it's not easy as follows.
	*
	* Take care:
	* helper terminate condition
	* 1. All Palindrome -- ends with return;
	* 2. None Palindrome -- ends with i < s.length()
	*
	* These are not solution but all Partition. it shows how to partition a string.
	* [a, a, b, b, a, a], [a, a, b, b, aa], [a, a, b, ba, a], [a, a, b, baa], [a, a, bb, a, a], [a, a, bb, aa],......
	*
	* @author jeffwan
	* @date Mar 4, 2014
	*/
	public class PalindromePartition {
	public static void main(String[] args) {
	String str = "aabbaa";
	System.out.println(partition(str));
	}
	public static ArrayList<ArrayList<String>> partition(String s) {
	ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
	if (s == null || s.length() == 0) {
	return result;
	}
	ArrayList<String> list = new ArrayList<String>();
	helper(result, list, s, 0);
	return result;
	}
	public static void helper(ArrayList<ArrayList<String>> result,
	ArrayList<String> list, String s, int position) {
	if (position == s.length()) {
	result.add(new ArrayList<String>(list));
	return;
	}
	for (int i = position; i < s.length(); i++) {
	String prefix = s.substring(position, i + 1);
	if (!isPalindrome(prefix)) {
	continue;
	}
	list.add(prefix);
	helper(result, list, s, i + 1);
	list.remove(list.size() - 1);
	}
	}
	// Judge if string is palindrome
	public static boolean isPalindrome(String str) {
	int start = 0;
	int end = str.length() - 1;
	while (start < end) {
	if (str.charAt(start) != str.charAt(end)){
	return false;
	}
	start++;
	end--;
	}
	return true;
	}
	}

view raw PalindromePartition.java hosted with ❤ by GitHub

TwoSum @LeetCode

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

	package leetcode;
	import java.util.Arrays;
	import java.util.HashMap;
	import javax.swing.text.html.parser.TagElement;
	import javax.xml.transform.Templates;
	/**
	*
	* Solution:
	* 1. useHashMap to store target O(n)
	* 2. two pointers, also need extra space to store sorted array O(n*log(n)
	* 3. brute force O(n*n) will not AC.
	*
	* @author jeffwan
	* @date Mar 2, 2014
	*/
	public class TwoSum {
	// HashMap get set O(1) --> O(n)
	public int[] twoSum(int[] numbers, int target) {
	int result[] = new int[2];
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	for (int i = 0; i < numbers.length ; i++) {
	if (map.containsKey(numbers[i])) {
	int index = map.get(numbers[i]);
	result[0] = index + 1;
	result[1] = i + 1;
	break;
	} else {
	map.put(target - numbers[i], i);
	}
	}
	return result;
	}
	// O(n*log(n)) sort O(n*log(n)), two loop O(n) O(n*log(n)) + 2*O(n) = O(n*log(n))
	public int[] twoSum1(int[] numbers, int target) {
	//int[] sortedNumbers = numbers;
	//Arrays.sort(sortedNumbers); -- will lead numbers sorted
	int[] sortedNumbers = new int[numbers.length];
	System.arraycopy(numbers, 0, sortedNumbers, 0, numbers.length);
	Arrays.sort(sortedNumbers);
	int left = 0;
	int right = numbers.length - 1;
	while (left < right) {
	int temp = sortedNumbers[left] + sortedNumbers[right];
	if (temp == target) {
	break;
	}
	if (temp < target) {
	left++;
	} else {
	right--;
	}
	}
	int result[] = {-1, -1};
	for (int i = 0 ; i < numbers.length; i++) {
	if ((numbers[i] == sortedNumbers[left]) || (numbers[i] == sortedNumbers[right])) {
	if (result[0] == -1) {
	result[0] = i + 1;
	} else {
	result[1] = i + 1;
	break;
	}
	}
	}
	Arrays.sort(result);
	return result;
	}
	// Time Limit Exceeded O(n*n) -- Alought I optimized this one.
	public static int[] twoSum2(int[] numbers, int target) {
	int[] result = new int[2] ;
	boolean flag = false;
	for (int i = 0; i < numbers.length && !false; i++) {
	for (int j = i + 1; j < numbers.length; j++) {
	if (numbers[i] + numbers[j] == target) {
	result[0] = i;
	result[1] = j;
	flag = true;
	break;
	}
	}
	}
	return result;
	}
	}

view raw TwoSum.java hosted with ❤ by GitHub