LeetCodeの配列[Permutations]の組合せ[Combinations]と実現[Python]
8255 ワード
leetcodeには2つの古典的なテーマがあり、1つの配列の配列と組み合わせを求めて、深さ優先再帰検索で解くことができます.一緒にlook lookに行きましょう.
配列[Permutations]
标题:Given a collection of distinct integers,return all possible permutations.
Example:
構想:全配列問題を分解し,直接解くことができるまでサブ問題にすることができる.nums=[1,2,3]は,まず1を固定し,[2,3]を全列にした結果を1を足すとよいが,その後2を固定し,全列[1,3]を順次類推する.
次は対応するコードで、ある数を固定して、startの位置に置いて、startの後の数に対して全列に再帰します
再帰が完了したら、元の置換位置の2つの数を戻して、次の置換が元の順序に基づいていることに注意してください.
フル配列なのでDFS検索はnになってから終了します
再帰の場合、再帰関数の前の部分は順方向に実行され、後ろの部分は逆方向に実行されることを理解する必要があります.
[Combinations]
标题:Given two integers n and k,return all possible combinations of k numbers out of 1...n.
Example:
考え方:この問題は配列問題と似ている点もあれば、異なる点もあり、すべてのn要素ではなくk要素が必要であるため、DFSはkが終わるまで検索します.そのため、中間結果を保存するために追加のtemp配列も必要です.
正直、ここでもstartの意味はよくわかりませんが、知っている方はコメントで説明していただきたいです.ありがとうございます.
参照先:
https://www.cnblogs.com/grandyang/p/4358848.html https://www.cnblogs.com/grandyang/p/4332522.html
配列[Permutations]
标题:Given a collection of distinct integers,return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
構想:全配列問題を分解し,直接解くことができるまでサブ問題にすることができる.nums=[1,2,3]は,まず1を固定し,[2,3]を全列にした結果を1を足すとよいが,その後2を固定し,全列[1,3]を順次類推する.
次は対応するコードで、ある数を固定して、startの位置に置いて、startの後の数に対して全列に再帰します
再帰が完了したら、元の置換位置の2つの数を戻して、次の置換が元の順序に基づいていることに注意してください.
フル配列なのでDFS検索はnになってから終了します
再帰の場合、再帰関数の前の部分は順方向に実行され、後ろの部分は逆方向に実行されることを理解する必要があります.
class Solution:
def permute(self, nums):
res = []
self.func(nums, 0 ,res)
return res
def func(self,nums, start, res):
if start==len(nums):
res.append(nums.copy())
else:
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start]
self.func(nums, start+1, res)
nums[start], nums[i] = nums[i], nums[start]
[Combinations]
标题:Given two integers n and k,return all possible combinations of k numbers out of 1...n.
Example:
Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
考え方:この問題は配列問題と似ている点もあれば、異なる点もあり、すべてのn要素ではなくk要素が必要であるため、DFSはkが終わるまで検索します.そのため、中間結果を保存するために追加のtemp配列も必要です.
正直、ここでもstartの意味はよくわかりませんが、知っている方はコメントで説明していただきたいです.ありがとうございます.
class Solution:
def combine(self, n, k):
if k>n or k<0:
return []
res = []
temp = []
self.func(n, k, 1, temp, res)
return res
def func(self, n, k, start, temp, res):
if len(temp) == k:
res.append(temp.copy())
else:
for i in range(start, n+1):
temp.append(i)
self.func(n, k, i+1, temp, res)
temp.pop()
参照先:
https://www.cnblogs.com/grandyang/p/4358848.html https://www.cnblogs.com/grandyang/p/4332522.html