LeetCode

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

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

問題ページはこちら。 2553. Separate the Digits in an Array 与えられた数値を１桁ずつ返す問題。 整数で与えられるので、文字列として解釈して１文字ずつ解を得ればOK。 class Solution: de...

mediumとは思えない難しさだったので備忘録。 与えられた配列からすべての部分列を作り、各部分列の最小値の合計を求める問題。 Input: arr = Output: 17Explanation:Subarrays are , , , ,...

daily challengeで出てきて難しかったので備忘録。 n個のjobのstartTime, endTime, profitが与えられ、スケジュールが重複しないように利益を最大化する問題。 全探索を考えた時、jobを選ぶ / 選ばない...

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

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

Solution が無かったので自分の解法。 再帰 まずは具体例で考える。 n=１０の場合、1と９に分けられる。９はさらに２と７、７はさらに３と４・・・というように樹形図のように分岐していく。 ある値numは、iとnum-iに分割でき、この...

k面のサイコロをn個振った時、合計値がtargetになる組み合わせの数を求める問題。 全探索する場合、1~kのどれが出るかという試行がn回繰り返され、O(K^N)となり間に合わない。 ここで、サイコロの出目を1つずつ足していくことを考える。...

問題はこちら。 2N人をA,Bの2つのグループ分け、均等に振り分けるために必要なコストを最小化する問題。 Aに振り分けるコスト、Bに振り分けるコストが与えられる。 貪欲法 Aに行きやすい人はAに行かせ、Bに行きやすい人はBに行かせれば良い。...