网站建设后台管理怎么管理,dede怎么做网站,做网站时背景音乐,大型网站集群怎么做全排列 - 三种形式
思路 - 回溯
「路径」#xff0c;记录已经做过的选择「选择列表- 多叉树」#xff0c;表示当前可以做出的选择#xff0c;在前序和后序位置操作。 前序位置#xff0c;做选择进入下一层决策树后序位置#xff0c;撤销选择 「结束条件」 遍历到树的底层…全排列 - 三种形式
思路 - 回溯
「路径」记录已经做过的选择「选择列表- 多叉树」表示当前可以做出的选择在前序和后序位置操作。 前序位置做选择进入下一层决策树后序位置撤销选择 「结束条件」 遍历到树的底层叶子节点
46. 全排列 - 元素无重不可复选
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
题解
public ListListInteger res new LinkedList(); // 记录结果
public LinkedListInteger track new LinkedList(); // 记录路径
public ListListInteger permute(int[] nums) {backtrack(nums);return res;
}
// 回溯
public void backtrack(int[] nums) {// 结束条件base case到达叶子节点if (track.size() nums.length) {// 找出一个全排列退出。不能直接add(track)track引用的对象一直在变化最后track为空导致res添加的所有track也全都为空。res.add(new LinkedList(track));return;}// 选择列表for (int i 0; i nums.length; i) {// 已存在的路径排除,避免重复使用if (track.contains(nums[i])) continue;track.add(nums[i]); // 前序位置做选择backtrack(nums); // 进入下一层决策树track.removeLast(); // 后序位置撤销选择}
}避免重复选择
使用集合的 contains() 方法判断使用 used数组 标记还可以被选择的元素
变种求元素个数为 k 的排列
// 求元素个数为 k 的排列
public void backtrack(int[] nums, int k) {if (track.size() k) {res.add(new LinkedList(track));return;}for (int i 0; i nums.length; i) {if (track.contains(nums[i])) continue;track.add(nums[i]);backtrack(nums, k);track.removeLast();}
}47. 全排列 II - 元素可重不可复选
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。
题解
方法一保证相同元素在排列中的相对位置保持不变
public ListListInteger res new LinkedList();
public LinkedListInteger track new LinkedList();
public boolean[] used;
public ListListInteger permuteUnique(int[] nums) {// 先排序让相同元素靠在一起Arrays.sort(nums);used new boolean[nums.length];backtrack(nums);return res;
}
// 剪枝相同元素在排列中的相对位置保持不变
public void backtrack(int[] nums) {if (track.size() nums.length) {res.add(new LinkedList(track));return;}for (int i 0; i nums.length; i) {if (used[i]) continue; // 剪枝已访问过跳出if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue; // 剪枝没有访问过的树枝若值相同跳过相对位置改变导致重复啦,要跳过track.add(nums[i]);used[i] true;backtrack(nums);track.removeLast();used[i] false;}
}方法二记录前一条树枝的值相同的只遍历第一个树枝其它跳过
public void backtrack2(int[] nums) {if (track.size() nums.length) {res.add(new LinkedList(track));return;}// 记录前一条树枝的值,初始化为特殊值int prevNum -110;for (int i 0; i nums.length; i) {if (used[i]) continue; // 剪枝已访问过跳出if (prevNum nums[i]) continue; // 剪枝,相同则跳过,去重复track.add(nums[i]);used[i] true;prevNum nums[i]; // 记录这条树枝上的值backtrack2(nums);track.removeLast();used[i] false;}
}方法三set去重
// 方法三 找出全排列 然后通过set去重效率低
// public SetListInteger set new HashSet();全排列 III - 元素无重可复选
允许重复使用元素去除剪枝逻辑即可。
public ListListInteger res new LinkedList(); // 结果
public LinkedListInteger track new LinkedList(); // list记录路径
public ListListInteger permute(int[] nums) {backtrack(nums);return res;
}
/*** 回溯*/
public void backtrack(int[] nums) {// base case到达叶子节点if (track.size() nums.length) {// 收集叶子节点上的值res.add(new LinkedList(track));return;}for (int i 0; i nums.length; i) {track.add(nums[i]); // 做选择backtrack(nums); // 进入下一层决策树track.removeLast(); // 撤销选择}
}
