Leetcode Review(8)

Posted on | In |

Long time no see.

22. Generate Parentheses

Description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

At first I think of using Stack, two Stacks. But actually you can draw a tree. Just like:

​ (
/ \
(( ()
​ / \
()( ()). (just a part of tree)

Every time in the left tree, we add a “(“ while in the right tree we add “)”. But there are two constraints.

  • The # of ( and ) must be small than n.
  • We can only add “)” when “)” s are less than “(“s.

So we can use recurrence. And add constraints.

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 {
    List<String> list;
    public List<String> generateParenthesis(int n) {
        list = new LinkedList<>();
        
        generateParenthesis(n,0,0,"");
        return list;
        
    }
    
    public void generateParenthesis(int n,int open, int close,String str){
        if(open == n && close == n){
            list.add(str);
        }
            
        
        if(open<n)
            generateParenthesis(n,open+1,close,str+"(");
        if(close<open)
            generateParenthesis(n,open,close+1,str+")");
        
    }
}

我感觉好像知道了，如果有递归问题，都可以画树！！

## 46 Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

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

I haven’t figure out yet.

相当于是，

对于每一串数组，

1，2，3，4，5

我们要全排列的话，可以先固定1，然后对（2，3，4，5）全排列。然后再把1和2交换，对（1，3，4，5）全排列。直到把1和5交换之后，对2，3，4，1全排列。

然后对于里面的每一个子序列，比如（2，3，4，5），是用同样的方式进行求全排列的，固定2，然后对（3，4，5）全排列，再交换2和3，对（4，5）全排列.

……

所以设被交换的第一个数为start，那么对于start，从start 后面的数，先挨个交换，然后求start+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
32
33
34
35
36
37
38
39
class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> permute(int[] nums) {
        res = new LinkedList<List<Integer>>();
        int[] aux = new int[nums.length];
        permute(nums,0);
        return res;
    
    }
    
    public void permute(int[] nums,int start){
        if(start>=nums.length)
            return;
        if(start == nums.length-1){
            List<Integer> list = new ArrayList<>();
            for(int num:nums)
                list.add(num);
            res.add(list);
            System.out.println("add");
            
        }
        for(int i = start; i<nums.length;i++){
            System.out.println("before start = "+start+"; i = "+i);
            swap(nums,start,i);
            permute(nums,start+1);
            System.out.println("after start = "+start+"; i = "+i);
            swap(nums,start,i);
        }
        
    }
    
    public void swap(int[] nums,int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
       
    
}