leetcode遡及アルゴリズムの概要(python)
13783 ワード
使用するシーンを遡及:
遡及法は、複数のステップからなる問題に非常に適しており、各ステップには複数のオプションがあり、あるステップで1つのオプションを選択すると、次のステップに進み、新しいオプションに直面します.私たちはこのように最後の状態に達するまで選択を繰り返しています.
一般的に木を描いて示す
遡及する問題の手順:【木の深さ遍歴過程】図を描き、要素が重複しているかどうかを観察し、重複している場合は枝を切る必要があり、 をどのように切るかを考える.遡及3要素:経路、選択リスト、終了条件 このコードテンプレートに従って、コードを書き出します.
経験:選択後に選択を取り消す必要があり、backtrack(path+[num[i],num[:i]+num[i+1:])のような関数リストに選択を書くと、pathのように外に書く必要はありません.append(nums[i])では、前の操作を取り消す必要があります.ツリーにとって、1つのノード1つのノードの処理で、私は通常1つ目を使って、選択したパスを関数の中に置くことに慣れています.2つ目を選択した場合は、取り消し操作が必要です.
剣指offer面接問題の二叉木の経路と行列の経路を真剣に考える必要がある.
【https://mp.weixin.qq.com/s__biz=MzAxODQxMDM0Mw==&mid=2247484709&idx=1&sn=1c24a5c41a5a255000532e83f38f2ce4&chksm=9bd7fb2daca0723be888b30345e2c5e64649fc31a00b05c27a0843f349e2dd9363338d0dac61&scene=21#wechat_redirect】
アルゴリズムフレームワーク
くだらないことは言わないで、直接アルゴリズムの枠組みを遡ります.遡及問題を解決することは,実際には決定ツリーの遍歴過程である.3つの問題を考えるだけです
1、経路:つまりすでに選択されている.
2、選択リスト:つまり、現在できる選択です.
3、終了条件:つまり決定木の底に到達し、選択できない条件.
コードの面では、遡及アルゴリズムのフレームワーク:
その核心はforループの中の再帰であり,再帰呼び出しの前に「選択をする」こと,再帰呼び出しの後に「選択を取り消す」こと,特に簡単である.
枝切り方法:の全配列の中の枝は、後の要素が最初の要素と同じ場合を考慮するだけで、continueになります.ただし、同層の違いが上下層と同じであることを保証する(i>start)に注意し、leetcode 40を参照する.まとめ は全配列問題に対してmarkを用いるのに適しておらず、markはマトリクス内の要素が一度だけアクセスする場合、例えばアクセスマトリクス内の座標やアルファベット問題に用いる.
注意事項
1.選択リストループ内で判断が必要な場合はcontinue(このステップがだめで次のステップを行う機会があることを示す)、選択リストループ外で判断した場合はreturnで中断する
2.まず現在の経路を判断し、次の選択リストに進む.これにより、すべての状態が判断されることが保証されます.
(剣指offer 12,13有感而発)
問題の順序を決める.
Leetcode:46,47,39,40,78,90,22
剣指offer:12,13
【leetcode 46】全配列
【leetcode 46】全配列2
【leetcode 39】コンビネーション
【leetcode 40】コンビネーション2
この問題は2回目にやった時も問題が発生した.問題は枝を切る条件にある
この大物を参考にして、とてもよく書けました.https://leetcode-cn.com/problems/combination-sum-ii/solution/xiang-xi-jiang-jie-ru-he-bi-mian-zhong-fu-by-allen/
前の問題の回朔と全く同じで、悪いのはただ1つのどのように繰り返しの問題を避けるかだけです
これは繰り返しを避けることが大切です.この方法の最も重要な役割は,同じ階層に同じ要素が現れないようにすることである.しかし、異なるレベル間の重複を許可します.
1/2このような状況は発生しない/5例2 1/2このような状況は確かに許可されている/2なぜあるのかこの不思議な効果は?まずcur-1==curは、現在の要素が以前の要素と同じか否かを判定するための文である.この文は例1を切り落とすことができる.しかし問題が来て、現在の要素と前の要素をすべて切り落とすと、例2の状況も消えてしまいます.2番目の2が現れたとき、彼は前の2と同じだったからだ.
では、例2をどのように残すのでしょうか.ではcur>beginを用いてこのような状況を回避すると、例1の2つの2つは同じレベルにあり、例2の2つの2つの2は異なるレベルにあることがわかります.1つのforループでは、遍歴されたすべての数が1つのレベルに属します.1つのレベルで、2が1つしか現れなければならない場合は、最初に繰り返される2を見逃しますが、後に現れる2を見逃しません.最初に現れた2の特徴はcur==beginである.2番目に現れた2つの特徴はcur>beginである.
【leetcode 78】サブセット
構想:図を描いた後、すべてのノードが要求に合っていることが分かった.だからそれぞれの葉にresultを加えます
【leetcode 90】サブセット2
また枝切りの問題にぶつかった.絵を描くと、1、2、2のときは2つの2が最初の2を残しておけばいいことがわかります.
[leetcode 79]単語検索——[剣指offer]12題
backtrackに戻り値があるのはこれだけのようで、やはり難しいと思いますハハハハ.
markはマトリクス要素をマークするために使用され、0はアクセスしていないことを示し、1はアクセスしたことを示す.
考え方:の1つはbacktrack(i,j,word)が現在のi,jを判断し、下に進むことができれば次のステップ、できなければ次のステップ(markで表す) .は、i,jに対する次のcur_である.i, cur_jは判断を行い、下に進めば次のステップ、できなければ次のステップ(markで示す) を退ける.
注意: backtrackでは,ループ選択リストではcontinueのみ,ループリスト外ではreturnのみを用いる. この問題に対して、wordを見つけて、1つを捨てて、再帰的な戻り値の正しい応用に注意します.
考え方1
考え方2:
[剣指offer]13題ロボットの動き範囲
考え方1:backtrackは戻り値がなければ処理しなくてもよい.
考え方2:
初期ijの処理に注意してください.
まとめ:いくつかの小さな細部があり、出会った穴を記録します.1、count=0はselfと書かなければならない.count=0ですが、マトリクスリストは使用しません.2、バックトラックに戻り値がある場合、再帰判定時に3、mapを適用する対象は正の整数でなければならず、負の数ではないので、i,jがアウトであるか否かを判断してからi_を得るlist, j_list.
[leetcode 22]かっこの生成
構想:絵を描いて、経路と中断条件をよく考えます.
遡及法は、複数のステップからなる問題に非常に適しており、各ステップには複数のオプションがあり、あるステップで1つのオプションを選択すると、次のステップに進み、新しいオプションに直面します.私たちはこのように最後の状態に達するまで選択を繰り返しています.
一般的に木を描いて示す
遡及する問題の手順:【木の深さ遍歴過程】
経験:選択後に選択を取り消す必要があり、backtrack(path+[num[i],num[:i]+num[i+1:])のような関数リストに選択を書くと、pathのように外に書く必要はありません.append(nums[i])では、前の操作を取り消す必要があります.ツリーにとって、1つのノード1つのノードの処理で、私は通常1つ目を使って、選択したパスを関数の中に置くことに慣れています.2つ目を選択した場合は、取り消し操作が必要です.
剣指offer面接問題の二叉木の経路と行列の経路を真剣に考える必要がある.
【https://mp.weixin.qq.com/s__biz=MzAxODQxMDM0Mw==&mid=2247484709&idx=1&sn=1c24a5c41a5a255000532e83f38f2ce4&chksm=9bd7fb2daca0723be888b30345e2c5e64649fc31a00b05c27a0843f349e2dd9363338d0dac61&scene=21#wechat_redirect】
アルゴリズムフレームワーク
くだらないことは言わないで、直接アルゴリズムの枠組みを遡ります.遡及問題を解決することは,実際には決定ツリーの遍歴過程である.3つの問題を考えるだけです
1、経路:つまりすでに選択されている.
2、選択リスト:つまり、現在できる選択です.
3、終了条件:つまり決定木の底に到達し、選択できない条件.
コードの面では、遡及アルゴリズムのフレームワーク:
result = []
def backtrack( , ):
if :
result.add( )
return
for in :
backtrack( , )
その核心はforループの中の再帰であり,再帰呼び出しの前に「選択をする」こと,再帰呼び出しの後に「選択を取り消す」こと,特に簡単である.
枝切り方法:
注意事項
1.選択リストループ内で判断が必要な場合はcontinue(このステップがだめで次のステップを行う機会があることを示す)、選択リストループ外で判断した場合はreturnで中断する
2.まず現在の経路を判断し、次の選択リストに進む.これにより、すべての状態が判断されることが保証されます.
(剣指offer 12,13有感而発)
問題の順序を決める.
Leetcode:46,47,39,40,78,90,22
剣指offer:12,13
【leetcode 46】全配列
# ， start， ， start， start ， ， 。
# ， 。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
# [1, 2, 3], 1， 2，3， start
# ， 2， 1，3， start
result = []
size = len(nums)
if size == 0:#
return result
def backtrack(path, nums):
'''
:param path:
:param nums:
：len(path)==size
'''
if len(path) == size:
result.append(copy.deepcopy(path))
return
for i in range(len(nums)):#
#path.append(nums[i])
backtrack(path + [nums[i]], nums[:i]+nums[i+1:])
#path.pop()#
backtrack([], nums)
return result【leetcode 46】全配列2
# +
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
result = []
size = len(nums)
if size == 0:
return result
nums.sort() #
def backtrack(path, nums):
if len(path) == size:
result.append(copy.deepcopy(path)) # ，
return
for i in range(len(nums)):#
if i > 0 and nums[i] == nums[i-1]: #i>0 ， 【 + 】
continue
#path.append(nums[i])
backtrack(path + [nums[i]], nums[:i]+nums[i+1:])
#path.pop()#
backtrack([], nums)
return result
# ， ， ， 。【leetcode 39】コンビネーション
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
size = len(candidates)
if size == 0:
return result
def backtrack(path, start, residue):
if residue == 0:
result.append(copy.deepcopy(path))
return
if residue < 0:
return
for c in range(start, size): # [2, 3, 6, 7] 3， 3 ， 2 。
#residue -= candidates[i] ， residue
#path.append(candidates[c])
# print(path)
backtrack(path + [candidates[c]], c, residue - candidates[c]) ## residue-candidate[i]
#path.pop()
backtrack([], 0, target)
return result【leetcode 40】コンビネーション2
この問題は2回目にやった時も問題が発生した.問題は枝を切る条件にある
if i > start and candidates[i-1] == candidates[i]:
continue
if s < 0 or start >= size:
この大物を参考にして、とてもよく書けました.https://leetcode-cn.com/problems/combination-sum-ii/solution/xiang-xi-jiang-jie-ru-he-bi-mian-zhong-fu-by-allen/
前の問題の回朔と全く同じで、悪いのはただ1つのどのように繰り返しの問題を避けるかだけです
これは繰り返しを避けることが大切です.この方法の最も重要な役割は,同じ階層に同じ要素が現れないようにすることである.しかし、異なるレベル間の重複を許可します.
1/2このような状況は発生しない/5例2 1/2このような状況は確かに許可されている/2なぜあるのかこの不思議な効果は?まずcur-1==curは、現在の要素が以前の要素と同じか否かを判定するための文である.この文は例1を切り落とすことができる.しかし問題が来て、現在の要素と前の要素をすべて切り落とすと、例2の状況も消えてしまいます.2番目の2が現れたとき、彼は前の2と同じだったからだ.
では、例2をどのように残すのでしょうか.ではcur>beginを用いてこのような状況を回避すると、例1の2つの2つは同じレベルにあり、例2の2つの2つの2は異なるレベルにあることがわかります.1つのforループでは、遍歴されたすべての数が1つのレベルに属します.1つのレベルで、2が1つしか現れなければならない場合は、最初に繰り返される2を見逃しますが、後に現れる2を見逃しません.最初に現れた2の特徴はcur==beginである.2番目に現れた2つの特徴はcur>beginである.
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
size = len(candidates)
if size == 0:
return result
candidates.sort()
def backtrack(path, start, residue):
if residue == 0:
result.append(copy.deepcopy(path))
return
if residue < 0 or start >= size:#
return
for c in range(start, size):
# c start c-1 。
if c > start and candidates[c-1] == candidates[c]:#for ， ， 。 https://leetcode-cn.com/problems/combination-sum-ii/solution/xiang-xi-jiang-jie-ru-he-bi-mian-zhong-fu-by-allen/
continue
#path.append(candidates[c])
# i+1 ，start ，
backtrack(path + [candidates[c]], c+1, residue - candidates[c])
#path.pop()
backtrack([], 0, target)
return result【leetcode 78】サブセット
構想:図を描いた後、すべてのノードが要求に合っていることが分かった.だからそれぞれの葉にresultを加えます
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
size = len(nums)
if size == 0:
return result
def backtrack(path, start):
result.append(path)
if start == size:
return
for i in range(start, size):
backtrack(path+[nums[i]], i+1)
backtrack([], 0)
return result【leetcode 90】サブセット2
また枝切りの問題にぶつかった.絵を描くと、1、2、2のときは2つの2が最初の2を残しておけばいいことがわかります.
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
result = []
size = len(nums)
if size == 0:
result.append([])
return
nums.sort()
def backtrack(path, start):
result.append(path) #
if start == size:
return
for i in range(start, size):
if i > start and nums[i-1] == nums[i]: # ，
continue
backtrack(path + [nums[i]], i + 1)
backtrack([], 0)
return result[leetcode 79]単語検索——[剣指offer]12題
backtrackに戻り値があるのはこれだけのようで、やはり難しいと思いますハハハハ.
markはマトリクス要素をマークするために使用され、0はアクセスしていないことを示し、1はアクセスしたことを示す.
考え方:
注意:
考え方1
class Solution(object):
def exist(self, board, word):
row = len(board)
col = len(board[0])
if row == 0:
return False
mark = [[0 for _ in range(col)] for _ in range(row)]
def backtrack(i, j, mark, word):
if len(word) == 0:
return True
if not (i >= 0 and j >= 0 and i < row and j < col):
return False
if mark[i][j] == 1:
return False
if board[i][j] == word[0]:
mark[i][j] = 1
# 。
fanhuiz = backtrack(i+1, j, mark, word[1:]) or backtrack(i-1, j, mark, word[1:]) or backtrack(i, j-1, mark, word[1:]) or backtrack(i, j+1, mark, word[1:])
# if not (backtrack(i+1, j, mark, word[1:]) or backtrack(i-1, j, mark, word[1:]) or backtrack(i, j-1, mark, word[1:]) or backtrack(i, j+1, mark, word[1:]))
if not fanhuiz:
mark[i][j] = 0 # ， ，
return False
else:
return True
return False
for i in range(row):
for j in range(col):
if backtrack(i, j, mark, word):
return True
return False考え方2:
class Solution(object):
def exist(self, board, word):
directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
row = len(board)
col = len(board[0])
if row == 0:
return False
def backtrack(i, j, word, mark):
#
if len(word) == 0:
return True
for direct in directs: # （ ）
cur_i = i + direct[0]
cur_j = j + direct[1]
if cur_i >= 0 and cur_i < row and cur_j >= 0 and cur_j < col and board[cur_i][cur_j] == word[0]:# word
if mark[cur_i][cur_j] == 1:
continue
#
#
mark[cur_i][cur_j] = 1
if backtrack(cur_i, cur_j, word[1:], mark) is True:
return True
else:
mark[cur_i][cur_j] = 0
return False
mark = [[0 for _ in range(col)] for _ in range(row)]
for i in range(row):
for j in range(col):
if board[i][j] == word[0]:
#
mark[i][j] = 1
if backtrack(i, j, word[1:], mark) == True:# False
return True
else:
mark[i][j] = 0
return False[剣指offer]13題ロボットの動き範囲
考え方1:backtrackは戻り値がなければ処理しなくてもよい.
class Solution:
def movingCount(self, threshold, rows, cols):
self.count = 0
if rows == 0:
return self.count
mark = [[0 for _ in range(cols)] for _ in range(rows)]
def backtrack(i, j, k):
if i < 0 or i >= rows or j < 0 or j >= cols:
return
if mark[i][j] == 1:
return
tmpi = list(map(int, list(str(i))))
tmpj = list(map(int, list(str(j))))
if sum(tmpi) + sum(tmpj) > k:
return
mark[i][j] = 1
self.count += 1
backtrack(i-1, j, k)
backtrack(i+1, j, k)
backtrack(i, j-1, k)
backtrack(i, j+1, k)
backtrack(0, 0, threshold)
return self.count考え方2:
初期ijの処理に注意してください.
class Solution:
def movingCount(self, threshold, rows, cols):
directs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
self.count = 0
if rows == 0:
return self.count
mark = [[0 for _ in range(cols)] for _ in range(rows)]
mark[0][0] = 1
def backtrack(i, j, k):
for direct in directs:
cur_i = i + direct[0]
cur_j = j + direct[1]
if not (cur_i >= 0 and cur_i < rows and cur_j >= 0 and cur_j < cols):
continue
i_list = list(map(int, list(str(cur_i))))
j_list = list(map(int, list(str(cur_j))))
if sum(i_list) + sum(j_list) > k:
continue
if mark[cur_i][cur_j] == 1:
continue
self.count += 1
mark[cur_i][cur_j] = 1
backtrack(cur_i, cur_j, k)
if threshold > 0:
self.count = 1
backtrack(0, 0, threshold)
return self.countまとめ:いくつかの小さな細部があり、出会った穴を記録します.1、count=0はselfと書かなければならない.count=0ですが、マトリクスリストは使用しません.2、バックトラックに戻り値がある場合、再帰判定時に3、mapを適用する対象は正の整数でなければならず、負の数ではないので、i,jがアウトであるか否かを判断してからi_を得るlist, j_list.
[leetcode 22]かっこの生成
構想:絵を描いて、経路と中断条件をよく考えます.
class Solution:
def generateParenthesis(self, n: int):
result = []
if n == 0:
return result
def helper(left, right, path):
if right > left:
return
if left == n and right == n:
result.append(path[:])
return
if left < n:
helper(left+1, right, path+'(')
if right < n:
helper(left, right+1, path+')')
helper(0, 0, '')
return result