LeetCodeLeetCode Biweekly Contest 97の解法 問題ページはこちら。 2553. Separate the Digits in an Array 与えられた数値を1桁ずつ返す問題。 整数で与えられるので、文字列として解釈して1文字ずつ解を得ればOK。 ...2023.02.06LeetCode
LeetCode907. Sum of Subarray Minimums mediumとは思えない難しさだったので備忘録。 与えられた配列からすべての部分列を作り、各部分列の最小値の合計を求める問題。 Input: arr = Output: 17Explanation:Subar...2022.12.14LeetCode
LeetCode1235. Maximum Profit in Job Scheduling daily challengeで出てきて難しかったので備忘録。 n個のjobのstartTime, endTime, profitが与えられ、スケジュールが重複しないように利益を最大化する問題。 全探索を考えた...2022.11.28LeetCode
LeetCode尺取り法、累積和、二分探索で209. Minimum Size Subarray Sum 総和がtarget以上になるような最小の部分列の長さを求める問題。 公式の最適解は2 pointersで、O(N)で解ける。 class Solution: def minSubArrayLen(sel...2022.08.19LeetCode
LeetCode947. Most Stones Removed with Same Row or Column 二次元座標平面上において、x座標またはy座標が共通の点を次々に削除していき、削除した個数を求める問題。 深さ優先探索 全ての座標から出発し、DFSを行う。 たどり着けた点を削除し、もう削除できなくなったら...2022.07.26LeetCode
LeetCode再帰、DP、法則性の3通りで343. Integer Break Solution が無かったので自分の解法。 再帰 まずは具体例で考える。 n=10の場合、1と9に分けられる。9はさらに2と7、7はさらに3と4・・・というように樹形図のように分岐していく。 ある...2022.06.292022.09.02LeetCode
LeetCode1155. Number of Dice Rolls With Target Sum k面のサイコロをn個振った時、合計値がtargetになる組み合わせの数を求める問題。 全探索する場合、1~kのどれが出るかという試行がn回繰り返され、O(K^N)となり間に合わない。 ここで、サイコロの出目を1...2022.03.16LeetCode
LeetCode貪欲法とDPで 1029. Two City Scheduling 問題はこちら。 2N人をA,Bの2つのグループ分け、均等に振り分けるために必要なコストを最小化する問題。 Aに振り分けるコスト、Bに振り分けるコストが与えられる。 貪欲法 Aに行きやすい人はAに行か...2022.03.09LeetCode
LeetCode二分木の通りがけ順をMorris traversalで解く 二分木の値を通りがけ順に出力する問題。 再帰を使った深さ優先探索で解ける。 # Definition for a binary tree node. # class TreeNode: # def __...2022.02.092022.02.10LeetCode
LeetCode784. Letter Case Permutation 英数字の文字列が与えられ、アルファベットを大文字小文字に変換した際の全パターンを列挙する問題。 数字は変換しないので、アルファベットかどうかで場合分けしながら効率的な全探索を考える。 再帰 文字列を先頭か...2021.12.27LeetCode