首页 > 代码库 > LeetCode: Permutations 解题报告
LeetCode: Permutations 解题报告
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].
SOLUTION 1:
经典的递归回溯题目，一次ACCEPT. 请也参考上一个题目LeetCode: Combinations 解题报告.
1 public class Solution { 2 public List<List<Integer>> permute(int[] num) { 3 List<List<Integer>> ret = new ArrayList<List<Integer>>(); 4 if (num == null || num.length == 0) { 5 return ret; 6 } 7 8 dfs(num, new ArrayList<Integer>(), ret); 9 return ret;10 }11 12 public void dfs(int[] num, List<Integer> path, List<List<Integer>> ret) {13 int len = num.length;14 if (path.size() == len) {15 ret.add(new ArrayList<Integer>(path));16 return;17 }18 19 for (int i = 0; i < len; i++) {20 if (path.contains(num[i])) {21 continue;22 }23 24 path.add(num[i]);25 dfs(num, path, ret);26 path.remove(path.size() - 1);27 }28 }29 }
SOLUTION 2:
可能有的同学觉得为什么path.contains不用hashmap来代替哩？所以主页君写了一个带hashmap的版本。结论是，在这个set规模小的时候，hashmap的性能还不
如arraylist。
原因可能在于，hashmap申请的不是一个连续的空间，而arraylist比较小的话，直接在连续内存中操作，速度会比较快。
以下是此程序的运行结果，hashmap的版本速度要慢一倍：
Test size:9
Computing time with HASHMAP: 629.0 millisec.
Test size:9
Computing time with list: 310.0 millisec.
1 package Algorithms.permutation; 2 3 import java.util.ArrayList; 4 import java.util.HashSet; 5 import java.util.LinkedHashMap; 6 7 public class Permutation { 8 public static void main(String[] strs) { 9 int[] num = {1, 2, 3, 4, 5, 6, 7, 8, 9};10 System.out.printf("Test size:%d \n", num.length);11 12 Stopwatch timer1 = new Stopwatch();13 14 permute(num);15 System.out16 .println("Computing time with HASHMAP: "17 + timer1.elapsedTime() + " millisec.");18 19 System.out.printf("Test size:%d \n", num.length);20 21 Stopwatch timer2 = new Stopwatch();22 23 permute2(num);24 System.out25 .println("Computing time with list: "26 + timer2.elapsedTime() + " millisec.");27 }28 29 public static ArrayList<ArrayList<Integer>> permute(int[] num) {30 ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();31 if (num == null) {32 return ret;33 }34 35 permuteHelp(num, ret, new LinkedHashMap<Integer, Integer>());36 return ret;37 }38 39 public static void permuteHelp(int[] num, ArrayList<ArrayList<Integer>> ret, LinkedHashMap<Integer, Integer> set) {40 if (set.size() == num.length) {41 42 ArrayList<Integer> list = new ArrayList<Integer>();43 for (Integer i: set.keySet()){44 list.add(i);45 }46 ret.add(list);47 return;48 }49 50 int len = num.length;51 for (int i = 0; i < len; i++) {52 if (set.containsKey(num[i])) {53 continue;54 }55 56 //path.add(num[i]);57 set.put(num[i], 0);58 permuteHelp(num, ret, set);59 //path.remove(path.size() - 1);60 set.remove(num[i]);61 }62 }63 64 public static ArrayList<ArrayList<Integer>> permute2(int[] num) {65 ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();66 if (num == null) {67 return ret;68 }69 70 ArrayList<Integer> path = new ArrayList<Integer>();71 permuteHelp2(num, path, ret);72 return ret;73 }74 75 public static void permuteHelp2(int[] num, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> ret) {76 if (path.size() == num.length) {77 ret.add(new ArrayList<Integer>(path));78 return;79 }80 81 int len = num.length;82 for (int i = 0; i < len; i++) {83 if (path.contains(num[i])) {84 continue;85 }86 87 path.add(num[i]);88 permuteHelp2(num, path, ret);89 path.remove(path.size() - 1);90 }91 }92 }
GITHUB:
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/dfs/Permute.java
LeetCode: Permutations 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。