LeetCode pythonで深さ優先探索の行きがけ、帰りがけ、通りがけの使い分け
深さ優先探索では、行きがけ（preorder）、帰りがけ（postorder）、通りがけ（inorder）を使い分けることがあるが、こんがらってしまう。理解しやすいよう2分木で簡単な実装をしてみた。以下、当該ノード、左部分技、右部分技のこと...
LeetCode
LeetCode LeetCode 1799. Maximize Score After N Operations
Dailyで出てきたHardの問題。解説を見るとビットマスキングとDPを使っていて難しい。もっと単純に、素直に解けたので備忘録。もちろん最適解ではない。成約を見ると以下の通りである。1 <= n <= 7nums.length == 2 *...
LeetCode LeetCode Biweekly Contest 97の解法
問題ページはこちら。2553. Separate the Digits in an Array与えられた数値を１桁ずつ返す問題。整数で与えられるので、文字列として解釈して１文字ずつ解を得ればOK。class Solution: def se...
LeetCode 907. Sum of Subarray Minimums
mediumとは思えない難しさだったので備忘録。与えられた配列からすべての部分列を作り、各部分列の最小値の合計を求める問題。Input: arr = Output: 17Explanation:Subarrays are , , , , ,...
LeetCode 1235. Maximum Profit in Job Scheduling
daily challengeで出てきて難しかったので備忘録。n個のjobのstartTime, endTime, profitが与えられ、スケジュールが重複しないように利益を最大化する問題。全探索を考えた時、jobを選ぶ / 選ばないの2...
LeetCode 尺取り法、累積和、二分探索で209. Minimum Size Subarray Sum
総和がtarget以上になるような最小の部分列の長さを求める問題。公式の最適解は2 pointersで、O(N)で解ける。class Solution: def minSubArrayLen(self, target: int, nums:...
LeetCode 947. Most Stones Removed with Same Row or Column
二次元座標平面上において、x座標またはy座標が共通の点を次々に削除していき、削除した個数を求める問題。深さ優先探索全ての座標から出発し、DFSを行う。たどり着けた点を削除し、もう削除できなくなったら次のスタート地点から再度探索を行う。残った...
LeetCode 再帰、DP、法則性の３通りで343. Integer Break
Solution が無かったので自分の解法。再帰まずは具体例で考える。n=１０の場合、1と９に分けられる。９はさらに２と７、７はさらに３と４・・・というように樹形図のように分岐していく。ある値numは、iとnum-iに分割でき、この分割を繰...
LeetCode 1155. Number of Dice Rolls With Target Sum
k面のサイコロをn個振った時、合計値がtargetになる組み合わせの数を求める問題。全探索する場合、1~kのどれが出るかという試行がn回繰り返され、O(K^N)となり間に合わない。ここで、サイコロの出目を1つずつ足していくことを考える。サイ...
LeetCode 貪欲法とDPで 1029. Two City Scheduling
問題はこちら。2N人をA,Bの2つのグループ分け、均等に振り分けるために必要なコストを最小化する問題。Aに振り分けるコスト、Bに振り分けるコストが与えられる。貪欲法Aに行きやすい人はAに行かせ、Bに行きやすい人はBに行かせれば良い。Aに行く...