Wednesday, February 25, 2015

Candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
Solution:
进行两次扫描,一次从左往右,一次从右往左。
(这道题用到的思路和Trapping Rain Water是一样的,用动态规划。)
第一次扫描的时候维护对于每一个小孩左边所需要最少的糖果数量,存入数组对应元素中,
第二次扫描的时候维护右边所需的最少糖果数,并且比较将左边和右边大的糖果数量存入结果数组对应元素中。
这样两遍扫描之后就可以得到每一个所需要的最最少糖果量,从而累加得出结果。
方法只需要两次扫描,所以时间复杂度是O(2*n)=O(n)。空间上需要一个长度为n的数组,空间复杂度是O(n)。
public class Solution {
    public int candy(int[] ratings) {
        if(ratings == null || ratings.length == 0)
            return 0;
        
        int[] num = new int[ratings.length];
        num[0] = 1;//at least has 1 candy
        
        for(int i = 1; i < ratings.length; i++) {
            if(ratings[i] > ratings[i - 1]) {
                //if child i has rating higher than i-1, which should 1 bigger than its left neighbour
                num[i] = num[i - 1] + 1;
            }else {
                num[i] = 1;
            }
        }
        
        int res = num[ratings.length - 1];
        
        for(int i = ratings.length - 2; i >= 0; i--) {
            int cur = 1;
            if(ratings[i] > ratings[i + 1]) {
                //if child i has rating higher than its right neighbour, but the candies array did not 
                //represented this situation correctly, then correct it.
                cur = num[i + 1] + 1;
            }
            res += Math.max(cur, num[i]);
            num[i] = cur;
        }
        
        return res;
    }
}

Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
    1
   / \
  2   3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
Solution: Recursion. Similar as [LeetCode] Binary Tree Maximum Path Sum Solution, the difference here is only adding a track variable to sum all the paths.
问题处理:
1 分情况就是: (1)空节点, (2)到了叶子节点, (3)一般节点(包括只有左孩子,只有右孩子,两个孩子都有)
2 递归到该点的时候就把这点的值与前面的值乘以10,然后相加
3 需要如何保存前面的值?以参数传递的方式保存,以供下一层使用。总值可以以两种方式保存:参数传递方式,返回函数值方式。
算法的本质是一次先序遍历,所以时间是O(n),空间是栈大小,O(logn)。
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int sumNumbers(TreeNode root) {
        return helper(root, 0);
    }
    
    public int helper(TreeNode root, int sum) {
        if(root == null) { //terminate condition, root == null, just return 0
            return 0;
        }
        
        if(root.left == null && root.right == null) { //terminate condition, if root == leaf, add the value to sum and return
            return sum * 10 + root.val;
        }
            
        return helper(root.left, sum*10+root.val) + helper(root.right, sum*10+root.val);
        
    }
}

Word Break

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".
Solution:
This problem can be solve by using a naive approach, which is trivial. A discussion can always start from that though. Time: O(2^n).
首先我们要存储的历史信息res[i]是表示到字符串s的第i个元素为止能不能用字典中的词来表示,我们需要一个长度为n的布尔数组来存储信息。然后假设我们现在拥有res[0,...,i-1]的结果,我们来获得res[i]的表达式。思路是对于每个以i为结尾的子串,看看他是不是在字典里面以及他之前的元素对应的res[j]是不是true,如果都成立,那么res[i]为true,写成式子是
假设总共有n个字符串,并且字典是用HashSet来维护,那么总共需要n次迭代,每次迭代需要一个取子串的O(i)操作,然后检测i个子串,而检测是constant操作。所以总的时间复杂度是O(n^2)(i的累加仍然是n^2量级),而空间复杂度则是字符串的数量,即O(n)。
public class Solution {
    public boolean wordBreak(String s, Set dict) {
        if(s == null || s.length() == 0)
            return true;
        
        //Define res[] such that res[i]==true => 0-(i-1) can be segmented using dictionary
        boolean[] res = new boolean[s.length() + 1];
        res[0] = true;  //set first to be true, since we need initial state
        
        for(int i = 0; i < s.length(); i++) {
            StringBuilder str = new StringBuilder(s.substring(0, i+1));
            for(int j = 0; j <= i; j++) {
                if(res[j] == true && dict.contains(str.toString())) {
                    res[i + 1] = true;
                    break;
                }
                str.deleteCharAt(0);
            }
        }
        return res[s.length()];
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/22358863

Tuesday, February 24, 2015

Maximum Subarray


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.
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.
Note: 
这是一道非常经典的动态规划的题目,用到的思路我们在别的动态规划题目中也很常用,以后我们称为”局部最优和全局最优解法“。
基本思路是这样的,在每一步,我们维护两个变量,一个是全局最优,就是到当前元素为止最优的解是,一个是局部最优,就是必须包含当前元素的最优的解。接下来说说动态规划的递推式(这是动态规划最重要的步骤,递归式出来了,基本上代码框架也就出来了)。假设我们已知第i步的global[i](全局最优)和local[i](局部最优),那么第i+1步的表达式是:
local[i+1]=Math.max(A[i], local[i]+A[i]),就是局部最优是一定要包含当前元素,所以不然就是上一步的局部最优local[i]+当前元素A[i](因为local[i]一定包含第i个元素,所以不违反条件),但是如果local[i]是负的,那么加上他就不如不需要的,所以不然就是直接用A[i];
global[i+1]=Math(local[i+1],global[i]),有了当前一步的局部最优,那么全局最优就是当前的局部最优或者还是原来的全局最优(所有情况都会被涵盖进来,因为最优的解如果不包含当前元素,那么前面会被维护在全局最优里面,如果包含当前元素,那么就是这个局部最优)。

接下来我们分析一下复杂度,时间上只需要扫描一次数组,所以时间复杂度是O(n)。空间上我们可以看出表达式中只需要用到上一步local[i]和global[i]就可以得到下一步的结果,所以我们在实现中可以用一个变量来迭代这个结果,不需要是一个数组,也就是如程序中实现的那样,所以空间复杂度是两个变量(local和global),即O(2)=O(1)。
public class Solution {
    public int maxSubArray(int[] A) {
        int sum = A[0];
        int maxSum = A[0];
        for(int i = 1; i < A.length; i++) {
            sum = Math.max(A[i], sum + A[i]);
            maxSum = Math.max(sum, maxSum);
        }
        return maxSum;
    }
}

Remove Duplicates from Sorted Array II

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].
Notes: this problem requires in-place array manipulation.
Solution1: run time complexity O(n), space complexity is constant space.
public class Solution {
    //no need to change the given array's size, 
    //only change the first k elements of the array which has duplicates removed.
    public int removeDuplicates(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        
        boolean isSameTwo = false;
        int pre = A[0];
        int count = 0;
        
        int o = 1;
        
        for(int i = 1; i < A.length; i++) {
            int cur = A[i];
            
            if(cur == pre) {
                if(!isSameTwo) {
                    isSameTwo = true;
                    A[o] = cur;
                    o++;
                    continue;
                }else {
                    count++;
                }
            }else {
                pre = cur;
                A[o] = cur;
                o++;
                isSameTwo = false;
            }
        }
        return A.length - count;
    }
}
Solution2: run time complexity O(n), space complexity is constant space.
public class Solution {
    //no need to change the given array's size, 
    //only change the first k elements of the array which has duplicates removed.
    public int removeDuplicates(int[] A) {
        if(A.length < 2)
            return A.length;
        
        int pre = 1;
        int cur = 2;
        
        while(cur < A.length) {
            if(A[cur] == A[pre] && A[cur] == A[pre - 1]) {
                cur++;
            }else {
                pre++;
                A[pre] = A[cur];
                cur++;
            }
        }
        return pre + 1;
    }
}
Solution3:run time complexity O(n), space complexity is constant space.
public class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int count = 1;
        boolean hasTwo = false;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                if (!hasTwo) {
                    nums[count] = nums[i];
                    count++;
                    hasTwo = true;
                } else {
                    continue;
                }
            } else {
                nums[count] = nums[i];
                count++;
                hasTwo = false;
            }
        }
        
        return count;
    }
}

