LeetCode O(N)で567. Permutation in String 2つの文字列s1とs2が与えられ、s1の並び替えがs2に含まれるかどうか(s1の順列がs2の部分文字列か)判定する問題。 最初に思いついた解法 s1, s2 の長さをn1, n2とする。 s2から長さn1の文字列を切り出し、collecti... 2021.11.16 LeetCode
LeetCode 5通りの方法で189. Rotate Arrayを解く 長さnの配列をk個右に回転させる問題。 There are at least three different ways to solve this problem.と書いてあったので、色々試してみた。 全探索 1個ずらす作業をk回繰り返す。... 2021.11.04 LeetCode
LeetCode 最大部分列和をKadane’s algorithmで解く 与えられた配列のうち、連続した部分配列の和の最大値を求める問題を考える(最大部分配列問題、最大部分列和問題)。 愚直に解くと二重ループだが、O(n^2)となり遅い。 DPの一種であるKadane's algorithmを使うとO(n)で高速... 2021.11.01 LeetCode