继续打卡算法题,今天学习的是LeetCode第47题全排列II,这道题目是道中等题
。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些提升。
分析一波题目
哈哈,学习上一题46题全排列,本题只需要先排序,然后加一个去重复逻辑就可以了
比如下方的1223,第三个2和第二个2其实会搜索相同的数据组成排列,因此可以去重。
本题解题技巧
1、理解排列定义,排列是有顺序的。
2、每次都从第一个元素开始取数,但是一个数字在一个排列中只能出现一次
3、需要先排序,方便去除重复
编码解决
下面代码和组合总和II的代码非常相似。
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
//递归 回溯
Arrays.sort(nums);
boolean[] used = new boolean[nums.length];
backtracking(nums, new ArrayList<>(), 0, 0, used);
return result;
}
private List<List<Integer>> result = new ArrayList<>();
public void backtracking(int[] nums,List<Integer> path, int startIndex, int sum, boolean[] used) {
//结束条件
if( path.size() == nums.length) {
result.add(new ArrayList(path));
return;
}
//递归单层逻辑
for(int i=startIndex; i<nums.length; i++) {
//这里就是去重复 used[i-1] == false 新的排列刚开始,这个排列还没使用过,如果是used[i-1] == true代表还是在同一个排列里
if((i > 0 && nums[i] == nums[i-1] && used[i-1] == false )|| used[i] == true) {
continue;
}
path.add(nums[i]);
sum += nums[i];
used[i] = true;
//开始递归 startIndex传i,就是考虑每个数字都可以重复使用的情况
backtracking(nums, path, 0, sum, used);
//回溯
sum = sum - nums[i];
used[i] = false;
path.remove(path.size()-1);
}
}
}
总结
本题和46题解法几乎一致,排列问题通过回溯法解决,只加了一个减枝(去重复)。 需要注意减枝的情况是在同一层树上进行,同一个排列里不需要去重,也就不需要减枝。