LeetCode

スポンサーリンク
LeetCode

947. Most Stones Removed with Same Row or Column

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

343. Integer Break

Solution が無かったので自分の解法。 まずは10ぐらいまで手作業で実験してみる。 2 : 1x1=1 3 : 1x2=2 4 : 2x2=4 5 : 2x3=6 6 : 3x2x2=9 7 : 3x4=...
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に行か...
LeetCode

二分木の通りがけ順をMorris traversalで解く

二分木の値を通りがけ順に出力する問題。 再帰を使った深さ優先探索で解ける。 # Definition for a binary tree node. # class TreeNode: # def __...
2022.02.10
LeetCode

784. Letter Case Permutation

英数字の文字列が与えられ、アルファベットを大文字小文字に変換した際の全パターンを列挙する問題。 数字は変換しないので、アルファベットかどうかで場合分けしながら効率的な全探索を考える。 再帰 文字列を先頭か...
LeetCode

O(N)で567. Permutation in String

2つの文字列s1とs2が与えられ、s1の並び替えがs2に含まれるかどうか(s1の順列がs2の部分文字列か)判定する問題。 最初に思いついた解法 s1, s2 の長さをn1, n2とする。 s2から長さn1...
LeetCode

5通りの方法で189. Rotate Arrayを解く

長さnの配列をk個右に回転させる問題。 There are at least three different ways to solve this problem.と書いてあったので、色々試してみた。 全探索 ...
LeetCode

最大部分列和をKadane’s algorithmで解く

与えられた配列のうち、連続した部分配列の和の最大値を求める問題を考える(最大部分配列問題、最大部分列和問題)。 愚直に解くと二重ループだが、O(n^2)となり遅い。 DPの一種であるKadane's algorithm...
LeetCode

1302. Deepest Leaves Sum

簡単なグラフの問題。 幅優先探索と深さ優先探索の両方で解いてみた。 class Solution: def deepestLeavesSum(self, root: TreeNode) -&gt...
スポンサーリンク
タイトルとURLをコピーしました