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

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.

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.

Note: 

Kadane's algorithm

这是一道非常经典的动态规划的题目，用到的思路我们在别的动态规划题目中也很常用，以后我们称为”局部最优和全局最优解法“。
基本思路是这样的，在每一步，我们维护两个变量，一个是全局最优，就是到当前元素为止最优的解是，一个是局部最优，就是必须包含当前元素的最优的解。接下来说说动态规划的递推式（这是动态规划最重要的步骤，递归式出来了，基本上代码框架也就出来了）。假设我们已知第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".

click to show clarification.

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

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

Two Sum

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

Solution1: brute force

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        
        for(int i = 0; i < numbers.length; i++) {
            for(int j = i + 1; j < numbers.length; j++) {
                if(numbers[i] + numbers[j] == target) {
                    res[0] = i + 1;
                    res[1] = j + 1;
                }
            }
        }
        return res;
    }
}

Solution2:  HashMap

Time complexity depends on the put and get operations of HashMap which is normally O(1).

O(n) runtime, O(n) space.

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        HashMap map = new HashMap();
        
        for(int i = 0; i < numbers.length; i++) {
            if(map.containsKey(target-numbers[i])) {
                res[0] = map.get(target - numbers[i]) + 1;
                res[1] = i + 1;
            }else {
                map.put(numbers[i], i);
            }
        }
        return res;
    }
}

Solution3:  
先对数组进行排序，然后使用夹逼的方法找出满足条件的pair. 
算法的时间复杂度是O(nlogn+n)=O(nlogn)，空间复杂度取决于排序算法。
注意：输出结果改成了满足相加等于target的两个数，而不是他们的index。因为要排序，如果要输出index，需要对原来的数的index进行记录，方法是构造一个数据结构，包含数字的值和index，然后排序。

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        
        Arrays.sort(numbers);
        int l = 0, r = numbers.length - 1;
        while(l < r) {
            if(numbers[l] + numbers[r] == target) {
                res[0] = numbers[l];
                res[1] = numbers[r];
                return res;
            }else if(numbers[l] + numbers[r] > target) {
                r--;
            }else {
                l++;
            }
        }
        return null;
    }
}