【Leetcode Permutation I & II】 Problem 1: Permutation I
Given a collection of numbers, return all possible permutations.
For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
Solve the problem on leetcode
分析：
这次，我们要生成完整的序列了，那么和上次的Subset有什么不同呢？
1. 添加进res的时间，上面题我们每添加一个数字到tmp里，就可以往res里面添加，而这次，我们要生成完整的序列，所以需要当tmp.size()＝＝序列长度的时候再往res里面添加
2. 每次不能从pos开始往数组尾巴扫了，因为我们要求的不是Subset而是完整序列，所以要从第一个数字开始往数组尾巴扫，问题又来了，我们怎么知道取没取过这个元素呢，那么我们就创建一个boolean[] visit 每此添加的时候给相对应位置置True，删去的时候置False
public class Solution {
public ArrayList> permute(int[] num) {
ArrayList> res = new ArrayList>();
ArrayList tmp = new ArrayList();
boolean[] visit = new boolean[num.length];
Arrays.sort(num);
dfs(res,tmp,num,visit);
return res;
}public void dfs(ArrayList> res, ArrayList tmp, int[] num, boolean[] visit){
if(tmp.size()==num.length) {
res.add(new ArrayList(tmp));
return;
}
for(int i=0;
i 几点注意的地方：
1. 每次判断是否visit的时候，这个if语句应该概括for循环里所有的动作，因为这么想，如果visit过，我们什么事也不做，直接跳过
2. 给res添加完之后，别忘了return
Problem 2 Permutation II
Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, [1,1,2] have the following unique permutations: [1,1,2], [1,2,1], and [2,1,1].
Solve the problem on leetcode
同样的思路，有重复的数字出现在集合里，而不能生成重复的序列
我们运用和Subset II 一样的思路，在remove后直接找到下一个和这次添加不重复的数字
public class Solution {
public ArrayList> permuteUnique(int[] num) {
ArrayList> res = new ArrayList>();
ArrayList tmp = new ArrayList();
boolean[] visit = new boolean[num.length];
Arrays.sort(num);
dfs(res,tmp,num,visit);
return res;
}public void dfs(ArrayList> res, ArrayList tmp, int[] num, boolean[] visit){
if(tmp.size()==num.length) {
res.add(new ArrayList(tmp));
return;
}
for(int i=0;
i 推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr（） （KMP超详细讲解，sunday解法等五种方法，java实现）
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)
- Python|Python Leetcode(665.非递减数列)