Leetcode - Permutations I && II

Given a collection of numbers, return all possible permutations.
For example,

[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

[Thoughts]:

public class Solution {
    public List<List<Integer>> permute(int[] num) {//15
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        permute(num, res, list);
        return res;
        
    }
    
    public void permute(int[] num, List<List<Integer>> res, List<Integer> list){
        if(list.size()==num.length) {
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i= 0; i<num.length; i++){
            if(list.contains(num[i]))continue;
            list.add(num[i]);
            permute(num, res, list);
            list.remove(list.size()-1);
        }
        return;
    }
}

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,

[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

[Thoughts]:

public class Solution {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        int[] visited = new int[num.length];
        
        Arrays.sort(num);
        helper(result, list, visited, num);
        return result;
    }
    
    public void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, int[] visited, int[] num) {
        if(list.size() == num.length) {
            result.add(new ArrayList<Integer>(list));
            return;
        }
        
        for(int i = 0; i < num.length; i++) {
            if (visited[i] == 1 || (i != 0 && num[i] == num[i - 1] && visited[i - 1] == 0)){
                continue;
            }
            visited[i] = 1;
            list.add(num[i]);
            helper(result, list, visited, num);
            list.remove(list.size() - 1);
            visited[i] = 0;
        }
    }
}

Leetcode - Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

[Thoughts]: 以2543为例过一遍

public class Solution {
    public void nextPermutation(int[] num) {
        int end = num.length-2;
        int index = -1;
        while(end>=0){
            if(num[end]<num[end+1]){
                index = end;
                break;
            }
            end--;
        }
        if(end<0){//逆序的情况，如321，转为123
            Arrays.sort(num);
            return;
        }
        //通过上一个while找到2，下面就是把2跟2后面比2大的最小数互换，得到3542
        end = num.length-1;
        while(end>index){
            if(num[end]>num[index]){
                int temp = num[index];
                num[index] = num[end];
                num[end] = temp;
                break;
            }
            end--;
        }
        
        //3是正确的位置，代码中对应index的位置，但是3后面此时是从大到小排列，逆一下，变为3245
        end = num.length-1;
        index = index+1;
        while(index<end){
            int temp = num[index];
            num[index] = num[end];
            num[end] = temp;
            end--;
            index++;
        }
    }
}

Leetcode - Combination Sum I && II

I: Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3] 

[Thoughts]:简单的dfs 回溯

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(candidates.length==0) return res;
        Arrays.sort(candidates);
        List<Integer> list = new ArrayList<Integer>();
        combinationProcess(candidates, target, 0, res, list);
        return res;
    }
    
    public void combinationProcess(int[] candidates, int target, int start, List<List<Integer>> res, List<Integer> list){
        if(target==0){
            res.add(new ArrayList(list));
            return;
        }
        
        for(int i=start; i<candidates.length; i++){
            if(candidates[i]<=target){
                target -= candidates[i];
                list.add(candidates[i]);
                combinationProcess(candidates, target, i, res, list);
                list.remove(list.size()-1);
                target += candidates[i];
            }
        }
        
    }
}

II: Each number in C may only be used once in the combination.
[Thoughts]: 加粗的敌方是和I仅有的不同的地方， 也可以用ArrayList 自带的contains方法判别是否res是否已经有这个list来避免重复

public class Solution {
    public List<List<Integer>> combinationSum2(int[] num, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(num.length==0) return res;
        Arrays.sort(num);
        List<Integer> list = new ArrayList<Integer>();
        combinationProcess(num, target, 0, res, list);
        return res;
    }
    public void combinationProcess(int[] num, int target, int start, List<List<Integer>> res, List<Integer> list){
        if(target==0){
            res.add(new ArrayList(list));
            return;
        }
        
        for(int i=start; i<num.length; i++){
            if(num[i]<=target && (i==start || num[i]!=num[i-1])){
                target -= num[i];
                list.add(num[i]);
                combinationProcess(num, target, i+1, res, list);
                list.remove(list.size()-1);
                target += num[i];
            }
        }
        
    }
}

Leetcode - Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the k^th permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
[Thoughts]:

public class Solution {
    public String getPermutation(int n, int k) {
        ArrayList<Integer> numberList = new ArrayList<Integer>();
        int fac=1; 
        for(int i=1; i<=n; i++){
            numberList.add(i);
            fac = fac * i; //fac初始化为n!
        }
        
        k--;//start from 1 in the question, start from 0 in our code
        
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++){
            fac = fac/(n-i);//若计算第一位，则后面有n-1位，后面n-1位共（n-1）!个序列，fac更新为(n-1)! 
            int index = k / fac; //计算index
            k = k % fac;
            
            sb.append(numberList.get(index));
            numberList.remove(index);//!!不要忘记除去已经使用过的数字
        }
        
        return sb.toString();
    }
}

Leetcode - Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

[Thoughts]:
找啊找啊找规律，Backtracking + DFS的赶脚

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(n<k) return res;
        List<Integer> l = new ArrayList<Integer>();
        
        combineGenerate(res, l, n, k, 1);
        return res;
    }
    
    public void combineGenerate(List<List<Integer>> res, List<Integer> l, int n, int k, int start){
        if(l.size() == k)
            res.add(new ArrayList(l));
        for(int i=start; i<=n; i++){
            l.add(i);
            combineGenerate(res, l, n, k, i+1);
            l.remove(l.size()-1);
        }
    }
}

Leetcode - Subsets I && II

I ： Given a set of distinct integers, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

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

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

public class Solution {
    public List<List<Integer>> subsets(int[] S) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        res.add(new ArrayList<Integer>()); //Note: add empty subset. 
        Arrays.sort(S);
        
        for(int i: S){
            //ArrayList is not synchronized, it must be synchronized externally.
            List<List<Integer>> temp = new ArrayList<List<Integer>>(res); 
            for(List<Integer> subset : temp){
                List<Integer> l = new ArrayList<Integer>(subset);
                l.add(i);
                res.add(l);
            }
        }
        return res;
    }
}

II: Given a collection of integers that might contain duplicates, S, return all possible subsets.
可以仍然按照I的思路，list自带contains方法可判断是否有重复。

public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] num) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        res.add(new ArrayList<Integer>());

        Arrays.sort(num);
        
        for(int i : num){
            List<List<Integer>> temp = new ArrayList<List<Integer>>(res);
            for(List<Integer> subset : temp){
                List<Integer> l = new ArrayList<Integer>(subset);
                l.add(i);
                if(!res.contains(l))
                    res.add(l);
            }
        }
        return res;
    }
}

也可以用recursive的方法去重：

public class Solution {
 public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);  // requirement is non-descending order
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> subResult = new ArrayList<Integer>();
        result.add(new ArrayList<Integer>());     // don't forget null subsets!
        subsetsWithDup(num, 0,0, result, subResult);
        return result;
    }
    public void subsetsWithDup(int[] num, int start, int level, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> subResult){
        if(level == num.length)
            return;    
        for(int i = start; i<num.length; i++){
            if(i!=start && num[i] == num[i-1]){ // this statement deal with the duplicate case.
                continue;
            }
            subResult.add(num[i]);
            result.add((ArrayList<Integer>)subResult.clone());
            subsetsWithDup(num, i+1, level + 1, result, subResult);
            subResult.remove(subResult.size() - 1);
            }
        } 
}