Google Code Jam 2016 B Rank and File 解法

問題

N×Nの行列を考える。各マスには数字が振られており、どの行もどの列も昇順になっている。 N×Nの行列では行と列の数は合計で2N個だが、この問題では2×N-1個の行か列のリストが与えられる。 取り除かれた行又は列のリストを出力する問題

Dashboard - Round 1A 2016 - Google Code Jam

解法

1行目と1列目の2つリストを考えた時に、それぞれの先頭の数字は同じ数字となる。このように列と行は必ず同じ数字を含んでいる。つまり、2N個のリストが与えられた場合、それぞれの数字の出現回数は必ず偶数個となる。よって取り除かれた数字を見つけるためには、出現回数が奇数の物をピックアップすればOK。この解法の計算量はO(N2)。

ソースコード

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

解法

上記のサンプルのように、深さ優先探索を用いて要素を取得していく。 その際、i番目の要素を取得した場合、その次の要素の取り方は一様なので、i番目の要素を取った時の最大値を保存しておくことでその値を再利用できる。

解法

2つのLinkedListが交わる点を見つける Intersection of Two Linked Lists in LeetCode

問題

2つのLinkedListが与えられ、2つが交差する点を見つける問題

leetcode.com

解法

HashMapを用いた解法は空間計算量がO(N)となるが、O(1)で解ける方法がある。

以下の2つの処理を同時に行う

  • リストAを順番に先頭から見ていき、末尾までいったらリストBの先頭に進む。
  • リストBを順番に先頭見ていき、末尾まで行ったらAの先頭に進む。

すると交差していたら同じタイミング交差点を通化することになる。

ソースコード

Excel Sheet Column Number

問題

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

leetcode.com

ソースコード

アルファベットから数字へ

数字からアルファベットへ

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

問題

Int型の配列が与えられて、出現回数が配列の要素数過半数以上の物を出力する問題。 必ずマジョリティな要素は存在すると保証されている。

leetcode.com

解き方

HashMapを用いれば時間計算量O(N)で解けるが、空間計算量はO(N)になってしまう。この問題は以下のようにすることで空間計算量O(1)で解くことができる。

ソースコード