Leetcode Review(9)

Posted on | In |

78 Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

1
2
3
4
5
6
7
8
9
10
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

这一题相当于找所有nums的所有子集。我们可以知道，一共会有2^(nums.length)个子集。如何判断某个数在某个子集有没有出现呢。我们可以用一个mask。

n位的二进制数，有2^n种可能(0~1<<(nums.length))，对于每一种可能，如果在第j位的数是1,说明第nums[j]存在于该可能（子集）中。

时间复杂度是2^n*n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res  = new ArrayList<List<Integer>>();
        
        int n = nums.length;
        if(n==0)
            return res;
        
        for(int i = 0; i < 1<<n; i++){
            List<Integer> list = new ArrayList<>();
            for(int j = 0; j < n; j++){
                if( (1&(i>>j))!=0)
                    list.add(nums[j]);
            }
            res.add(list);
        }
        return res;
        
    }
}

337 House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

1
2
3
4
5
  3
 / \
2   3
 \   \ 
  3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

1
2
3
4
5
    3
   / \
  4   5
 / \   \ 
1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

你说这个贼还能再可怜一些吗。偷个东西还得做算法题。

我现在一看到树，第一反应就是dfs。对于每一个node，有两种可能，就是偷或者不偷。假设偷了currentNode，我们就不能偷他的左右孩子节点。但是如果不偷currentNode,对于左右孩子节点，我们就可以选择偷或者不偷（选择最优解）。所以对于每个node，我们会有两个两个状态：res[0]表示偷了当前节点；res[1]表示没有偷当前节点。

所以res[0] = root.val + left_res[1]+right_res[1];

​ res[1] = Math.max(left_res[0],left_res[1])+Math.max(right_res[0],right_res[1]);

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        if(root == null)
            return 0;
        int[] res = robber(root);
        return  Math.max(res[0],res[1]);
    }
    public int[] robber(TreeNode root){
        if(root == null)
            return new int[2];
        
        int[] left = robber(root.left);
        int[] right = robber(root.right);
        
        int[] res = new int[2];
        res[0] = root.val + left[1]+right[1]; //choose current node
        res[1] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);//not choose current node
        
        return res;
    }
}

494 Target Sum

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

  1. The length of the given array is positive and will not exceed 20.
  2. The sum of elements in the given array will not exceed 1000.
  3. Your output answer is guaranteed to be fitted in a 32-bit integer.

这一题，又是可以画树状图。左路径是乘-1，右路径是乘1。

每次往后推进一个数，到最后一个数的时候判断，如果满足条件，就把全局变量count++。

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
class Solution {
    private int count = 0;
    public int findTargetSumWays(int[] nums, int S) {
        finder(nums,0,S);
        return count;
        
    }
    
    private void finder(int[] nums, int start, int target){
        //System.out.println(nums[start]+" "+target);
        if(start == nums.length-1){
            if(nums[start]==target)
                count++;
            if(nums[start]==-target)
                count++;
            
            return;
        }
        finder(nums,start+1,target+nums[start]);
        finder(nums,start+1,target-nums[start]);
        return;
         
    }
}

但是zhengyu He同学表示这样做复杂度太高，O(n^2)。所以还是得改啊……