週末だったのでちまちまと他のことをしながらやりました．
5がわからなくて長時間悩んだり…
前回はこちら blog.naosuke.me
#4 Median of Two Sorted Arrays
問題
- 2つの整列済みの配列 num1, num2 が与えられる
[1,3]と[2]
- この2つの配列の中央値を返却する
- このとき， num1とnum2を結合すると
[1, 2, 3]となるため，中央値は2となる
- このとき， num1とnum2を結合すると
解答
- 何も考えずにnum1, num2を結合しsortしなおして arrayに格納する
- 中央値の添字を，配列長 / 2でとる
- 奇数のときは，切り捨てた値であればOK (Rubyは添字が0始まりなので)
array = [1,2,3]であれば長さ3，割って切り捨てたら1でarray[1] = 2で中央値が取れる - 偶数のとき，配列長 / 2であれば整数となるが，例えば4のときは中央は 2番め，3番めの平均なので，添字をよしなに丸めてあげる
- 奇数のときは，切り捨てた値であればOK (Rubyは添字が0始まりなので)
雑感
- 配列の結合を使ったけど，メモリ効率はあまり良くないんだろうなという感じ
- sorted arrayであれば，2つの配列の大小を比較しながら中央値になりうる値まで走査をしたほうがいいと思う
- 新規で配列を定義しないので，O(n)のメモリを使用しなくて済むはず
- が，多分見た目として分かりづらいのであまり書きたくないなあという印象
#5 Longest Palindromic Substring
問題
- ある文字列sが渡され，そこに含まれた回文となる部分文字列のうち最長のものを返す
abacdededだと，回文としてabcdeaba`deddedededeが含まれる- このうち最長のものは
dededであるため，これを返却する
解答
- まず，全体が回文のものはその時点で終わり
- で，そうじゃないものに対して，初期値としての部分文字列として文字列の頭1字を格納しておく
- その後，全文字に対して前方から操作を行う
- 今見ている文字から，前方に対して同じ文字が連続しているかをチェック
- 連続した文字列分から，左右に1字ずつ走査していく
- 回文は中心から必ず左右対称の文字列となるため
- 例:
abcbaだとcを中心にabとbaが対称，abcccbaだと cccを中心にそれぞれ対称
- 回文であれば更に1字広げる，そうでなければ最長文字列の更新のチェックを行う
雑感
- 回文判定とかは普段書かないのでめちゃくちゃ悩んだ
- 基本的な方針は最初の頃から思いついていたんだけど，走査方法が非常にイマイチで，実行時間切れなどを多発してしまった
- 今回の回答が最大O(n2)だけど，その前のは連続した文字列部分の判定を別途していたため O(n3)とかだった
- ↑が解消しても，回文判定の範囲とかにちまちまバグがあってミスを連発
- 終わったあと解説を見たけど，O(n)とかでもやろうと思えばできるらしい．まじかよ
- コード的にもあまりきれいな感じじゃないので，もう少しなんかないかなあと思ってる
