?LeetCode刷題實戰(zhàn)46：全排列
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做?全排列，我們先來看題面：
https://leetcode-cn.com/problems/permutations/
Given a collection of?distinct?integers, return all possible permutations.
題意
樣例
輸入: [1,2,3]
輸出:
[
??[1,2,3],
??[1,3,2],
??[2,1,3],
??[2,3,1],
??[3,1,2],
??[3,2,1]
]
解題
回溯法
class?Solution:
????def?dfs(self,?nums,?n,?i,?cur,?ret,?flag):
????????if?i?==?n:
????????????ret.append(cur.copy())
????????????return
????????for?p?in?range(n):
????????????#?遍歷所有元素
????????????#?如果p元素已經(jīng)放置過了，跳過
????????????if?flag[p]:
????????????????continue
????????????#?當(dāng)前位置放置p
????????????cur.append(nums[p])
????????????#?flag[p]置為True
????????????flag[p]?=?True
????????????#?遞歸
????????????self.dfs(nums,?n,?i+1,?cur,?ret,?flag)
????????????#?回溯
????????????cur.pop()
????????????flag[p]?=?False
????????
????def?permute(self,?nums:?List[int])?->?List[List[int]]:
????????ret?=?[]
????????n?=?len(nums)
????????#?記錄元素i有沒有放置過
????????flag?=?[False?for?_?in?range(n)]
????????self.dfs(nums,?n,?0,?[],?ret,?flag)
????????return?ret
其他方法
class?Solution:
????def?get_next(self,?nums:?List[int]):
????????"""
????????Do?not?return?anything,?modify?nums?in-place?instead.
????????"""
????????#?長度
????????n?=?len(nums)
????????#?記錄圖中i-1的位置
????????pos?=?n?-?1
????????for?i?in?range(n-1,?0,?-1):
????????????#?如果降序破壞，說明找到了i
????????????if?nums[i]?>?nums[i-1]:
????????????????pos?=?i-1
????????????????break
????????????????
????????for?i?in?range(n-1,?pos,?-1):
????????????#?從最后開始找大于pos位置的
????????????if?nums[i]?>?nums[pos]:
????????????????#?先交換元素，在進行翻轉(zhuǎn)
????????????????nums[i],?nums[pos]?=?nums[pos],?nums[i]
????????????????#?翻轉(zhuǎn)[pos+1,?n]區(qū)間
????????????????nums[pos+1:]?=?nums[n:pos:-1]
????????????????return?False
????????return?True
????????
????????
????def?permute(self,?nums:?List[int])?->?List[List[int]]:
????????ret?=?[]
????????#?從小到大排序，獲得最小排列
????????nums?=?sorted(nums)
????????ret.append(nums.copy())
????????#?如果還有下一個排列則繼續(xù)調(diào)用
????????while?not?self.get_next(nums):
????????????#?要.copy()是因為Python中存儲的引用，如果不加copy
????????????#?會導(dǎo)致當(dāng)nums發(fā)生變化之后，ret中存儲的數(shù)據(jù)也會變化
????????????ret.append(nums.copy())
????????return?ret
上期推文：
評論
圖片
表情