> 文档中心 > LeetCode46-全排列(Golang)

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;    }};

K歌软件