bugCat's Blog

毛的感情的程序猿

0%

排列组合题目小结

发表于 更新于 分类于
本文字数： 9.3k 阅读时长 ≈ 8 分钟

排列组合题目小结

排列题目

全排列

题目描述

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

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

没有重复元素，比较简单，可以放心的进行交换

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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
         public List<List<Integer>> permute(int[] nums) {
                 List<List<Integer>> res = new ArrayList<>();
                dfs(nums, res, 0);
                return res;
            }

    private void dfs(int[]nums,List<List<Integer>> res,int index){
        if (index==nums.length-1) {
            List<Integer> path = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                path.add(nums[i]);
            }
            res.add(path);
        }

        for (int i = index; i < nums.length; i++) {
            //排列树进行交换
            swap(nums, index, i);
            dfs(nums,res,index+1);
            swap(nums, index, i);
        }
    }

    private void swap(int[] cs,int i,int j){
        int temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
    }
}

全排列2

题目描述

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

1
2
3
4
5
6
7
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutations-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

有重复的数字，进行排列时就会有重复，所以我们再交换的时候加入set，可以抵消这种交换带来的问题

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
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        dfs(nums, res, 0);
        return res;
    }

    public void dfs(int[]nums,List<List<Integer>> res,int index){
        if (index==nums.length-1) {
            List<Integer> path = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                path.add(nums[i]);
            }
            res.add(path);
            return;
        }
        Set<Integer> intSet = new HashSet<Integer>();
        for (int i = index; i < nums.length; i++) {
            if (i==index || !intSet.contains(nums[i])) {
                intSet.add(nums[i]);
                swap(nums, index, i);
                dfs(nums,res,index+1);
                swap(nums, index, i);
            }
        }
    }

    private void swap(int[] cs,int i,int j){
        int temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
}

下一个排列

题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/next-permutation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

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
class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) return;

        int i = nums.length - 2;
        //从后向前先找第一个从后看是降序。
        //eg : 1,4,3,2 找到 1 
        while (i>-1 && nums[i+1]<=nums[i]) {
            i--;
        }

        int j = nums.length - 1;
        if(i>-1){
            
            //找到刚好比nums[i]大的数
            //eg : 1,4,3,2 中已经找到了1，所以接着找到2
            while(nums[i]>=nums[j])j--;
            swap(nums,i,j);
        }
        //出来变成 2,4,3,1

        i++;
        j = nums.length-1;
        //将剩下的数进行逆序，变成小的在前面
        //eg 2,4,3,1 -> 2,1,3,4
        while (i<j) {
           swap(nums,i,j);
            i++;
            j--;
        }
    }

     void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

思路其实比较简单，直接从后向前先找第一个从后看是降序，可以参考：https://leetcode-cn.com/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/

第k个排列

题目描述

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

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

给定 n 和 k，返回第 k 个排列。

说明：

  • 给定 n 的范围是 [1, 9]。
  • 给定 k 的范围是[1, n!]。

示例 1:

1
2
输入: n = 3, k = 3
输出: "213"

示例 2:

1
2
输入: n = 4, k = 9
输出: "2314"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-sequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder res = new StringBuilder();
        StringBuilder num = new StringBuilder("123456789");
        int[] f= new int[n];
        f[0] = 1;
        for (int i = 1; i < f.length; i++) {
            f[i] = f[i-1]*i;
        }
        --k;
        for (int i = n; i >=1; --i) {
            int j = k/f[i-1];
            k%=f[i-1];
            res.append(num.charAt(j));
            num.deleteCharAt(j);
        }
        return res.toString();
    }
}

参考：https://www.cnblogs.com/ariel-dreamland/p/9149577.html

组合题目

子集

题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

代码

这个组合问题不存在重复数字，所以不慌，比较简单

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
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        ArrayList<Integer>ans = new ArrayList<>();
        dfs(nums,ans,0);
        return res;
    }

     /**
     * 回溯
     * @param nums
     * @param ans
     * @param n 从第n个数开始没有被访问
     */
    public void dfs(int []nums,ArrayList<Integer>ans,int n){
        
        res.add(new ArrayList(ans));
        for (int i = n; i < nums.length; i++) {
            ans.add(nums[i]);
            dfs(nums, ans, i+1);
           ans.remove(ans.size()-1);
        }
        
    }
}

