欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

排列组合问题总结:

程序员文章站 2022-06-28 16:13:17
1、给定一个 没有重复 数字的序列,返回其所有可能的全排列。示例:输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]先想一下模板: public void dfs(int k){ if (k==nums.length){ System.out.println(tmp); //排列完毕 打印。 r......

1、给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

先想一下模板:

      public void dfs(int k){
        if (k==nums.length){
            System.out.println(tmp);    //排列完毕 打印。
            return;
        }
        for(int i=0;i<nums.length;i++ ){
            tmp.set(k,nums[i]);          //从第0位开始依次赋值
            dfs(k+1);
        }
    }

写出下面的代码

import java.util.*;

class Solution {
    List<List<Integer>> res;
    List<Integer> tmp = new ArrayList<>();
    boolean[] used ;
    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];                    //初始化
        for(int i=0;i<used.length;i++){
            used[i] =false;
            tmp.add(0);
        }

        res = new ArrayList<>();
        dfs(0, nums);
        return res;
    }

    public void dfs(int k, int[] nums) {            //套模板
        if (k == nums.length) {
            res.add(new ArrayList<>(tmp));    //注意这里
        
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
              
                tmp.set(k,nums[i]);
                used[i] = true;
                dfs(k + 1, nums);
                used[i] = false;
        
            }
        }
    }

}

看了题解 回溯思想: 主要代码差别在这里:(其实差不多)

  // tmp.add(0); 注释掉

public void dfs(int k, int[] nums) {            //套模板
        if (k == nums.length) {
            res.add(new ArrayList<>(tmp));
            System.out.println("out" + tmp);
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                tmp.add(nums[i]);            
                used[i] = true;
                dfs(k + 1, nums);
                used[i] = false;
                tmp.remove(tmp.size()-1);    //回溯 还原状态
            }
        }
    }

2、全排列II

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

 

示例 1:

输入:nums = [1,1,2]
输出:
[[1,1,2],
 [1,2,1],
 [2,1,1]]

思考和上面的不同,

法一:可以直接在res里面去重

法二:先排序,回溯的时候 进行剪枝 。题解可参考:回溯剪枝
 

            if (used[i])
                continue;
            if(i>0 &&nums[i]==nums[i-1]&&!used[i-1])  //如果相等,且前一个没有使用
                continue;

 

 

3、

给定两个整数 nk,返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
public class Solution {
    List<List<Integer>> res;
    List<Integer> tmp = new ArrayList<>();

    public static void main(String[] args) {
        Solution s = new Solution();
        s.combine(4,2);
    }

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

    public void dfs(int b,int kk,int n) {            //套模板
        if (tmp.size()==kk) {
            res.add(new ArrayList<>(tmp));
            System.out.print(tmp);
            return;
        }
        for (int i = b; i <=n; i++) {
                tmp.add(i);
                dfs(i+1,kk,n);            //这里的不同点是i+1  不是上面排列中的k [[1, 2][1, 3][1, 4][2, 3][2, 4][3, 4]]
                // 如果改成上面排列中的的k(也就是改成b+1) [[1, 2][1, 3][1, 4][2, 2][2, 3][2, 4][3, 2][3, 3][3, 4][4, 2][4, 3][4, 4]]
                // 改成b [[1, 1][1, 2][1, 3][1, 4][2, 1][2, 2][2, 3][2, 4][3, 1][3, 2][3, 3][3, 4][4, 1][4, 2][4, 3][4, 4]]
                tmp.remove(tmp.size()-1);
        }
    }

}

 

本文地址:https://blog.csdn.net/yu1336199790/article/details/112265586

相关标签: leetcode 算法