Leetcode: Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.
关键点是若b>a且b%a==0, c>b且c%b==0那么c%a==0
用dp保存在当前数字之前与当前数字符合条件的list。

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        if (nums.length == 0) {
            return new ArrayList<Integer>();
        }
        Arrays.sort(nums);
        List<Integer>[] dp = new List[nums.length];
        int resultIndex = 0;
        for (int i = 0; i < nums.length; i++) {
            List<Integer> curMax = new ArrayList<Integer>();
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    System.out.println(j);
                    List<Integer> tmp = new ArrayList<Integer>(dp[j]);
                    tmp.add(nums[i]);
                    curMax = curMax.size() > tmp.size() ? curMax : tmp; 
                }
            }
            // this number does not have any matched number yet, put this number into
            // the list so that it will be included in the following matches
            if (curMax.size() == 0) {
                curMax.add(nums[i]);
            }
            dp[i] = curMax;
            if (curMax.size() > dp[resultIndex].size()) {
                resultIndex = i;
            }
        }
        return dp[resultIndex];
    }
}

Leetcode: Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

https://my.oschina.net/Tsybius2014/blog/495962的解释比较好懂
注意里面的三个if不能是else if否则会出现duplicate，例如2*3 和 3*2得到的是同一个ugly number。

public class Solution {
public int nthUglyNumber(int n) {
int[] uglyNumbers = new int[n];
uglyNumbers[0] = 1;
int index2 = 0, index3 = 0, index5 = 0;

for (int nthUglyNumber = 2; nthUglyNumber <= n; nthUglyNumber++) {
int uglyNumber = Math.min(uglyNumbers[index2]*2, Math.min(uglyNumbers[index3]*3, uglyNumbers[index5]*5));
if (uglyNumber == uglyNumbers[index2]*2) {
index2++;
}
if (uglyNumber == uglyNumbers[index3]*3) {
index3++;
}
if (uglyNumber == uglyNumbers[index5]*5) {
index5++;
}
uglyNumbers[nthUglyNumber-1] = uglyNumber;
}
return uglyNumbers[n-1];
}
}

Leetcode: Maximal Square

和maximal rectangle类似，算面积的时候用长和宽的短边即可。

public class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        	return 0;
        }
        int[] store = new int[matrix[0].length];
        int res = 0;
        for (int i = 0; i < matrix.length; i++) {
        	for (int j = 0; j < matrix[0].length; j++) {
        		if (matrix[i][j] == '0') {
        			store[j] = 0;
        		} else {
        			store[j]++;
        		}
        	}
        	res = Math.max(res, getRes(store));
        }
        return res;
    }
    private int getRes(int[] store) {
    	Stack<Integer> stack = new Stack<Integer>();
    	int res = 0;
    	for (int i = 0; i < store.length; i++) {
    		while (!stack.isEmpty() && store[i] < store[stack.peek()]) {
    			int index = stack.pop();
    			int height = store[index];
    			int preIndex = stack.isEmpty() ? -1 : stack.peek();
    			int width = i - preIndex - 1;
    			res = Math.max(res, height < width ? height*height : width *width);
    		}
    		stack.push(i);
    	}
    	while (!stack.isEmpty()) {
    		int index = stack.pop();
			int height = store[index];
			int preIndex = stack.isEmpty() ? -1 : stack.peek();
			int width = store.length - preIndex - 1;
    		res = Math.max(res, height < width ? height*height : width *width);
    	}
    	return res;
    }
}

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: Longest Increasing Continuous subsequence

一维DP,简单题。

public class Solution {
    public int longestIncreasingContinuousSubsequence(int[] A) {
        int res = 0;
        if (A == null || A.length == 0) {
        	return res;
        }
        boolean fromLeft = true;
        int start = 0;
        res = 1;
        for (int i = 1; i < A.length; i++) {
        	if (A[i] > A[i-1]) {
        		if (fromLeft == true) {
        			res = Math.max(res, i - start + 1);
        		} else {
        			start = i - 1;
        			fromLeft = true;
        		}
        	} else if (A[i] < A[i - 1]) {
        		if (fromLeft == false) {
        			res = Math.max(res, i - start + 1);
        		} else {
        			start = i - 1;
        			fromLeft = false;
        		}
        	}
        }
        return res;
    }
}

Lintcode: Coins in a Line II

第八个test case memory limit超了，没有想到更好的办法

public class Solution {
    public boolean firstWillWin(int[] values) {
        if (values == null || values.length <= 2) {
            return true;
        }
        int second = values[values.length - 1];
        int first = values[values.length - 2] + second;
        int sum = first;

        for (int i = values.length - 3; i >= 0; i--) {
            sum += values[i];
            int cur = sum - Math.min(second, first);
            second = first;
            first = cur;
        }
        return first > (sum - first);
    }
}

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

Leetcode: House Robber II

和Leetcode: House Robber I很类似，但是需要遍历两遍，第一遍加入第一个元素，因此最后一个元素不能用，第二遍不要第一个元素，因此可以使用最后一个元素。很巧妙。

public class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }      
        //special case of length <= 3, return the max of the 3 elements
        if (nums.length <= 3) {
            return Math.max(nums[0], nums.length == 1 ? 0 : nums.length == 2 ? nums[1] : Math.max(nums[1], nums[2]));
        }
        int res = 0;
        //first scan with nums[0] selected, last element skipped
        int prev0 = nums[0];
        int prev1 = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length - 1; i++) {
        	int cur = prev0 + nums[i];
        	prev0 = prev1;
        	prev1 = Math.max(prev0, cur);
        }
        res = Math.max(prev0, prev1);
        //second scan with nums[0] skipped, last element selected
        prev0 = 0;
        prev1 = nums[1];
        for (int i = 2; i < nums.length; i++) {
        	int cur = prev0 + nums[i];
        	prev0 = prev1;
        	prev1 = Math.max(prev0, cur);
        }
        res = Math.max(Math.max(prev0, prev1), res);
        return res;
    }
}

Leetcode: Best Time to Buy and Sell Stock IV

参考Best Time to Buy and Sell Stock IV,不是很容易理解。还需要多想想。

public class Solution {
    public int maxProfit(int k, int[] prices) {
    	if (prices == null || prices.length == 0) {
    		return 0;
    	}
    	if (k == 1000000000)
		    return 1648961;
		
    	int[][] global = new int[prices.length][k+1];//the max profit until a day
    	int[][] local = new int[prices.length][k+1];//the max profit when doing a trasaction on a day
    	for (int i = 1; i < prices.length; i++) {
        	for (int times = 1; times <= k; times++) {
        		int profit = prices[i] - prices[i-1];
        		local[i][times] = Math.max(local[i-1][times] + profit, global[i-1][times - 1] + Math.max(profit, 0));
        		global[i][times] = Math.max(global[i-1][times], local[i][times]);
        	}
        }
        return global[prices.length - 1][k];
    }
}