行业门户网站建设方案,设计了网站,免费看行情的软件大全免费,一般用什么做网站首页如果每个数字任意取的话。就不需要加book标志位
没有重复项数字的全排列_牛客题霸_牛客网 描述 给出一组数字#xff0c;返回该组数字的所有排列 例如#xff1a; [1,2,3]的所有排列如下 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]. #xff08;以数字在数组中的位… 如果每个数字任意取的话。就不需要加book标志位
没有重复项数字的全排列_牛客题霸_牛客网 描述 给出一组数字返回该组数字的所有排列 例如 [1,2,3]的所有排列如下 [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1]. 以数字在数组中的位置靠前为优先级按字典序排列输出。 数据范围数字个数 0n≤60n≤6 要求空间复杂度 O(n!)O(n!) 时间复杂度 O(n!O(n! 示例1 输入[1,2,3]返回值[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 普通的dfs模板套用加上一个book标志位表示每一位元素是否被用过
class Solution {
public:vectorvectorint res;vectorint temp;void dfs(vectorint num, int index, vectorbool book){if(index num.size()){res.push_back(temp);return;}for(int i 0; i num.size(); i){if(book[i]false){book[i] true; // 感觉像最近写的互斥锁哈哈哈哈temp.push_back(num[i]);dfs(num, index1, book);temp.pop_back();book[i] false;}}}vectorvectorint permute(vectorint num) {vectorbool book (num.size(), false); // 设置一个book标志位标志每一个数是否被用过dfs(num, 0, book);return res;}
}; 有重复项数字的全排列_牛客题霸_牛客网 描述 给出一组可能包含重复项的数字返回该组数字的所有排列。结果以字典序升序排列。 数据范围 0n≤80n≤8 数组中的值满足 −1≤val≤5−1≤val≤5 要求空间复杂度 O(n!)O(n!)时间复杂度 O(n!)O(n!) 示例1 输入[1,1,2]返回值[[1,1,2],[1,2,1],[2,1,1]] 示例2 输入[0,1]返回值[[0,1],[1,0]] class Solution {
public:vectorvectorint res;setvectorint ress; // 使用set来接收vectorint temp;void dfs(vectorint num, vectorbool book, int index){if(index num.size()){ress.insert(temp);return;}for(int i 0; i num.size(); i){if(book[i]){book[i] false;temp.push_back(num[i]);dfs(num, book, index1);temp.pop_back();book[i] true;}}}vectorvectorint permuteUnique(vectorint num) {vectorbool book (num.size(), true);dfs(num, book, 0);for(auto e : ress) // 最终将set转化为vector{res.push_back(e);}return res;}
}; 知识点递归与回溯
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程最重要的就是查看能不能讲原本的问题分解为更小的子问题这是使用递归的关键。
如果是线型递归子问题直接回到父问题不需要回溯但是如果是树型递归父问题有很多分支我需要从子问题回到父问题进入另一个子问题。因此回溯是指在递归过程中从某一分支的子问题回到父问题进入父问题的另一子问题分支因为有时候进入第一个子问题的时候修改过一些变量因此回溯的时候会要求改回父问题时的样子才能进入第二子问题分支。
思路
这道题类似没有重复项数字的全排列但是因为交换位置可能会出现相同数字交换的情况出现的结果需要去重因此不便于使用交换位置的方法。
我们就使用临时数组去组装一个排列的情况每当我们选取一个数组元素以后就确定了其位置相当于对数组中剩下的元素进行全排列添加在该元素后面给剩余部分进行全排列就是一个子问题因此可以使用递归。
终止条件 临时数组中选取了n个元素已经形成了一种排列情况了可以将其加入输出数组中。返回值 每一层给上一层返回的就是本层级在临时数组中添加的元素递归到末尾的时候就能添加全部元素。本级任务 每一级都需要选择一个不重复元素加入到临时数组末尾遍历数组选择。
回溯的思想也与没有重复项数字的全排列类似对于数组[1,2,2,3]如果事先在临时数组中加入了1后续子问题只能是[2,2,3]的全排列接在1后面对于2开头的分支达不到因此也需要回溯将临时数组刚刚加入的数字pop掉同时vis修改为没有加入这样才能正常进入别的分支。 1 2 3 4 5 6 7 8 //标记为使用过 vis[i] true; //加入数组 temp.add(num[i]); recursion(res, num, temp, vis); //回溯 vis[i] false; temp.remove(temp.size() - 1);
