Matsushita's Blog

2017-05-12から1日間の記事一覧

Longest Substring Without Repeating Characters

問題 文字列sが与えられ、以下の条件での最大の部分文字列の長さを出力する。 条件は、部分文字列内には同じ文字は被ってはいけない。 leetcode.com 解法 ハッシュマップを用いて、キーに文字をバリューにその文字が出現した場所(index)を保存することでO(N…

N以下の素数の個数を求める Count Primes in LeetCode

問題 leetcode.com 解法 N√Nの解法だと間に合わない。 素数の倍数は全て素数ではないという性質を使って解く。 素数を見つけたら、その倍数を予め素数ではない印を付けておく。 ソースコード 参考 この解法の計算量はO(NloglogN)らしい。 www.youtube.com

隣接する要素は盗めない泥棒 House Robber in LeetCode 動的計画法

問題 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が交わる点を見つける Intersection of Two Linked Lists in LeetCode

問題 2つのLinkedListが与えられ、2つが交差する点を見つける問題 leetcode.com 解法 HashMapを用いた解法は空間計算量がO(N)となるが、O(1)で解ける方法がある。 以下の2つの処理を同時に行う リストAを順番に先頭から見ていき、末尾までいったらリストB…

Excel Sheet Column Number

問題 アルファベットの文字列が与えられ、それをエクセルシートに対応した数字を出力する問題 leetcode.com ソースコード アルファベットから数字へ 数字からアルファベットへ

配列の中のマジョリティーを探す Majority Element in LeetCode

問題 Int型の配列が与えられて、出現回数が配列の要素数の過半数以上の物を出力する問題。 必ずマジョリティな要素は存在すると保証されている。 leetcode.com 解き方 HashMapを用いれば時間計算量O(N)で解けるが、空間計算量はO(N)になってしまう。この問題…