46、47、全排列

leetcode

Created At : 2020-07-26 00:19

Count:1.2k Views 👀 :

Comment:

46、全排列
1. 示例:

题解

1、深度优先搜索
47、全排列 2
1. 示例:
解

46、全排列

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

示例:

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

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

题解

1、深度优先搜索

回溯法实现

class Solution {
    public void  backtrack(int n,ArrayList<Integer> nums,List<List<Integer>> output,int first) {
        // 所有数字都加入了
        if (first == n) {
            output.add(new ArrayList<Integer>(nums));
        }
        
        // 遍历，递归和回溯
        for (int i =  first;i < n;i++) {
            Collections.swap(nums,first,i);
            
            backtrack(n,nums,output,first + 1);
            
            Collections.swap(nums,first,i);
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        // 返回的结果
        List<List<Integer>> output = new LinkedList();
        
        // 复制到基本列表中
        ArrayList<Integer> nums_lst = new ArrayList<Integer>();
        for (int num:nums) {
            nums_lst.add(num);
        }
        
        int n = nums.length;
        backtrack(n,nums_lst,output,0);
        return output;
    }
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        int len=nums.length;
        if(len==0) return res;
        boolean[] visit=new boolean[len];
        dfs(nums,len,res,new ArrayList<Integer>(),visit);
        return res;

    }

    private void dfs(int[] nums,int len,List<List<Integer>> res,List<Integer> path,boolean[] visit){
        if(path.size()==len){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i=0;i<len;i++){
            if(visit[i]) {continue;}
            visit[i]=true;
            path.add(nums[i]);
            dfs(nums,len,res,path,visit);
            path.remove(path.size()-1);
            visit[i]=false;
        }

    }
}

47、全排列 2

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

示例:

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

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

解

回溯 + 剪枝

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Solution {

    private List<List<Integer>> res = new ArrayList<>();
    private boolean[] used;

    private void findPermuteUnique(int[] nums, int depth, Stack<Integer> stack) {
        if (depth == nums.length) {
            res.add(new ArrayList<>(stack));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                // 修改 2：因为排序以后重复的数一定不会出现在开始，故 i > 0
                // 和之前的数相等，并且之前的数还未使用过，只有出现这种情况，才会出现相同分支
                // 这种情况跳过即可
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                    continue;
                }
                used[i] = true;
                stack.add(nums[i]);
                findPermuteUnique(nums, depth + 1, stack);
                stack.pop();
                used[i] = false;
            }
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        // 修改 1：首先排序，之后才有可能发现重复分支
        Arrays.sort(nums);

        // 如果是降序，需要把 nums 变为包装数组类型，输入 Arrays.sort() 方法才生效，并且还要传入一个比较器，搜索之前，再转为基本类型数组，因此不建议降序排序
        // Integer[] numsBoxed = IntStream.of(nums).boxed().collect(Collectors.toList()).toArray(new Integer[0]);
        // Arrays.sort(numsBoxed, Collections.reverseOrder());
        // nums = Arrays.stream(numsBoxed).mapToInt(Integer::valueOf).toArray();

        used = new boolean[len];
        findPermuteUnique(nums, 0, new Stack<>());
        return res;
    }
}

//  作者：liweiwei1419
// 链接：https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/

C++版

/ author: carryzz

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int> &nums) {
        sort(nums.begin(), nums.end());// 先排个序
        int n = nums.size();
        vector<int> temp;// 单个局部解
        vector<vector<int>> res; // 结果集合
        vector<bool> visited(n, false);// 标记数组
        DFS(nums, temp, res, 0, visited);// 深度优先搜索
        return res;
    }

    void DFS(vector<int> &nums, vector<int> &temp, vector<vector<int>> &res, int cursize, vector<bool> &visited) {
        if (cursize == nums.size()) {// 递归结束入口
            res.push_back(temp);
            return;
        }
        // 递归 回溯
        for (int i = 0; i < nums.size(); i++) {
            if (!visited[i]) {// 没有访问过的位置
                // 剪枝
                if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1])
                    continue;
                // 递归
                temp.push_back(nums[i]);
                visited[i] = true;
                DFS(nums, temp, res, cursize + 1, visited);
                // 回溯
                temp.pop_back();
                visited[i] = false;
            }
        }
    }
};

int main() {
    Solution solution = Solution();
    // 示例
    vector<int> nums;
    nums.push_back(2);
    nums.push_back(3);
    nums.push_back(3);

    vector<vector<int>> res = solution.permuteUnique(nums);

    // 使用索引遍历
    int i, j;
    cout << "Use index : " << endl;
    for (i = 0; i < res.size(); i++) {
        for (j = 0; j < res[0].size(); j++)
            cout << res[i][j] << " ";
        cout << endl;
    }

    // 使用迭代器遍历
    vector<int>::iterator it;
    vector<vector<int>>::iterator iter;
    vector<int> vec_tmp;

    cout << "Use iterator : " << endl;
    for (iter = res.begin(); iter != res.end(); iter++) {
        vec_tmp = *iter;
        for (it = vec_tmp.begin(); it != vec_tmp.end(); it++)
            cout << *it << " ";
        cout << endl;
    }

    return 0;
}

// 作者：liweiwei1419
// 链接：https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com