Skip to content

Latest commit

 

History

History
461 lines (378 loc) · 10.5 KB

6_回溯法.md

File metadata and controls

461 lines (378 loc) · 10.5 KB

回溯法

一、排列问题

*1、全排列（46）

46. 全排列

//思路：
//Perms(nums[0...n-1]) = {取出一个数字} + Perms{nums[{0...n-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]){
      p.add(nums[i]);
      visited[i]=true;

      generatePermutation(nums,index+1,p);

      p.remove(p.size()-1);
      visited[i]=false;
    }
  }
  return;
}

@Test
public void test(){
  int[] nums = {1,2,3};
  List<List<Integer>> res=permute(nums);
  for(List<Integer> list : res){
    System.out.println(list);
  }
}

2、全排列 II（47）

47. 全排列 II

//思路：
//1、先对数组进行排序，这样如果存在重复元素，则这些元素是相邻的
//2、对于重复元素,最后一个元素加入排列
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;
  }
  Arrays.sort(nums);

  visited = new boolean[nums.length];

  List<Integer> p = new ArrayList<>();
  generatePermutation(nums,0,p);

  return res;
}

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]){
      if(i>0 && (nums[i-1]==nums[i] && !visited[i-1])){
        // 为甚要加上这个 !visited[i-1]
        //实际上是指 nums[i-1] 和 nums[i] 相邻元素，并且都没有被访问，则后面的元素加入排列
        continue;
      }
      p.add(nums[i]);
      visited[i]=true;
      generatePermutation(nums,index+1,p);
      visited[i]=false;
      p.remove(p.size()-1);
    }
  }
  return;
}

@Test
public void test(){
  int[] nums = {1,1,2};
  List<List<Integer>> res=permuteUnique(nums);
  for(List<Integer> list : res){
    System.out.println(list);
  }
}

*3、字母大小写全排列（784）

784. 字母大小写全排列

private List<String> res;

public List<String> letterCasePermutation(String S) {
  res = new ArrayList<>();
  if(S.length()==0){
    res.add(S);
    return res;
  }

  StringBuilder builder = new StringBuilder(S);
  replaceCh(0,builder);
  return res;
}

//替换 index 位置元素
private void replaceCh(int index, StringBuilder builder){
  if(index==builder.length()){
    res.add(builder.toString());
    return;
  }

  char ch = builder.charAt(index);
  if(Character.isLetter(ch)){
    builder.setCharAt(index,Character.toLowerCase(ch));
    replaceCh(index+1,builder);
    builder.setCharAt(index,Character.toUpperCase(ch));
    replaceCh(index+1,builder);
  }else{
    replaceCh(index+1,builder);
  }
  return;
}

@Test
public void test(){
  //String S = "a1b2";
  String S = "3z4";
  System.out.println(letterCasePermutation(S));
}

二、组合问题

*1、组合（77）

77. 组合

private List<List<Integer>> res;

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,0,c);

  return res;
}

//c存储已经找到的组合
//从start开始搜索新的元素
private void findCombination(int n,int k,int start,List<Integer> c){
  if(k==c.size()){ //已经找到 k 个元素
    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;
}

@Test
public void test(){
  int n=4;
  int k=2;
  List<List<Integer>> res=combine(n,k);
  for(List<Integer> list : res){
    System.out.println(list);
  }
}

2、组合总和（39）

39. 组合总和

private List<List<Integer>> res;

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    res=new ArrayList<>();
    if(candidates.length==0){
        return res;
    }
    List<Integer> p=new ArrayList<>();
    solve(candidates,0,target,p);
    return res;
}

private void solve(int[] candidates,int startIndex,int target,List<Integer> p){
    if(target==0){
        res.add(new ArrayList<>(p));
    }
    for(int i=startIndex;i<candidates.length;i++){
        if(target>=candidates[i]){
            p.add(candidates[i]);
            solve(candidates,i,target-candidates[i],p);
            p.remove(p.size()-1);
        }
    }
}

3、组合总和 II（40）

40. 组合总和 II

private List<List<Integer>> res;

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    res=new ArrayList<>();
    if(candidates.length==0){
        return res;
    }
    Arrays.sort(candidates);
    List<Integer> p=new ArrayList<>();
    solve(candidates,0,target,p);
    return res;
}

private void solve(int[] candidates,int startIndex,int target,List<Integer> p){
    if(target==0){
        res.add(new ArrayList<>(p));
        return;
    }
    for(int i=startIndex;i<candidates.length;i++){
        if(i > startIndex && candidates[i] == candidates[i-1])
            continue;
        if(target>=candidates[i]){
            p.add(candidates[i]);
            solve(candidates,i+1,target-candidates[i],p);
            p.remove(p.size()-1);
        }
    }
    return;
}