Reverse Words in a String

Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Clarification:
  • What constitutes a word?
    A sequence of non-space characters constitutes a word.
  • Could the input string contain leading or trailing spaces?
    Yes. However, your reversed string should not contain leading or trailing spaces.
  • How about multiple spaces between two words?
    Reduce them to a single space in the reversed string.
Solution: O(n) runtime, O(n) space
One simple approach is a two-pass solution: First pass to split the string by spaces into an array of words, then second pass to extract the words in reversed order.
We can do better in one-pass. While iterating the string in reverse order, we keep track of a word’s begin and end position. When we are at the beginning of a word, we append it.
public class Solution {
    public String reverseWords(String s) {
        StringBuilder result = new StringBuilder();
        int len = s.length();
        
        for(int i = s.length() - 1; i >= 0; i--) {
            if(s.charAt(i) == ' ') {
                len = i;
            }else if(i == 0 || s.charAt(i - 1) == ' ') {
                if(result.length() != 0) {
                    result.append(' ');
                }
                result.append(s.substring(i, len));
            }
        }
        return result.toString();
    }
}

Tuesday, February 10, 2015

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
Solution: in each combination, former number is smaller than the following number.  In another word, [1, 2] and [2, 1] is considered as the same combination, and only [1, 2] is required as the result in this problem.
For choosing number in a specific layer, we can use a iteration, e.g. in the first layer, we try 1-5.  While for step in another layer, we can use recursive call.  Parameters we need for a recursive call are the current combination, the combination result set, the n, the k, and the start point of iteration (e.g. if we chose 1 for the first position, start point of 2nd position is 2; while if we chose 2 for the first position, start point of second position is 3).  
复杂度O(n!)
类似于 Permutation那道
public class Solution {
    public ArrayList> combine(int n, int k) {
        ArrayList> result = new ArrayList>();
        ArrayList comb = new ArrayList();
        
        if(n < k)
            return result;
        int start = 1;   //start is begin from 1.
        select(n, k, start, comb, result);
        return result;
    }
    
    public void select(int n, int k, int start, ArrayList comb, ArrayList> result) {
        
        //one possible combination constructed 
        if(comb.size() == k) {
            result.add(new ArrayList(comb));  //because comb is ArrayList<> so it will not disappear from stack to stack
            return;
        }else {   
            for(int i = start; i <= n; i++) {   //try each possibility number in current position 
                comb.add(i);
                select(n, k, i+1, comb, result);  //after selecting number for current position, process next position 
                comb.remove(comb.size() - 1);  //clear the current position to try next possible number
            }
        }
    }
}
Or:
public class Solution {
    public List> combine(int n, int k) {
        List> res = new ArrayList>();
        if (n < k) {
            return res;
        }
        
        List list = new ArrayList();
        int start = 1;
        helper(res, list, n, k, start);
        return res;
    }
    
    public void helper(List> res, List list, int n, int k, int start) {
        if (list.size() == k) {
            res.add(new ArrayList(list));
            return;
        } else {
            for (int i = start; i <= n; i++) {
                list.add(i);
                helper(res, list, n, k, i + 1);
                list.remove(list.size() - 1);
            }
        }
    }
}