乐趣区

关于leetcode算法:全排列问题

jiezi

全排列有两种枚举程序：
（1）按程序枚举每个地位填哪个数
（2）按程序枚举每个数填哪个地位

两种程序都能解，但如果要保障字典序，则须要应用（1）按程序枚举每个地位填哪个数。因为优先思考将小的数放到后面地位。

leetcode 46. 全排列
给定一个不含反复数字的数组 nums，返回其所有可能的全排列。你能够按任意程序返回答案。

示例 1：
输出：nums = [1,2,3]
输入：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提醒：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不雷同

计划：采纳（1）按程序枚举每个地位填哪个数

class Solution {List<Integer> path = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();;
    public List<List<Integer>> permute(int[] nums) {dfs(nums, 0, 0);
        return ans;
    }

    // u: 坑位，按程序枚举每个坑位填哪个数
    public void dfs(int[] nums, int u, int state) {if (u == nums.length) {ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) { // 枚举每个数
            if ((state >> i & 1) == 0) {path.add(nums[i]);
                dfs(nums, u + 1, state + (1 << i));
                path.remove(path.size() - 1);
            }
        }
    }
}

leetcode 47. 全排列 II

给定一个可蕴含反复数字的序列 nums，按任意程序 返回所有不反复的全排列。

示例 1：
输出：nums = [1,1,2]
输入：
[[1,1,2],
[1,2,1],
[2,1,1]]

提醒：
1 <= nums.length <= 8
-10 <= nums[i] <= 10

办法 1：[顺次枚举每个数，看能填到哪些坑位上]

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> permutation(vector<int>& nums) {sort(nums.begin(), nums.end());
        path.resize(nums.size());
        dfs(nums, 0, 0, 0);
        return ans;
    }

 // u: 枚举到第几个数 start: 上一个数的坑位在哪 state: 标记坑位是否被占
    void dfs(vector<int> &nums, int u, int start, int state) {if (u == nums.size()) {ans.push_back(path);
            return;
        }
        if (!u || nums[u] != nums[u - 1]) start = 0; // 下一个反复元素只能放在前面，有序性。其余都从第 0 个坑位开始看是否填

        for (int i = start; i < nums.size(); i ++) // 枚举坑位，看是否填上 nums[u]
            if (!(state >> i & 1)) {path[i] = nums[u];
                dfs(nums, u + 1, i + 1, state + (1 << i));
            }
    }
};

此处 i: 坑位，u: 第几个数。此处和上一题不一样！上一题是顺次枚举每个坑位看能填哪些数，而此题是顺次枚举每个数，看能填到哪些坑位上。（因为此题顺次枚举每个数能够判断反复数字，反复的只能放到上一个反复填的坑位之后）
链接：https://www.acwing.com/activi…

解法 2：【第 u 坑位枚举每个数是否填，即按程序枚举每个地位填哪个数】

vector<vector<int>> ans;
vector<int> path;
vector<bool> st;

void dfs(vector<int>& nums, int u) {if (u == nums.size()) {ans.push_back(path);
        return;
    }

    for (int i = 0; i < nums.size(); i++) // 顺次枚举每个数，所以能够规定雷同数的程序
        if (!st[i]) {if (i && (nums[i] == nums[i - 1]) && !st[i - 1]) // 用第一次没有用过的雷同数，不能跳。则程序就定下来了
                continue;
            st[i] = true;
            path[u] = nums[i]; // 因为顺次枚举每个地位填哪个数，故 u 递增也能够应用 path.push_back(nums[i]);
            dfs(nums, u + 1);
            st[i] = false;     // 此时就须要 path.pop_back();}
}

vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());
    st = vector<bool>(nums.size(), false);
    path = vector<int>(nums.size());
    dfs(nums, 0);
    return ans;
}

又回来看一遍视频，讲的切实太好了，有两句最外围的内容，我加上本人的了解整顿写了一下。
A 1 分 24 秒到 2 分 00 秒：讲了为什么要先排序 因为后果是要去重的，而后果都是列表模式的，那列表怎么判重呢？就是排序之后一个一个的比拟，所以那还不如先排序之后再计算，再计算的过程中判断是否有反复，省得对每个后果再做一次排序去重操作。
B 2 分 25 秒到 4 分 10 秒：讲了怎么判断以后分支是否是反复的分支。因为之前曾经排好序了，所以以后元素 nums[i] 如果和前一个元素雷同，即 nums[i] == nums[i-1]就阐明该分支有可能是反复的。然而这个相等条件有两种可能一种是，1 1‘2，也就是抉择完 1 之后再抉择第二个 1，两个元素尽管反复，然而第二个元素是前一个元素的下一层，这时是没有问题的。另一种是之前的同层分支曾经有 1 1‘2 了，这次的抉择是 1‘1 2。两个元素反复，且重的是同层门路。那就阐明是反复分支。
具体辨别的方法是 nums[i-1] 的 used 状态是被抉择的，那么阐明以后的 nums[i] 是 nums[i-1]的下一层门路。否则如果 nums[i-1] 的状态是没被抉择的，那么阐明以后的 nums[i] 是 nums[i-1] 同层门路。

有内鬼终止 AC
2021-10-01
@GB2312 说的太好了，补充一下
为什么 ” nums[i-1] 的 used 状态是被抉择的，那么阐明以后的 nums[i] 是 nums[i-1]的下一层门路。”
起因：因为往上层递归的话，始终再往上层走，dfs 还未 return，也就是说 used 还没有被回溯为未抉择状态，所以同一条分支上，nums[i-1] 的 used 状态肯定是被抉择的。
为什么 ” 如果 nums[i-1] 的状态是没被抉择的，那么阐明以后的 nums[i] 是 nums[i-1] 同层门路。”
起因：递归到叶节点，开始往上回溯了，回溯到某一层时把 used[i-1]回溯为未抉择状态，而后 for 循环 i ++ 横向挪动，天然这时再判断 used[i-1]就肯定是未抉择状态。

因为咱们是枚举每个坑位填哪个数，所以雷同数的枚举到的程序必定是顺次的，不能也不会跳过！

PS: 两种解法中排序的目标不是让数组有序，而只是让雷同的数放在一起。

退出移动版