4、组合总和 III（216）

216. 组合总和 III

private List<List<Integer>> res;

public List<List<Integer>> combinationSum3(int k, int n) {
    res=new ArrayList<>();
    if(k>n || k==0){
        return res;
    }
    List<Integer> p=new ArrayList<>();
    //数值是从1开始的
    findCombination(k,n,1,p);
    return res;
}

private void findCombination(int k,int n,int num,List<Integer> p){
    //注意，这里的递归结束条件
    if(k==0 && n==0){
        res.add(new ArrayList<>(p));
        return;
    }
    for(int i=num;i<=9;i++){
        //要求n>=i，这样保证(n-i)>=0,保证递归能终止
        if(n>=i){
            p.add(i);
            findCombination(k-1,n-i,i+1,p);
            p.remove(p.size()-1);
        }
    }
}

5、子集（78）

78. 子集

private List<List<Integer>> res;

private void findSubset(int[] nums,int index,List<Integer> p){
    //这里不需要递归的结束条件
    //因为当index==nums.length之后，就会自动终止递归
    //为什么自己不递归？这样会导致解缺失的情况
    //if(index==nums.length){
    //    res.add(new ArrayList<>(p));
    //return;
    //}
    //结果：[[1, 2, 3], [1, 3], [2, 3], [3]]
    //因为每次递归对数组长度是没有要求的，加上条件后，每次只能获取定长的数据
    res.add(new ArrayList<>(p));
    for(int i=index;i<nums.length;i++){
        p.add(nums[i]);
        findSubset(nums,i+1,p);
        p.remove(p.size()-1);
    }
}

public List<List<Integer>> subsets(int[] nums) {
    res=new ArrayList<>();
    if(nums.length==0){
        return res;
    }
    List<Integer> p=new ArrayList<>();
    findSubset(nums,0,p);
    return res;
}

6、子集II（90）

90. 子集 II

private List<List<Integer>> res;

private void findSubsets(int[] nums,int index,List<Integer> p){
    res.add(new ArrayList<>(p));
    for(int i=index;i<nums.length;i++){
        //剪枝去重复元素，对于搜索的任何一层决不能在本层出现重复，也就是说在相同index下不能出现重复的元素
        //(i>0 && nums[i-1]==nums[i]) 相邻的重复元素
        //i==index 表示在同一层
        if(i!=index && (i>0 && nums[i-1]==nums[i])){
            continue;
        }
        p.add(nums[i]);
        findSubsets(nums,i+1,p);
        p.remove(p.size()-1);
    }
}

public List<List<Integer>> subsetsWithDup(int[] nums) {
    res=new ArrayList<>();
    if(nums.length==0){
        return res;
    }
    Arrays.sort(nums);
    List<Integer> p=new ArrayList<>();
    findSubsets(nums,0,p);
    return res;
}

7、二进制手表（401）

401. 二进制手表

public List<String> readBinaryWatch(int num) {
    List<String> res=new ArrayList<>();
    if(num<0){
        return res;
    }
    for(int h=0;h<12;h++){
        for(int m=0;m<60;m++){
            //统计h在二进制下“1”的数量
            //h=5 --> 转化为二进制(101)-->结果为2
            if(Integer.bitCount(h)+Integer.bitCount(m)==num){
                res.add(String.format("%d:%02d",h,m));
            }
        }
    }
    return res;
}
//表示小时的灯
int[] hour={1,2,4,8};
//表示分钟的灯
int[] minute={1,2,4,8,16,32};

private List<String> res;

//num表示还需要点亮的LED数
//index表示所点的表示小时的LED的下标
private void solve(int num,int index,int[] watch){
    if(num==0){
        int h=0;
        int m=0;
        for(int i=0;i<hour.length;i++){
            h+=watch[i]*hour[i];
        }
        for(int i=0;i<minute.length;i++){
            m+=watch[i+4]*minute[i];
        }
        res.add(String.format("%d:%02d",h,m));
    }
    while(index<10){
        //选中index灯
        watch[index]=1;
        //条件取舍，对于hour>11 和 min>59的情况舍去
        if(!((watch[2]==1 && watch[3]==1)||(watch[6]==1 && watch[7]==1 && watch[8]==1 && watch[9]==1))){
            solve(num-1,index+1,watch);
        }
        watch[index]=0;
        index++;
    }
}

public List<String> readBinaryWatch(int num) {
    res=new ArrayList<>();
    //表示手表的10个LED灯，0:表示灯为开启，1表示灯开了
    int[] watch=new int[10];
    solve(num,0,watch);
    return res;
}