Posted on | In

Solution 1: accepted

BFS.

  1. two queues
  2. one queue + one flag node
  3. one queue + int size (chosen)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (root == null) {
      return result;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
      ArrayList<Integer> list = new ArrayList<>();
      int size = queue.size();
      for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        list.add(node.val);
        if (node.left != null) {
          queue.add(node.left);
        }
        if (node.right != null) {
          queue.add(node.right);
        }
      }
      result.add(list);
    }
    return result;
}

Posted on | In

Solution 1: accepted 3ms

BFS. Viration of question 102.Try recursive as well.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if (root == null) {
      return result;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    boolean reverse = false;
    while (!queue.isEmpty()) {
      ArrayList<Integer> list = new ArrayList<>();
      int size = queue.size(); // get size now as it's dynamic
      for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        list.add(node.val);
        if (node.left != null) {
          queue.add(node.left);
        }
        if (node.right != null) {
          queue.add(node.right);
        }
      }
      if (reverse) {
          Collections.reverse(list);
          reverse = false;
      } else {
          reverse = true;
      }
      result.add(list);
    }
    return result;
}

Posted on | In

Solution 1: accepted 4ms

Time: O(n)
Space: O(1) (O(h) if the stack space is considered)

```java
class Solution {
// consider to use a class Type to record the value
static int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPath(root);
int temp = max;
max = Integer.MIN_VALUE;
return temp;
}

public int maxPath(TreeNode root) {
    if (root == null) {
        return 0;
    } else {
        // divide
        int left = maxPath(root.left);
        int right = maxPath(root.right);

        // conquer
        max = Math.max(max, root.val + left + right);
        return Math.max(0, root.val + Math.max(0, Math.max(left, right)));
    }       
}

}

Posted on | In

Solution1�� accepted

������java
class Solution {
public List binaryTreePaths(TreeNode root) {
List result = new ArrayList<>();
List path = new ArrayList<>();
traverse(result, path, root);
return result;
}

private void traverse(List<String> result, List<Integer> path, TreeNode root) {
    if (root == null) {
        return;
    } 
    path.add(root.val);
    if (root.left == null && root.right == null) {
        result.add(formatList(path));
    } else {
        traverse(result, path, root.left);
        traverse(result, path, root.right);
    }
    path.remove(path.size() - 1);
}

private String formatList(List<Integer> path) {
    StringBuilder sb = new StringBuilder();
    sb.append(path.get(0));
    for (int i = 1; i < path.size(); i++) {
        sb.append("->" + path.get(i));
    }
    return sb.toString();
}

}
������

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        traverse(result, "", root);
        return result;
    }
    
    private void traverse(List<String> result, String path, TreeNode root) {
        if (root == null) {
            return;
        } 
        
        path += root.val;
        if (root.left == null && root.right == null) {
            result.add(path);
        } else {
            traverse(result, path + "->", root.left);
            traverse(result, path + "->", root.right);
        }
    }
}

Posted on | In

Solution 1: accepted

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<List<Integer>> combinationSum2(int[] cand, int target) {
    Arrays.sort(cand);
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    dfs_com(cand, 0, target, path, res);
    return res;
}
public void dfs_com(int[] cand, int cur, int target, List<Integer> path, List<List<Integer>> res) {
    if (target == 0) {
        res.add(new ArrayList(path));
        return ;
    }
    if (target < 0) return;
    for (int i = cur; i < cand.length; i++){
        if (i > cur && cand[i] == cand[i-1]) continue;
        path.add(path.size(), cand[i]);
        dfs_com(cand, i+1, target - cand[i], path, res);
        path.remove(path.size()-1);
    }
}

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
11
12
8.88023
3
34.00515
-3
0.00001
2147483647
1.00000
2147483647
1.00000
-2147483648
2.00000
-2147483648

Solution 1: TLE

Brute force is not working. 

1
2
3
4
5
6
7
8
9
10
11
public double myPow(double x, int n) {
    if (n == 0) return (double)1;
    double result = 1;
    boolean neg = n < 0? true : false;
    n = Math.abs(n);
    while (n > 0) {
        result *= x;
        n--;
    }
    return neg? 1 / result : result;
}

Solution 2: accepted 24ms

Binary method. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public double myPow(double x, int n) {
  if (n == 0) 
      return (double)1;
  double result = 1;
  boolean isNegative = n < 0;
  if (n == Integer.MIN_VALUE) {
      result = x;
      n = Integer.MAX_VALUE;
  }
  n = n < 0? -n : n;
  while (n > 0) {
    int factor = 1;
    double base = x;
    while (n / 2 >= factor) { // n >= factor * 2 may cause overflow if n is the max or min int
      factor *= 2;
      base *= base;
    }
    result *= base;
    n -= factor;
  }
  return isNegative? 1 / result : result;
}
Alternative: accepted 20ms

Use long to avoid MAX and MIN checks.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public double myPow(double x, int n) {
  if (n == 0) 
      return (double)1;
  double result = 1;
  boolean isNegative = n < 0;
  long ln = (long)n;
  ln = ln < 0? -ln: ln;
  while (ln > 0) {
    long factor = 1;  // int will cause factor = 0 (overflow) when n = MIN_VALUE
    double base = x;
    while (ln / 2 >= factor) {
      factor *= 2;
      base *= base;
    }
    result *= base;
    ln -= factor;
  }
  return isNegative? 1 / result : result;
}

Posted on | In

Solution 1: accepted 28ms

DFS. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<>();
        if (n == 0) {
            return result;
        }
          
        comboHelper(result, list, n, k);
        return result;
    }
    
    private void comboHelper(List<List<Integer>> result,
                            List<Integer> list,
                            int n,
                            int k) {
        if (k == 0) {
            result.add(new ArrayList<>(list));
        } else {
            for (int i = n; i > 0; i--) {
                list.add(i);
                comboHelper(result, list, i - 1, k - 1);
                list.remove(list.size() - 1);
            }
        }
    }
}

Posted on | In

Test cases

1
2
3
4
5
[]
[0, 2]
[2, 2]
[1, 1, 2]
[0, 1, 2]

Solution 1: accepted 13ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int removeDuplicates(int[] nums) {
  int len = nums.length;
  if (nums.length < 2)
    return len;
  int count = 1;      
  for (int i = 1; i < len; i++) {
    if (nums[i - 1] != nums[i]) {
      nums[count] = nums[i];
      count++;
    }
  }
    return count;
}

Posted on | In

Solution 1: accepted 7ms

DFS, similar to question 078. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<>();
        permuteHelper(result, list, nums);
        return result;
    }
    
    public void permuteHelper(List<List<Integer>> result, List<Integer> list, int[] nums) {
        if (nums.length == list.size()) {
            result.add(new ArrayList<Integer>(list));  // use "else" or "return" after it to end the recursion
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (!list.contains(nums[i])) {
                    list.add(nums[i]);
                    permuteHelper(result, list, nums);
                    list.remove(list.size() - 1);
                }
            }
        }
    }
}

Posted on | In

Solution 1: accepted 3ms

DFS. Follow-up of 078 Subset. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        subsetsHelper(result, list, nums, 0);
        return result;
    }
    
    public void subsetsHelper(List<List<Integer>> result,
                              List<Integer> list,
                              int[] nums,
                              int pos) {
        result.add(new ArrayList<Integer>(list));
        for (int i = pos; i < nums.length; i++) {
            if (i == pos || nums[i] != nums[i - 1]) { // only remove duplicates in this level, i.e. [1,2] and [1,2]
                list.add(nums[i]);
                subsetsHelper(result, list, nums, i + 1); // will reset duplicates, so we will still have [1, 2, 2]
                list.remove(list.size() - 1);
            } 
        }
    }
}