LeetCode46-全排列(Golang)
LeetCode46-全排列
题意:
- 给定一个不重复的整数数组,要求返回该数组的全排列
思路一:
- 考虑使用深度优先搜索(DFS)。
- 对于每一位,枚举可能的结果。
- 避免重复的方法:用一个map保存前面位置的数据使用情况,如果用了就置为1,没用就置为0,只有当数值为0的时候,才能进行下一步枚举。
- 当枚举到终点的时候,将tmp存入ans答案数组中。
代码一(Golang):
func permute(nums []int) [][]int { mp:=make(map[int]int) tmp:=make([]int,0) ans:=make([][]int,0) var dfs func(now int) dfs=func(now int){ if now==len(nums){ ans=append(ans,append([]int(nil),tmp...)) return } for _,j:=range nums{ if mp[j]!=1{ mp[j]=1 tmp=append(tmp,j) dfs(now+1) tmp=tmp[:len(tmp)-1] mp[j]=0 } } } dfs(0) return ans}
思路二:
- 利用交换nums数组的元素,来实现枚举。
- 既可以避免重复,又减少了map的开销,代码还简洁。
代码二(Golang):
func permute(nums []int) [][]int { ans:=make([][]int,0) var dfs func(now int) dfs=func(now int){ if now==len(nums){ ans=append(ans,append([]int(nil),nums...)) return } for j:=now;j<len(nums);j++{ nums[j],nums[now]=nums[now],nums[j] dfs(now+1) nums[j],nums[now]=nums[now],nums[j] } } dfs(0) return ans}
抖机灵(C++):
利用cpp的库函数,next_permutation()可速过此题。
class Solution {public: vector<vector> permute(vector& nums) { vector<vector> ans; sort(nums.begin(),nums.end()); do{ ans.push_back(nums); }while(next_permutation(nums.begin(),nums.end())); return ans; }};