LeetCode 101:あなたと一緒に簡単に問題を書く(python版)第2章最も分かりやすい欲張りアルゴリズム
LeetCode 101:あなたと一緒に簡単に問題を書きます(python版)
注:作者:高暢Chang Gao、原書はc++バージョンで、解題の構想ははっきりしていて、知識点は全面的で、良い本です;pythonバージョンに翻訳された解法は必ずしも最適解法ではないかもしれませんが、本人は初心者なので、アルゴリズムの実現は第一歩で、最適化してからやります.権利侵害があれば、連絡して削除します.
第2章最も分かりやすい欲張りアルゴリズム
2.1アルゴリズムは、その名の通り、貪欲アルゴリズムまたは貪欲思想が貪欲な戦略を採用し、操作のたびに局所的に最適であることを保証し、最終的に得られた結果をグローバルに最適化する.最も簡単な例を挙げます:明ちゃんと王さんはりんごが好きで、明ちゃんは5つ食べることができて、王さんは3つ食べることができます.りんご園に食べきれないりんごがあることを知っています.明ちゃんと王さんは全部でどれだけのりんごを食べますか.この例では、私たちが選ぶことができる貪欲な戦略は、一人一人が自分が食べることができる最も多くのリンゴを食べることであり、これは一人一人にとって局所的に最も優れている.また、グローバル結果はローカル結果の単純な和であり、ローカル結果は互いにコヒーレントではないため、ローカル最適戦略も同様にグローバル最適戦略である.
2.2分配問題455.Assign Cookies (Easy)
テーマは子供たちとビスケットの山があり、子供一人一人が飢餓度を持っていて、ビスケットごとに大きさがあります.子供一人一人が最大1つのビスケットしか食べられず、ビスケットの大きさが子供の飢餓度より大きいときだけ、この子は満腹になります.最大でどれだけの子供が満腹になるかを解く.
入出力サンプルは、子供の飢餓度とクッキーの大きさを表す2つの配列を入力します.出力は最大何人の子供が満腹になることができる数量があります
この例では,2人の子供に[1,2],[1,3],[2,3]の3つの組み合わせのいずれかを与えることができ,2人の子供は満腹になることができる.
問題解飢餓度が一番小さい子供が一番満腹になりやすいので、私たちはまずこの子を考えます.残りのビスケットが飢餓度の大きい子供を満たすようにするために、私たちはこの子の飢餓度より大きく、最小のビスケットをこの子にあげなければならない.この子を満たした後、私たちは同じ戦略を取って、残りの子供の中で飢餓度が最も小さい子供を考えて、条件を満たしていないビスケットが存在するまで考えました.簡単に言えば、ここの貪欲な策略は、残りの子供の中で最小の飢餓度の子供に最小の満腹のビスケットを割り当てることです.具体的には、大きさの関係を得る必要があるので、子供とビスケットを別々にソートするのが便利です.これにより、飢餓度が最も小さい子供とサイズが最も小さいビスケットから出発し、条件を満たすペアがどれだけあるかを計算することができます.
135.Candy(Hard)
テーマは子供たちが一列に並んでいて、子供一人一人が自分の採点を持っていることを説明します.今、これらの子供にキャンディを出す必要があります.ルールは、一人の子供の採点が自分のそばの子供より高い場合、この子供はそばの子供より多くのキャンディを手に入れなければなりません.すべての子供は少なくとも1つのキャンディを持っていなければなりません.最低何個のキャンディが必要かを解く.
入出力サンプル入力は、子供のスコアを表す配列です.出力は最低キャンディの数です.
この例では、最も少ないキャンディ分法は[2,1,2]である.
問題解455が終わったら、比較関係のある貪欲な戦略には必ず順序や選択が必要だと思いますか?この問題も貪欲な策略を運用しているが、私たちは簡単な2回の遍歴だけでいい:すべての子供のキャンディの数を1に初期化する.まず左から右へ遍歴し、右の子供のスコアが左より高い場合、右の子供のキャンディの数は左の子供のキャンディの数に1を加えるように更新されます.右から左にもう一度繰り返し、左の子供のスコアが右の子供より高く、左の子供の現在のキャンディ数が右の子供のキャンディ数より大きくない場合、左の子供のキャンディ数は右の子供のキャンディ数に1を加えるように更新されます.この2回の遍歴で、配られたキャンディはテーマの要求を満たすことができます.ここでの欲張り戦略は,遍歴のたびに隣接側の大きさ関係のみを考慮し更新することである.サンプルでは、初期化されたキャンディ割り当ては[1,1,1,1]であり、1回目の遍歴更新後の結果は[1,1,2]であり、2回目の遍歴更新後の結果は[2,1,2]である.
2.3区間問題435.Non-overlapping Intervals (Medium)
タイトルは,所与の複数の区間を記述し,これらの区間が互いに重ならないようにするために必要な除去区間の最小個数を計算する.起止接続は重複しない.
入出力サンプル入力は、区間の開始と終了を表す複数の長さが2に固定された配列からなる配列です.削除する区間の数を示す整数を出力します.
この例では,残りの区間[[1,2],[2,4]]が互いに重ならないように区間[1,3]を除去することができる.
問題解保留区間を選択する際、区間の終わりは非常に重要である:選択した区間の終わりが小さいほど、他の区間に残る空間が大きくなり、より多くの区間を保留することができる.したがって,我々が取った貪欲な戦略は,末尾が小さく交差しない区間を優先的に保持することである.具体的には,まず区間を末尾の大きさに従って増順に並べ替え,末尾が最小で前の選択の区間と重ならない区間を毎回選択する.サンプルでは、ソート後の配列は[[1,2],[1,3],[2,4]]である.我々の貪欲な戦略に従って、まず区間に初期化された[1,2].[1,3]と[1,2]が交差するため、私たちはこの区間をスキップした.[2,4]と[1,2]は交差しないため,我々はそれを保持する.したがって、最終的に保持される区間は[[1,2],[2,4]]注:ソートは、実際の状況に基づいて、区間を先頭にソートするか、末尾にソートするか、先頭と末尾を個別にソートするかを判断できます.
2.4練習
基礎難易度605.Can Place Flowers(Easy)はどのような貪欲な戦略を取って、最も多くの花を植えることができますか?
452 Minimum Number of Arrows to Burst Balloons(Medium)という問題は435とよく似ていますが、少し違いますが、具体的にはどこが違いますか?
763 Partition Labels(Medium)あなたの貪欲な戦略を満たすために、いくつかの前処理が必要ですか?注意配列を処理する前に,1回の情報(周波数,個数,1回目の出現位置,最後の出現位置など)を統計することで,問題の難易度を大幅に低減できる.
122 Best Time to Buy and Sell Stock II(Easy)株取引問題型で比較的簡単な問題ですが、取引回数を制限しない場合、どのようにして最大利益を得ることができますか?
進級難易度406 Queue Reconstruction by Height(Medium)の暖かいヒントで、この問題は並べ替えと挿入操作を同時に必要とする可能性がある.
665 Non-decreasing Array(Easy)は、あなたの貪欲な戦略が様々な場合でも最適な解であるかどうかをよく考える必要があります.
注:作者:高暢Chang Gao、原書はc++バージョンで、解題の構想ははっきりしていて、知識点は全面的で、良い本です;pythonバージョンに翻訳された解法は必ずしも最適解法ではないかもしれませんが、本人は初心者なので、アルゴリズムの実現は第一歩で、最適化してからやります.権利侵害があれば、連絡して削除します.
第2章最も分かりやすい欲張りアルゴリズム
2.1アルゴリズムは、その名の通り、貪欲アルゴリズムまたは貪欲思想が貪欲な戦略を採用し、操作のたびに局所的に最適であることを保証し、最終的に得られた結果をグローバルに最適化する.最も簡単な例を挙げます:明ちゃんと王さんはりんごが好きで、明ちゃんは5つ食べることができて、王さんは3つ食べることができます.りんご園に食べきれないりんごがあることを知っています.明ちゃんと王さんは全部でどれだけのりんごを食べますか.この例では、私たちが選ぶことができる貪欲な戦略は、一人一人が自分が食べることができる最も多くのリンゴを食べることであり、これは一人一人にとって局所的に最も優れている.また、グローバル結果はローカル結果の単純な和であり、ローカル結果は互いにコヒーレントではないため、ローカル最適戦略も同様にグローバル最適戦略である.
2.2分配問題455.Assign Cookies (Easy)
テーマは子供たちとビスケットの山があり、子供一人一人が飢餓度を持っていて、ビスケットごとに大きさがあります.子供一人一人が最大1つのビスケットしか食べられず、ビスケットの大きさが子供の飢餓度より大きいときだけ、この子は満腹になります.最大でどれだけの子供が満腹になるかを解く.
入出力サンプルは、子供の飢餓度とクッキーの大きさを表す2つの配列を入力します.出力は最大何人の子供が満腹になることができる数量があります
input: [1,2], [1,2,3]
output: 2
この例では,2人の子供に[1,2],[1,3],[2,3]の3つの組み合わせのいずれかを与えることができ,2人の子供は満腹になることができる.
問題解飢餓度が一番小さい子供が一番満腹になりやすいので、私たちはまずこの子を考えます.残りのビスケットが飢餓度の大きい子供を満たすようにするために、私たちはこの子の飢餓度より大きく、最小のビスケットをこの子にあげなければならない.この子を満たした後、私たちは同じ戦略を取って、残りの子供の中で飢餓度が最も小さい子供を考えて、条件を満たしていないビスケットが存在するまで考えました.簡単に言えば、ここの貪欲な策略は、残りの子供の中で最小の飢餓度の子供に最小の満腹のビスケットを割り当てることです.具体的には、大きさの関係を得る必要があるので、子供とビスケットを別々にソートするのが便利です.これにより、飢餓度が最も小さい子供とサイズが最も小さいビスケットから出発し、条件を満たすペアがどれだけあるかを計算することができます.
"""
， ， ， ，
"""
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
num = min(len(g),len(s))
i, j = 0, 0
while i < len(g) and j < len(s):
if g[i] <= s[j]:
i += 1
j +=1
else:
j += 1
return i
135.Candy(Hard)
テーマは子供たちが一列に並んでいて、子供一人一人が自分の採点を持っていることを説明します.今、これらの子供にキャンディを出す必要があります.ルールは、一人の子供の採点が自分のそばの子供より高い場合、この子供はそばの子供より多くのキャンディを手に入れなければなりません.すべての子供は少なくとも1つのキャンディを持っていなければなりません.最低何個のキャンディが必要かを解く.
入出力サンプル入力は、子供のスコアを表す配列です.出力は最低キャンディの数です.
input: [1,0,2]
output: 5
この例では、最も少ないキャンディ分法は[2,1,2]である.
問題解455が終わったら、比較関係のある貪欲な戦略には必ず順序や選択が必要だと思いますか?この問題も貪欲な策略を運用しているが、私たちは簡単な2回の遍歴だけでいい:すべての子供のキャンディの数を1に初期化する.まず左から右へ遍歴し、右の子供のスコアが左より高い場合、右の子供のキャンディの数は左の子供のキャンディの数に1を加えるように更新されます.右から左にもう一度繰り返し、左の子供のスコアが右の子供より高く、左の子供の現在のキャンディ数が右の子供のキャンディ数より大きくない場合、左の子供のキャンディ数は右の子供のキャンディ数に1を加えるように更新されます.この2回の遍歴で、配られたキャンディはテーマの要求を満たすことができます.ここでの欲張り戦略は,遍歴のたびに隣接側の大きさ関係のみを考慮し更新することである.サンプルでは、初期化されたキャンディ割り当ては[1,1,1,1]であり、1回目の遍歴更新後の結果は[1,1,2]であり、2回目の遍歴更新後の結果は[2,1,2]である.
"""
， ，
， +1，
， +1（ ， ）
"""
class Solution:
def candy(self, ratings: List[int]) -> int:
nums = [1] * len(ratings)
for i in range(1, len(ratings)):
if ratings[i] > ratings[i - 1]:
nums[i] = nums[i - 1] + 1
for i in range(len(ratings) - 1, 0, -1):
if ratings[i] < ratings[i - 1]:
if nums[i - 1] <= nums[i]:
nums[i - 1] = nums[i] + 1
result = sum(nums)
return result
2.3区間問題435.Non-overlapping Intervals (Medium)
タイトルは,所与の複数の区間を記述し,これらの区間が互いに重ならないようにするために必要な除去区間の最小個数を計算する.起止接続は重複しない.
入出力サンプル入力は、区間の開始と終了を表す複数の長さが2に固定された配列からなる配列です.削除する区間の数を示す整数を出力します.
input: [[1,2], [2,4], [1,3]]
output: 1
この例では,残りの区間[[1,2],[2,4]]が互いに重ならないように区間[1,3]を除去することができる.
問題解保留区間を選択する際、区間の終わりは非常に重要である:選択した区間の終わりが小さいほど、他の区間に残る空間が大きくなり、より多くの区間を保留することができる.したがって,我々が取った貪欲な戦略は,末尾が小さく交差しない区間を優先的に保持することである.具体的には,まず区間を末尾の大きさに従って増順に並べ替え,末尾が最小で前の選択の区間と重ならない区間を毎回選択する.サンプルでは、ソート後の配列は[[1,2],[1,3],[2,4]]である.我々の貪欲な戦略に従って、まず区間に初期化された[1,2].[1,3]と[1,2]が交差するため、私たちはこの区間をスキップした.[2,4]と[1,2]は交差しないため,我々はそれを保持する.したがって、最終的に保持される区間は[[1,2],[2,4]]注:ソートは、実際の状況に基づいて、区間を先頭にソートするか、末尾にソートするか、先頭と末尾を個別にソートするかを判断できます.
"""
， ， ，
"""
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort()
j = 0
for i in range(len(intervals)-1):
if intervals[i+1][0] >= intervals[i][0] and intervals[i+1][0] < intervals[i][1]:
if intervals[i][1] <= intervals[i+1][1]:
intervals[i], intervals[i+1] = intervals[i+1],intervals[i]
j += 1
return j
2.4練習
基礎難易度605.Can Place Flowers(Easy)はどのような貪欲な戦略を取って、最も多くの花を植えることができますか?
452 Minimum Number of Arrows to Burst Balloons(Medium)という問題は435とよく似ていますが、少し違いますが、具体的にはどこが違いますか?
763 Partition Labels(Medium)あなたの貪欲な戦略を満たすために、いくつかの前処理が必要ですか?注意配列を処理する前に,1回の情報(周波数,個数,1回目の出現位置,最後の出現位置など)を統計することで,問題の難易度を大幅に低減できる.
122 Best Time to Buy and Sell Stock II(Easy)株取引問題型で比較的簡単な問題ですが、取引回数を制限しない場合、どのようにして最大利益を得ることができますか?
進級難易度406 Queue Reconstruction by Height(Medium)の暖かいヒントで、この問題は並べ替えと挿入操作を同時に必要とする可能性がある.
665 Non-decreasing Array(Easy)は、あなたの貪欲な戦略が様々な場合でも最適な解であるかどうかをよく考える必要があります.
"""
605
， ， （0，0，0） （ ）
， ， ( ）
"""
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
flowerbed = [0] + flowerbed + [0]
for i in range(1, len(flowerbed)-1):
if [flowerbed[i-1],flowerbed[i],flowerbed[i+1]] == [0,0,0]:
n -= 1
flowerbed[i] = 1
if n > 0:
return False
else:
return True
"""
452
， ，
： ， +1，
"""
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
points.sort(key=lambda x:x[1])
j = 1
first_end = points[0][1]
for i in range(1, len(points)):
if points[i][0] > first_end:
j += 1
first_end = points[i][1]
return j
"""
763
， ，
： （ enumerate() ）
for （head tail）
"""
class Solution(object):
def partitionLabels(self, S):
last = {
value: key for key, value in enumerate(S)}#
#print(last)#{'a': 8, 'b': 5, 'c': 7, 'd': 14}
head = tail = 0
result = [] #
for key, value in enumerate(S):
tail = max(tail, last[value])
if key == tail:
result.append(tail - head + 1)
head = tail + 1
return result
"""
122 II
： ，
： ， ， ， ，
"""
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i-1]:
profit += prices[i] - prices[i-1]
return profit
"""
406
， ， h k
：K 0 , ， people.sort(key=lambda x:(-x[0],x[1])) h K ， （ ， K ）
"""
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
if not people:
return []
people.sort(key=lambda x:(-x[0],x[1]))
new_people = []
for p in people:#
new_people.insert(p[1],p)
return new_people
"""
665
——
： ，count+1， ，count>1, False
：Ⅰ—— （ ）；Ⅱ—— ( ）
： [3,4,2*,3], count=1， ， ， >2 2<3， [3，4，4*，3] ， >2 [1,4,1,2] ， Ⅱ
， ：
（Ⅰ）， 2 （Ⅰ）, [4,4,3*,3]， ， False
（ ）
"""
#
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
count = 0
for i in range(1,len(nums)):
if nums[i] < nums[i-1]:
count += 1
if count >1:
return False
if i > 1 and nums[i] < nums[i-2]:
nums[i] = nums[i-1]
return True
#
class Solution:
def checkPossibility(self, nums: List[int]) -> bool:
count = 0
for i in range(1,len(nums)):
if nums[i] < nums[i-1]:
count += 1
if i+1 < len(nums) and i-2 >= 0:
if nums[i+1] < nums[i-1] and nums[i-2] > nums[i]:
return False
if count > 1:
return False
return True