Skip to content

5_排列组合.md

Latest commit

 

History

History
295 lines (244 loc) · 7.03 KB

5_排列组合.md

File metadata and controls

295 lines (244 loc) · 7.03 KB
Raw

排列组合

1、全排列

全排列

private List<List<Integer>> res;

private boolean[] visited;

public List<List<Integer>> permute(int[] nums) {
    res = new ArrayList<>();
    if(nums==null || nums.length==0){
        return res;
    }
    visited = new boolean[nums.length];
    List<Integer> p =new ArrayList<>();
    generatePermutation(nums,0,p);
    return res;
}

//p中保存一个有 index 的元素的排列
//向这个排列的末尾添加第 (index+1) 个元素，组成有(index+1) 个元素排列
private void generatePermutation(int[] nums,int index,List<Integer> p){
    if(index==nums.length){
        res.add(new ArrayList<>(p));
        return;
    }
    for(int i=0;i<nums.length;i++){
        if(!visited[i]){
            visited[i]=true;
            p.add(nums[i]);
            generatePermutation(nums,index+1,p);
            p.remove(p.size()-1);
            visited[i]=false;
        }
    }
}

*2、全排列 II

全排列 II

private List<List<Integer>> res;

private boolean[] visited;

public List<List<Integer>> permuteUnique(int[] nums) {
    res = new ArrayList<>();
    if(nums==null || nums.length==0){
        return res;
    }
    visited = new boolean[nums.length];
    Arrays.sort(nums);
    List<Integer> p = new ArrayList<>();
    findUniquePermutation(nums,0,p);
    return res;
}

//p 保存的是有 index 元素的排列
//向这个排列的末尾添加第 (index+1) 个元素，组成有(index+1) 个元素排列
private void findUniquePermutation(int[] nums,int index,List<Integer> p){
    if(index==nums.length){
        res.add(new ArrayList<>(p));
        return;
    }
    for(int i=0;i<nums.length;i++){
        if(!visited[i]){
            if(i>0 && nums[i-1]==nums[i] &&
               !visited[i-1]){ //注意：相邻元素相同，并且都未被访问
                continue;
            }
            visited[i]=true;
            p.add(nums[i]);
            findUniquePermutation(nums,index+1,p);
            p.remove(p.size()-1);
            visited[i]=false;
        }
    }
    return;
}

3、字符串的排列

字符串的排列

private ArrayList<String> res;
private boolean[] visited;

public ArrayList<String> Permutation(String str) {
    res = new ArrayList<>();
    if(str==null || str.length()==0){
        return res;
    }
    char[] chs = str.toCharArray();
    Arrays.sort(chs); //方便后面的去重处理
    visited = new boolean[str.length()];
    permute(chs,0,new StringBuilder());
    return res;
}

//产生排列
//p中保存一个存在index个元素的排列
//向这个排列的末尾添加第(index+1)个元素，获得包含(index+1)个元素的排列
private void permute(char[] chs,int index,StringBuilder p){
    if(index==chs.length){
        res.add(p.toString());
        return;
    }
    for(int i=0;i<chs.length;i++){
        //需要进行去重处理
        if(i>0 && chs[i-1]==chs[i] && !visited[i-1]){
            continue;
        }
        if(!visited[i]){
            p.append(chs[i]);
            visited[i] = true;
            permute(chs,index+1,p);
            p.deleteCharAt(p.length()-1);
            visited[i] = false;
        }
    }
}

*4、字母大小写全排列

字母大小写全排列

private List<String> res;

//处理 index 位置的数据
//如果 index 位置是字母的话，则替换
private void replaceLetter(int index,StringBuilder p){
    if(index==p.length()){
        res.add(p.toString());
        return;
    }
    char ch=p.charAt(index);
    if(Character.isLetter(ch)){
        p.setCharAt(index,Character.toUpperCase(ch));
        replaceLetter(index+1,p);
        p.setCharAt(index,Character.toLowerCase(ch));
        replaceLetter(index+1,p);
    }else{
        replaceLetter(index+1,p);
    }
    return;
}

public List<String> letterCasePermutation(String S) {
    res=new ArrayList<>();
    if(S==null || S.length()==0){
        return res;
    }
    StringBuilder p=new StringBuilder(S);
    replaceLetter(0,p);
    return res;
}

*5、电话号码的字母组合

电话号码的字母组合

private final String[] letterMap={
    " ",//0
    "",//1
    "abc",//2
    "def",//3
    "ghi",//4
    "jkl",//5
    "mno",//6
    "pqrs",//7
    "tuv",//8
    "wxyz"//9
};

private List<String> res;

public List<String> letterCombinations(String digits) {
    res=new ArrayList<>();
    if(digits==null || digits.length()==0){
        return res;
    }
    generateLetterCombinations(digits,0,new StringBuilder());
    return res;
}

// p 保存 digits[0,index-1] 翻译得到的字符串
private void generateLetterCombinations(String digits,int index,StringBuilder p){
    if(index==digits.length()){
        res.add(p.toString());
        return;
    }
    char[] chs=letterMap[digits.charAt(index)-'0'].toCharArray();
    for(int i=0;i<chs.length;i++){
        p.append(chs[i]);
        generateLetterCombinations(digits,index+1,p);
        p.deleteCharAt(p.length()-1);
    }
}

6、组合

组合

//思路一：暴力解法

private List<List<Integer>> res;

//c存储已经找到的组合
//从start开始搜索新的元素
private void findCombination(int n,int k,int start,List<Integer> c){
    if(k==c.size()){
        res.add(new ArrayList<>(c));
        return;
    }
    for(int i=start;i<=n;i++){
        c.add(i);
        findCombination(n,k,i+1,c);
        c.remove(c.size()-1);
    }
    return;
}

public List<List<Integer>> combine(int n, int k) {
    res=new ArrayList<>();
    if(n<=0 || k<=0 || n<k){
        return res;
    }
    List<Integer> c=new ArrayList<>();
    findCombination(n,k,1,c);
    return res;
}
//思路二：剪枝优化
private List<List<Integer>> res;

//c存储已经找到的组合
//从start开始搜索新的元素
private void findCombination(int n,int k,int start,List<Integer> c){
    if(k==c.size()){
        res.add(new ArrayList<>(c));
        return;
    }

    //优化--剪枝
    //c存储的是已经找到的组合。
    //此时还剩下k-c.size()个空位，
    //则 [i...n]之间的元素最少要有 k-c.size() 个，即 n-i+1 >= k-c.size()
    //所以有 i <= n-(k-c.size())+1

    for(int i=start;i<=n-(k-c.size())+1;i++){
        c.add(i);
        findCombination(n,k,i+1,c);
        c.remove(c.size()-1);
    }
    return;
}

public List<List<Integer>> combine(int n, int k) {
    res=new ArrayList<>();
    if(n<=0 || k<=0 || n<k){
        return res;
    }
    List<Integer> c=new ArrayList<>();
    findCombination(n,k,1,c);
    return res;
}