Lexi's Leetcode solutions

Archive for October 9th, 2013

If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
趁热打铁,这个题和上两道相比简单了不少,因为是固定长度所以不用stack了,用int[]加一个position variable。每次在这个pos上一个一个试数,每确定一个就在下一个pos处recurse。

public ArrayList<ArrayList<Integer>> combine(int n, int k) {
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  if (k <= 0 || n < 1)
    return result;
  populateResult(1, n, 0, result, new int[k]);
  return result;
}
private void populateResult(int startNum, int endNum, int pos, 
            ArrayList<ArrayList<Integer>> result, int[] path) {
  if (pos == path.length) {
    ArrayList<Integer> combination = new ArrayList<Integer>();
    convertArrayToList(path, combination);
    result.add(combination);
    return;
  }
  for (int i = startNum; i <= endNum; i++) { //i is using which number
    path[pos] = i;
    populateResult(i + 1, endNum, pos + 1, result, path); //use next 
                                            //number on next position
    //as i++, use next number on same position
  }
}

比如 {1, 1, 1, 2, 3},x = 3, 结果就是{111}{12}{3}。这个题挺难想的,和上一题又不一样。正常stack,把1push进去,然后直接在2上recurse x=2的(因为1只能用一次)。这样一直做到x==0。这样就会有重复:当stack pop空了之后,回到第二个1上,又开始push,那stack的第0个又是1了,刚才已经做过stack第0个是1的一遍了(左边的一遍肯定包括了最多种的情况),所以现在再把1放里面就会重复。所以要在做“要不要在当前layer试一下下一个数?”的决定的时候,要看“下一个数和当前数是否相等?因为当前数已经做过了,同一层layer说明是同一个position,再放当前数就会重复)。

总结:

  • combination/set: 用stack,因为长度不固定。
  • permutation: 用int[],keep一个pos pointer。
  • 主函数里面不要循环,就一个以初始值call副函数的语句就行。
  • 副函数是循环里面call自己。
public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
  Arrays.sort(num);
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  Stack<Integer> path = new Stack<Integer>();
  combinationSum(num, target, 0, path, result);
  return result;
}
private void combinationSum(int[] arr, int target, int start, Stack<Integer> path, ArrayList<ArrayList<Integer>> result) {
  if (target == 0) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.addAll(path);
    result.add(list);
    return;
  }
  for (int i = start; i < arr.length; i++) {
    if (arr[i] > target)
      return;
    path.push(arr[i]);
    combinationSum(arr, target - arr[i], i + 1, path, result);
    path.pop();
    //do we want to place arr[i + 1] at the same position arr[i] has been?
    while (i + 1 < arr.length && arr[i] == arr[i + 1]) {
      i++;
    }
  }
}

比如{2, 3, 6, 7},x = 7,组合就是{2, 2, 3}和{7}。不能有重复,且必须是sorted order。

这个是标准DFS,一定要记住。先sort array,然后试图用2,用了2之后x相当于只剩5,然后下一层递归再用2,用到没法再用为止(当前值比x还大)。失败后stack pop出来,再试着在前面用了2, 2, 2的条件下用3, 挂,pop出2,在22的条件下用3,正好,输出。然后再pop一个2,再用3, {2, 3},再用下一个3。。在脑子里想一下和树的dfs的图是一样的。

public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
  Arrays.sort(candidates);
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
  Stack<Integer> path = new Stack<Integer>();
  combinationSum(candidates, target, 0, path, result);
  return result;
}
private void combinationSum(int[] arr, int target, int start, Stack<Integer> path, ArrayList<ArrayList<Integer>> result) {
  if (target == 0) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    list.addAll(path);
    result.add(list);
    return;
  }
  for (int i = start; i < arr.length; i++) {
    if (arr[i] > target) //这时候break可以保证不要再查后面那些越来越大的
      return;
    path.push(arr[i]);
    combinationSum(arr, target - arr[i], i, path, result); //start永远不会越界,所以一开始不用check
    path.pop();
   }
 }

Blog Stats

  • 221,510 hits
October 2013
M T W T F S S
 123456
78910111213
14151617181920
21222324252627
28293031