[Swift]LeetCode46.全排列|Permutations

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9907570.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

12ms

 1 class Solution {
 2   func permute (_ arr:[Int]) -> [[Int]] {
 3     
 4     var array = arr
 5     var result = [[Int]]()
 6     helper(&array,0,&result)
 7     return result
 8 }
 9 
10 func helper (_ arr: inout [Int], _ begin:Int, _ results: inout [[Int]]){
11     
12     if begin >= arr.count{
13         results.append(arr)
14         return
15     } else {
16         for i in begin..<arr.count{
17             // choose
18             arr.swapAt(begin, i)
19             // explore
20             helper(&arr, begin + 1, &results)
21             // unchoose
22             arr.swapAt(begin, i)
23         }
24     }
25   }
26 ｝

16ms

 1 class Solution {
 2     func permute(_ nums: [Int]) -> [[Int]] {
 3         
 4         var result = [[Int]]()
 5         var temp = [Int]()
 6         
 7         var isVisited : [Bool] = Array(repeating: false, count: nums.count)
 8         backTracking(nums, &result, &temp, &isVisited)
 9         return result
10         
11     }
12     
13     func backTracking(_ nums: [Int], _ result: inout [[Int]], _ temp: inout [Int], _ isVisited: inout [Bool]) {
14         if temp.count == nums.count {
15             result.append(temp)
16             return
17         }
18         for i in 0 ..< nums.count where !isVisited[i] {
19             temp.append(nums[i])
20             isVisited[i] = true
21             backTracking(nums, &result, &temp, &isVisited)
22             isVisited[i] = false
23             temp.removeLast()
24         }
25     }
26 }

24ms

 1 class Solution {
 2     func permute(_ nums: [Int]) -> [[Int]] {
 3     var result = [[Int]]()
 4     var nums = nums
 5     
 6     func permute(nums: inout [Int], start: Int, end: Int) {
 7         if start == end {
 8             result.append(nums)
 9         } else {
10             for i in start...end {
11                 nums.swapAt(i, start)
12                 permute(nums: &nums, start: start + 1, end: end)
13                 nums.swapAt(i, start)
14             }
15         }
16     }
17     permute(nums: &nums, start: 0, end: nums.count - 1)
18     return result
19     }
20 }

36ms

 1 class Solution {
 2     func permute(_ nums: [Int]) -> [[Int]] {
 3         var result : [[Int]] = []
 4         permuteNext(from: nums, to: [], result: &result)
 5         return result
 6     }
 7     func permuteNext(from : [Int] , to : [Int]  , result : inout [[Int]]) {
 8         if from.count == 0 {
 9             result.append(to)
10             return
11         }
12         
13         for idx in 0..<from.count {
14             var newfrom = from
15             newfrom.remove(at: idx)
16             permuteNext(from: newfrom, to: to + [from[idx]], result: &result)
17         }
18     }
19 }

36ms

 1 class Solution {
 2     var collectList: [[Int]] = []
 3       func permute(_ nums: [Int]) -> [[Int]] {
 4         
 5         if(nums.count == 0) {
 6             return collectList
 7         }
 8         
 9         permuteDFS(nums, start: 0, tempList: [Int]())
10         
11         return collectList
12     }
13     
14      func permuteDFS(_ nums: [Int], start: Int, tempList: [Int]) {
15         
16         var temp = tempList
17         
18         if(temp.count == nums.count) {
19             
20             collectList.append(temp)
21             
22         }else {
23             
24             for i in 0 ..< nums.count {
25                 
26                 if( temp.contains(nums[i])) {
27                     continue
28                 }
29                 
30                 temp.append(nums[i])
31                 
32                 permuteDFS(nums, start: (i + 1), tempList: temp)
33                 
34                 temp.removeLast()
35             }
36             
37         }
38         
39     }
40     
41 }

60ms

 1 class Solution {
 2     func permute(_ nums: [Int]) -> [[Int]] {
 3        if nums.isEmpty {
 4             return[[]]
 5         } else if nums.count == 1 {
 6             return [nums]
 7         } else {
 8             var result = [[Int]]()
 9             for i in 0..<nums.count {
10                 var nums = nums
11                 let num = nums.remove(at: i)
12                 for j in permute(nums) {
13                     result.append([num] + j)
14                 }
15             }
16             return result
17         }
18     }
19 }

80ms

 1 class Solution {
 2     func permute(_ nums: [Int]) -> [[Int]] {
 3         var result: [[Int]] = []
 4         permute(nums, [], &result)
 5         return result
 6     }
 7     
 8     func permute(_ nums: [Int], _ nums2: [Int], _ result: inout [[Int]]) {
 9         guard nums2.count != nums.count else {
10             result.append(nums2)
11             return
12         }
13         
14         nums.filter { !nums2.contains($0) }.forEach { (num) in
15             var nums4 = nums2
16             nums4.append(num)
17             permute(nums, nums4, &result)
18         }
19     }
20 }