Lexi's Leetcode solutions

Posts Tagged ‘固定解法

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
  }
}
Advertisements

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

别用傻乎乎的additional data structure,那样可以做,但是写起来太长。这个题上来的思路就是用左中右的inorder,这样一路下来,prev.next = curr,不断update当前的node为prev。但是写了半天,不知道怎么传prev,因为担心传java reference的问题;又回到了那个IntWrapper tree serialization的题。都是一个类型:https://leetcodenotes.wordpress.com/2013/08/24/phone-serializede-serialize-a-tree/

public void addSuccessor(Node node, Node[] prev) {
  if (node == null)
    return;
  addSuccessor(node.left, prev);
  if (prev[0] != null)
    prev[0].next = node;
  prev[0] = node;
  addSuccessor(node.right, prev);
}

类似题:找tree的in order traversal第x个节点:keep一个current node的index counter,同样是inorder的pattern,到当前node的时候counter++。这个init的i应该是-1,因为第一次找到最左边的节点的时候,i先+1,然后和x比较。

public TreeNode getNthNode(TreeNode node, IntWrapper i, int x) {
  if (node == null)
    return null;
  TreeNode foundAtLeft = getNthNode(node.left, i, x);
  i.val++;
  if (i.val == x)
    return node;
  if (foundAtLeft != null)
    return foundAtLeft;
  return getNthNode(node.right, i, x);
}

对这类题型其实不够熟悉,写了有15分钟才出来,太差了。总结一下。

BST一般找不到就null了,没办法keep track of走到哪个位置的信息。所以多传两个参数,leftBoundary和rightBoundary,分别表示“当前node为root的子树的left boundary – 当前子树的immediate prev)“和“immediate next”。因为你是top down的往下算,所以左右两边的boundary不断narrow down。当node == null时,此时的最靠近自己的boundary就起作用了,找他们之间最接近x的就行了。

这题和判断一棵树是不是BST是一个套路(后面有对比):

public TreeNode getClosest(TreeNode node, TreeNode leftBoundary, TreeNode rightBoundary, int x) {
  if (node == null)
    return getClosest(leftBoundary, rightBoundary, x);
  if (node.val < x) {
    return getClosest(node.right, node, rightBoundary, x);
  } else {
    return getClosest(node.left, leftBoundary, node, x);
  }
}
private TreeNode getClosest(TreeNode prev, TreeNode next, int x) {
  if (prev == null || next == null)
    return prev == null ? next : prev;
  if (next.val - x < x - prev.val)
    return next;
  else
    return prev;
}

附加:判断一棵树是不是BST,也是一路传下来boundary,不断看当前节点是不是满足上面传下来的左右boundary, 然后往下传的时候narrow down。最开始left, right, node都是null(没有左右节点限制)。

boolean isBST(Node node, Node leftBoundary, Node rightBoundary) {
  if (node == null)
    return true;
  if ((leftBoundary != null && node.val < leftBoundary.val) || (rightBoundary != null && node.val > rightBoundary.val))
    return false;
  if (!isBST(node.left, leftBoundary, node))
    return is BST(node.right, node, rightBoundary);
}

没啥可说的,对于每个cell,如过和word的开头字母一致,就生成一个新的全是false的visited[][], 进去原matrix开始前后左右的找。直到word的每个字母都找到为止。

要点:之前做的是直接

  // left, right, up, down
  return find(board, i, j - 1, word, index + 1, visited) || find(board, i, j + 1, word, index + 1, visited)
  || find(board, i - 1, j, word, index + 1, visited) || find(board, i + 1, j, word, index + 1, visited);

这样就挂了!因为往左走的一路已经Update visited[][]了,然后没人去undo它,往右走的一支就直接拿来用了,不就乱套了么!所以在mark true的时候,函数结尾给undo一下,就可以保证一对儿出现,路径在反上来的被清理。

public boolean exist(char[][] board, String word) {
  for (int i = 0; i < board.length; i++) {
    for (int j = 0; j < board[0].length; j++) {
      if (board[i][j] == word.charAt(0)) {
        boolean found = find(board, i, j, word, 0, new boolean[board.length][board[0].length]);
        if (found)
          return true;
      }
    }
  }
  return false;
}
private boolean find(char[][] board, int i, int j, String word, int index, boolean[][] visited) {
  if (i < 0 || j < 0 || i >= board.length || j >= board[0].length)
    return false;
  if (board[i][j] != word.charAt(index) || visited[i][j])
    return false;
  visited[i][j] = true;
  if (index == word.length() - 1)
    return true;
  // left, right, up, down
  boolean found = find(board, i, j - 1, word, index + 1, visited) || find(board, i, j + 1, word, index + 1, visited)
                || find(board, i - 1, j, word, index + 1, visited) || find(board, i + 1, j, word, index + 1, visited);
  visited[i][j] = false;//这样就能保证每次true的能给false回来
  return found;
}

这个题和前几天做的另一道“找二叉树的第n个元素“一样,用到的是pass-count technique:用一个IntWrapper keep track of 线性的index。无论tree怎么走,这个index是不断增加的。

serialize很简单,用#表示null,然后中左右(pre order)的traverse一遍就变成serialize的文件了。

deserialize的话,和preorder一样,怎么来的就怎么populate回去。是#,说明populate null,就不用往下做了;不是的话,继续做;重点是要keep track of current element in the array,就用到了一个Integer wrapper好能把count的这个值一路传下去。需要特别小心的是,这个count要一直增加,不管当前是不是#!

Node deserialize(char[] arr, IntWrapper i) {
  i.val++;//这个不能放if后面!
  if (arr[i.val] == '#')
    return null;
  Node newNode = new Node(arr[i.val]);
  newNode.left = deserialize(arr, i);
  newNode.right = deserialize(arr, i);
  return newNode;
}