LeetCode

LeetCode

pythonで深さ優先探索の行きがけ、帰りがけ、通りがけの使い分け

深さ優先探索では、行きがけ(preorder)、帰りがけ(postorder)、通りがけ(inorder)を使い分けることがあるが、こんがらってしまう。 理解しやすいよう2分木で簡単な実装をしてみた。以下、当該ノード、左部分技、右部分技のこ...
LeetCode

1799. Maximize Score After N Operations

Dailyで出てきたHardの問題。 解説を見るとビットマスキングとDPを使っていて難しい。 もっと単純に、素直に解けたので備忘録。もちろん最適解ではない。 成約を見ると以下の通りである。 1 <= n <= 7nums.length ==...
LeetCode

LeetCode Biweekly Contest 97の解法

問題ページはこちら。 2553. Separate the Digits in an Array 与えられた数値を1桁ずつ返す問題。 整数で与えられるので、文字列として解釈して1文字ずつ解を得ればOK。 class Solution: de...
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を選ぶ / 選ばない...
LeetCode

尺取り法、累積和、二分探索で209. Minimum Size Subarray Sum

総和がtarget以上になるような最小の部分列の長さを求める問題。 公式の最適解は2 pointersで、O(N)で解ける。 class Solution: def minSubArrayLen(self, target: int, num...
LeetCode

947. Most Stones Removed with Same Row or Column

二次元座標平面上において、x座標またはy座標が共通の点を次々に削除していき、削除した個数を求める問題。 深さ優先探索 全ての座標から出発し、DFSを行う。 たどり着けた点を削除し、もう削除できなくなったら次のスタート地点から再度探索を行う。...
LeetCode

再帰、DP、法則性の3通りで343. Integer Break

Solution が無かったので自分の解法。 再帰 まずは具体例で考える。 n=10の場合、1と9に分けられる。9はさらに2と7、7はさらに3と4・・・というように樹形図のように分岐していく。 ある値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に行かせれば良い。...