這篇文章,會帶大家快速回顧DFS+回溯法框架(還沒看過或想複習的可以點連結進去)。
用DFS+回溯法框架,解開 直線排列Permutations 的全系列題目。
幫助讀者鞏固DFS+回溯法框架這個重要的知識點。
白話的意思
# 列舉所有可能的情況,遞迴展開所有分支,把符合條件的分支納入解答。
def backtrack( parameter ):
# 終止條件
if stop condition:
save result if needed # 有需要的話,儲存當下的狀態作為結果
return
# 通則
for each possible next selection # 列出所有選擇
make a selection # 做出一個選擇
backtrack( updated patameter ) # 遞回展開下一層
undo selection # 撤銷選擇,回到原始狀態,準備做下一個選擇
return
輸入n個相異的元素,返回這n個元素的直線排列。
怎樣叫做直線排列?
其實就是每個元素輪流當排頭,並且依照同樣的規則遞迴展開。
1當排頭,剩下的元素遞迴展開做直線排列
2當排頭,剩下的元素遞迴展開做直線排列
...
n當排頭,剩下的元素遞迴展開做直線排列
什麼時候代表已經做完直線排列了?
當已經把所有元素都用完了,這時候這條分支的直線排列的展開已經完成,也結束了。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = []
def perm( start):
if start == len(nums):
result.append( nums.copy() )
return
for i in range(start, len(nums) ):
nums[start], nums[i] = nums[i], nums[start]
perm(start+1)
nums[start], nums[i] = nums[i], nums[start]
return
#========================
perm( start = 0 )
return result
輸入n個的元素,裡面可能有重複元素,返回這n個元素的直線排列。
通則和終止條件其實和前一題相同,這邊不重複敘述。
關鍵在於,如何保證不會重複製造相同的直線排列?
有一個直覺的想法,什麼資料結構可以記錄看過的資訊,用來去除重複?
就是Set集合,把看過的元素存到集合裡面,之後遇到同樣的元素就直接跳過即可。
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def perm(start):
## Base case aka stop condition
if start == len(nums):
result.append(nums.copy())
return
# Avoid repetition
seen = set()
## General cases
for i in range(start, len(nums)):
if nums[i] not in seen:
seen.add(nums[i])
nums[start], nums[i] = nums[i], nums[start]
perm(start+1 )
nums[start], nums[i] = nums[i], nums[start]
return
#-----------------------------------------
result = []
perm( start = 0)
return result
用字典來記錄每個元素的出現次數,字典的鍵值本身就具有排除重複的性質。
排列過程中,每排一次,當下數字的出現次數就減一,排到出現次數用完為止。
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def perm(start, cur):
## Base case aka stop condition
if start == len(nums):
result.append( cur )
return
## General cases
for number in occurrence:
# Avoid repetition
if occurrence[ number ] > 0:
occurrence[ number ] -= 1
perm(start+1, cur + [ number ] )
occurrence[ number ] += 1
return
#-----------------------------------------
occurrence = Counter(nums)
result = []
perm( start = 0, cur = [])
return result
好,今天一口氣介紹了最精華的部分,
通用的DFS+回溯法的枚舉框架,還有相關的直線排列衍伸變化題與演算法建造,
希望能幫助讀者、觀眾徹底理解它的原理,鞏固知識點。
並且能夠舉一反三,洞察其背後的本質和了解相關的應用領域!
感謝收看囉! 我們下篇文章再見~