Lexi's Leetcode solutions

Posts Tagged ‘easy

这题做了好几遍了,(尽管每次都有进步)但是因为一直用的二维数组char[][] board,到leetcode上跑才发现超时。问题出现在算“对角能不能放”的时候,因为char[][]要遍历才能知道之前都在哪些位置放了皇后,所以多花了遍历的时间。书上的算法是用int[] queenColAtRow,这样queenColAtRow[i]就表示“在第i行,把queen放在了result位置上“。这样可以直接O(1)的知道每行queen都放在哪列了,少遍历一维,大的就过了。

public int totalNQueens(int n) {
  ArrayList<String[]> solveNQueens = solveNQueens(n);
  return solveNQueens.size();
}
public ArrayList<String[]> solveNQueens(int n) {
  //生成全是.的board,因为要返回board本身,所以现在先填好了。
  char[][] board = new char[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      board[i][j] = '.';
    }
  }
  ArrayList<String[]> result = new ArrayList<String[]>();
  placeQueen(board, 0, n, result);
  return result;
}
private void placeQueen(char[][] board, int row, int n, ArrayList<String[]> result) {
  if (row == n) {
    result.add(copyBoard(board));
    return;
  }
  for (int col = 0; col < n; col++) {
    if (canPlace(board, row, col)) {
      board[row][col] = 'Q';
      placeQueen(board, row + 1, n, result);
      board[row][col] = '.';
    }
  }
}
private boolean canPlace(char[][] board, int row, int col) {
  // row is definitely fine
  for (int i = 0; i <= row; i++) {
    if (board[i][col] == 'Q')
      return false;
  }
  for (int i = 0; i < row; i++) {
    for (int j = 0; j < board.length; j++) {
      if (board[i][j] == 'Q' && Math.abs(i - row) == Math.abs(j - col))
      return false;
    }
  }
  return true;
}
Tags: , ,

尼玛这破题居然跑了好几遍才对!

一开始错的方法:

public int minDepth(TreeNode root) {
  if (root == null)
    return 0;
  int left = minDepth(root.left);
  int right = minDepth(root.right);
  return Math.min(left, right) + 1;
}

比如a#b这种左子树为空的树,我直接认为左子树的depth为0了,那当然左子树的depth小,然后parent直接取了0+1。问题在于,某个子树是null的时候,它不是叶子节点啊!这个时候就算没形成一个叶子到root的path,则认为depth为正无穷。改进:

public int minDepth(TreeNode root) {
  if (root == null)
    return Intger.MAX_VALUE;
  if (root.left == null && root.right == null)
    return 1; //说明是个leaf了!
  int left = minDepth(root.left);
  int right = minDepth(root.right);
  return Math.min(left, right) + 1;
}

忍不住回忆为啥做maxdepth的时候就没遇见问题呢?(如下)因为求的是max,所以那种某个子树为0的情况就被Math.max给解决了。总之这种题最好做完了试一试,一试就能立刻看出毛病了,自己干想还真想不到。

public int maxDepth(TreeNode root) {
  if (root == null)
    return 0;
  int left = maxDepth(root.left);
  int right = maxDepth(root.right);
  return Math.max(left, right) + 1;
}
Tags: ,

这题的要点在于要求inplace,即不能生成一个新list然后把当前最小的加后面。所以要zig zag的缝起来,不过也不难。list的题在所有循环处把null pointer exception处理好就行了。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  ListNode small, big, prevSmall = null;
  small = l1.val < l2.val ? l1 : l2;
  big = l1.val < l2.val ? l2 : l1;
  ListNode result = small;
  while (small != null && big != null) {
    while (small != null && small.val <= big.val) {
      prevSmall = small;
      small = small.next;
    }
  prevSmall.next = big;
  swap(small, big);
  }
  return result;
}
Tags: ,

就是merge sort那个n-way merge,轮流出牌。这个题的重点是要用heap,这样每次新加一个元素的时侯能很快的找到新的min。还有,这是第一次真的implement priority queue,需要自己写comparator(小于号说明是MinHeap)。

public ListNode mergeKLists(ArrayList<ListNode> lists) {
  ListNode result = null;
  ListNode curr = result;
  Comparator<ListNode> comp = new Comparator<ListNode>() {
    public int compare(ListNode a, ListNode b) {
      return a.val - b.val;
    }
  };
  PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>(lists.size(), comp);
  for (int i = 0; i < lists.size(); i++) {
    ListNode currHead = lists.get(i);
    if (currHead != null)
      minHeap.add(currHead);
  }
  while (!minHeap.isEmpty()) {
    ListNode smallest = minHeap.poll();
    if (result == null) {
      result = smallest;
      curr = result;
    } else {
      curr.next = smallest;
      curr = curr.next;
    }
    ListNode nextEnqueue = smallest.next;
    if (nextEnqueue != null)
      minHeap.add(nextEnqueue);
  }
  return result;
}
Tags: ,

今天又被assign了不归我的活,怒了。干脆上班不工作了,直接刷题。

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [2,6],[1,3],[8,10],[15,18],
return [1,6],[8,10],[15,18].

思路:先sort by start,然后不断判断当前的interval能不能吞噬下一个(curr.end >= next.start,说明这两个能连起来)。做的过程中发现几个问题:

  1. 本来是想直接循环list,然后不断吞噬,删掉被吞噬的。但是这样就一边iterate一边modify array了,会挂。所以还得用另一个list,然后决定是不断删list2里的东西,还是不断往list2里加东西。这个要拿例子试试哪种好使。
  2. 一开始写的是if (curr.end >= next.start) then curr.end = next.end。然后挂了几个test case,才注意到忘记了curr本身包括了next的情况。应该是curr.next = Math.max(curr.end, next.end)
  3. 第一次写java inline的comparator!
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
  Collections.sort(intervals, new Comparator<Interval>() {
    public int compare(Interval a, Interval b) {
      return a.start - b.start;
    }
  });
  ArrayList<Interval> result = new ArrayList<Interval>();
  for (int i = 0; i < intervals.size(); i++) {
    Interval curr = intervals.get(i);
    while (i < intervals.size() - 1 && curr.end >= intervals.get(i + 1).start) {
      curr.end = Math.max(curr.end, intervals.get(i + 1).end);
      i++;
    }//while出来说明curr已经吃饱了,可以加入result了。
    result.add(curr);
  }
  return result;
}
Tags: , ,

Blog Stats

  • 221,455 hits
June 2020
M T W T F S S
1234567
891011121314
15161718192021
22232425262728
2930