首页 > 代码库 > 【leetcode刷提笔记】Permutations
【leetcode刷提笔记】Permutations
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]
.
用深度搜索的方法搜索下面的一棵树(示例,非完整的树),每次搜索到叶子时经过的路径就是一个排列。
代码如下:
1 public class Solution { 2 public List<List<Integer>> permute(int[] num) { 3 List<List<Integer>> answerList = new ArrayList<List<Integer>>(); 4 ArrayList<Integer> currentList = new ArrayList<Integer>(); 5 boolean[] visited = new boolean[num.length]; 6 DS(answerList, visited, num, currentList); 7 return answerList; 8 } 9 10 public void DS(List<List<Integer>> answerList,boolean[] visited,int[] num,ArrayList<Integer> currentList){11 boolean find = true;12 for(int i = 0;i < num.length;i++){13 if(!visited[i]){14 currentList.add(num[i]);15 visited[i]= true;16 DS(answerList, visited, num, currentList);17 visited[i]= false;18 currentList.remove(currentList.size()-1);19 find = false;20 }21 }22 if(find){23 ArrayList <Integer> temp = new ArrayList<Integer>(currentList);24 answerList.add(temp);25 }26 }27 }
上述代码中DS函数为递归深度优先搜索函数,answerList记录最终得到的所有排列,visited数据记录在某个时间点对应节点是否在访问过的路径上,currentList为当前走过的路径。要注意的一点是找到一条新的路径后,要为这条路径申请内存空间存放它(代码第23行所示),否则currentList被修改的时候已经存放到answerList中的排列也会被修改。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。