曲靖网站建设,南宁模板网页制作,重庆做的好的房产网站,百度seo如何优化关键词1.问题描述 给定一个不含重复数字的数组 nums #xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案 示例1 输入#xff1a;nums [1,2,3] 输出#xff1a;[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例2 输入#xff1a;nums [0,1] 输出#xf…1.问题描述 给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案 示例1 输入nums [1,2,3] 输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例2 输入nums [0,1] 输出[[0,1],[1,0]] 示例3 输入nums [1]输出[[1]] 提示
1 nums.length 6-10 nums[i] 10nums 中的所有整数 互不相同 难度等级 中等 题目链接 全排列
2.解题思路 这道题要求我们返回所有可能的全排列每一个数都有可能在每一个位置出现这里我们要用到回溯的思想。 在解题之前我们要先来定义一些变量我们的一个排列可以用一个List集合来表示我们可以用一个辅助的List集合来寻找所有的全排列并定义一个用来存储最终所有全排列的List数组(data)接着我们还需要一个标识数组来标识nums中的哪些数已经在当前排列中出现过了防止出现同一个nums[i]在一个排列中排了两次。 ListListInteger data new ArrayList();boolean[] used new boolean[nums.length]; 这道题我们可以编写一个递归回溯的方法来找到所有的排列。 递归的结束条件是当辅助List的个数等于nums数组的个数时说明所有的数都已经拿出来进行排列了已经得到一个新的排列这时创建一个新的List将辅助数组的元素存入新的List中再将List存入最终用来存储所有全排列的List集合中然后直接返回即可。 //如果list的大小 nums的个数,说明得到一个排列if(list.size() nums.length){//添加新的排列data.add(new ArrayList(list));return;} 正常的递归逻辑也很简单用一个for循环对nums数组进行遍历先判断当前的数是否已经在辅助List排列了如果已经在List中排列则跳过这一个数。 //遍历nums数组,将还没排列的数字取出来进行排序for(int i 0;i nums.length;i){//已经被用过的数直接跳过if(used[i] true){continue;}......} 如果还没有在参与排列则将标记改为true并添加到辅助List中参与排列接着递归调用当前方法继续进行查找。找到包含当前子排列的所有排列之后我们还需要对当前的排列进行回溯将标记重新改回false并将当前对应的这个数从辅助list中取出防止对后面的排列造成影响。 //遍历nums数组,将还没排列的数字取出来进行排序for(int i 0;i nums.length;i){......//标记为已使用used[i] true;//添加到当前的排列中list.add(nums[i]);//递归backtrack(data,list,nums,used);//回溯list.remove(list.size()-1);used[i] false;} 当递归方法完全执行完成之后直接将用来存储全排列的List集合(data)返回即可。 backtrack(data,new ArrayListInteger(),nums,used);return data;
3.代码展示
class Solution {public ListListInteger permute(int[] nums) {ListListInteger data new ArrayList();boolean[] used new boolean[nums.length];backtrack(data,new ArrayListInteger(),nums,used);return data;}public void backtrack(ListListInteger data,ListInteger list,int[] nums,boolean[] used){//如果list的大小 nums的个数,说明得到一个排列if(list.size() nums.length){//添加新的排列data.add(new ArrayList(list));return;}//遍历nums数组,将还没排列的数字取出来进行排序for(int i 0;i nums.length;i){//已经被用过的数直接跳过if(used[i] true){continue;}//标记为已使用used[i] true;//添加到当前的排列中list.add(nums[i]);//递归backtrack(data,list,nums,used);//回溯list.remove(list.size()-1);used[i] false;}}
}
4.总结 这道题没什么太大的难度采用回溯递归的方法穷尽所有的排列可能让每一个数在每一个位置都出现一次。好了这道题没啥好啰嗦的祝大家刷题愉快早日上岸
