2017-05-12から1日間の記事一覧
問題 文字列sが与えられ、以下の条件での最大の部分文字列の長さを出力する。 条件は、部分文字列内には同じ文字は被ってはいけない。 leetcode.com 解法 ハッシュマップを用いて、キーに文字をバリューにその文字が出現した場所(index)を保存することでO(N…
問題 leetcode.com 解法 N√Nの解法だと間に合わない。 素数の倍数は全て素数ではないという性質を使って解く。 素数を見つけたら、その倍数を予め素数ではない印を付けておく。 ソースコード 参考 この解法の計算量はO(NloglogN)らしい。 www.youtube.com
問題 N個の整数を持つ配列が与えられる。隣接する要素は取れないという条件で、各要素の和の最大を求める問題。 例 [1, 2, 3, 4, 5] という配列の場合は以下のようなとり方がある 1 , 3, 5 → 9 1, 4 → 5 1, 5 → 6 2, 4 → 6 2, 5 → 7 max = 9 leetcode.com 解…
問題 2つのLinkedListが与えられ、2つが交差する点を見つける問題 leetcode.com 解法 HashMapを用いた解法は空間計算量がO(N)となるが、O(1)で解ける方法がある。 以下の2つの処理を同時に行う リストAを順番に先頭から見ていき、末尾までいったらリストB…
問題 アルファベットの文字列が与えられ、それをエクセルシートに対応した数字を出力する問題 leetcode.com ソースコード アルファベットから数字へ 数字からアルファベットへ
問題 Int型の配列が与えられて、出現回数が配列の要素数の過半数以上の物を出力する問題。 必ずマジョリティな要素は存在すると保証されている。 leetcode.com 解き方 HashMapを用いれば時間計算量O(N)で解けるが、空間計算量はO(N)になってしまう。この問題…