Longest Substring Without Repeating Characters
問題
文字列sが与えられ、以下の条件での最大の部分文字列の長さを出力する。 条件は、部分文字列内には同じ文字は被ってはいけない。
解法
ハッシュマップを用いて、キーに文字をバリューにその文字が出現した場所(index)を保存することでO(N)で解くことができる。
ソースコード
隣接する要素は盗めない泥棒 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
解法
上記のサンプルのように、深さ優先探索を用いて要素を取得していく。 その際、i番目の要素を取得した場合、その次の要素の取り方は一様なので、i番目の要素を取った時の最大値を保存しておくことでその値を再利用できる。
解法
2つのLinkedListが交わる点を見つける Intersection of Two Linked Lists in LeetCode
問題
2つのLinkedListが与えられ、2つが交差する点を見つける問題
解法
HashMapを用いた解法は空間計算量がO(N)となるが、O(1)で解ける方法がある。
以下の2つの処理を同時に行う
- リストAを順番に先頭から見ていき、末尾までいったらリストBの先頭に進む。
- リストBを順番に先頭見ていき、末尾まで行ったらAの先頭に進む。
すると交差していたら同じタイミング交差点を通化することになる。