子集II

题目描述

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

代码

有重复，需要进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
       Arrays.sort(nums);
        List<Integer>ans = new ArrayList<>();
        dfs(nums,ans,0);
        return res;
    }

    public void dfs(int []nums,List<Integer>ans,int n){
       res.add(new ArrayList(ans));
        for (int i = n; i < nums.length; i++) {
             //剪枝情况
             //这个判断需要理解
            if (i > n && nums[i] == nums[i - 1] ) continue;
            ans.add(nums[i]);
            dfs(nums, ans, i+1);
           ans.remove(ans.size()-1);
        }
        
    }
}

组合

题目描述

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例:

1
2
3
4
5
6
7
8
9
10
输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combinations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

为了和上面呼应，所以创建了nums这个数组，其实不需要创建也可以

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
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    int k;
    int []nums;
    public List<List<Integer>> combine(int n, int k) {
        nums = new int[n];
        this.k=k;
        for (int i = 0; i < nums.length; i++) {
            nums[i] = i+1;
        }
        LinkedList<Integer> path = new LinkedList<>();
        dfs(path,0);
        return res;
    }
    
    void dfs(LinkedList<Integer> path,int n){
        if (path.size()==k) {
            res.add(new LinkedList(path));
            return ;
        }

        for (int i = n; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(path,i+1);
            path.removeLast();
        }
    }
}

官方答案就没有创建，链接：https://leetcode-cn.com/problems/combinations/solution/zu-he-by-leetcode/

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
class Solution {
  List<List<Integer>> output = new LinkedList();
  int n;
  int k;

  public void backtrack(int first, LinkedList<Integer> curr) {
    // if the combination is done
    if (curr.size() == k)
      output.add(new LinkedList(curr));

    for (int i = first; i < n + 1; ++i) {
      // add i into the current combination
      curr.add(i);
      // use next integers to complete the combination
      backtrack(i + 1, curr);
      // backtrack
      curr.removeLast();
    }
  }

  public List<List<Integer>> combine(int n, int k) {
    this.n = n;
    this.k = k;
    backtrack(1, new LinkedList<Integer>());
    return output;
  }
}

组合总和

题目描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
  [7],
  [2,2,3]
]

示例 2：

1
2
3
4
5
6
7
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

提示：

  • 1 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • candidate 中的每个元素都是独一无二的。
  • 1 <= target <= 500

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

没有重复元素，数字可以无限制重复使用，数组并不是有序的

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
class Solution {
    List<List<Integer>> res = null;
    int[] candidates;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res = new LinkedList<>();
        if (candidates!=null&&candidates.length>0) {
            LinkedList<Integer> choose = new LinkedList<>();
            this.candidates = candidates;
            dfs(choose,target,0);
        }
        return res;
    }

    void dfs(LinkedList<Integer> choose,int target,int index){
        if (target==0) {
            res.add(new LinkedList(choose));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            //剪枝
            if (target>=candidates[i]) {
                choose.add(candidates[i]);
                //传递的是i，说明这个数字和可以使用
                dfs(choose,target-candidates[i],i);
                choose.pollLast();
            }
        }
    }
}

组合

题目描述

给定一个数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

  • 所有数字（包括目标数）都是正整数。
  • 解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码

没有重复元素，数字不可以无限制重复使用，因为有重复元素，所以我们采用的方法是直接进行排序

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 = null;
    int[] candidates;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        res = new LinkedList<>();
        if (candidates!=null&&candidates.length>0) {
            LinkedList<Integer> choose = new LinkedList<>();
            Arrays.sort(candidates);
            this.candidates = candidates;

            dfs(choose,target,0);
        }
        return res;
    }
    
    void dfs(LinkedList<Integer> choose,int target,int index){
        if (target==0) {
            res.add(new LinkedList(choose));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            //大于 index 这个很灵性,需要和大于 0 进行对比
            //大于 index说明index本身是可以取的
            if (i>index && candidates[i]==candidates[i-1]) {
                continue;
            }

            if (target>=candidates[i]) {
                choose.add(candidates[i]);
                //这里是i+1
                dfs(choose,target-candidates[i],i+1);
                choose.pollLast();
            }else{
                break;
            }
        }
    }
}

总结

排列组合问题我总是忘记，所以记录一下，方便下次查看