なおすけの落書き帳

毎日がエブリデイ。

LeetCode解いたメモ #7〜#10

今日もなんとかトライできた…!(昨日の話)
結局ブログを書きそびれたので2日分かきます.

前回はこちら. blog.naosuke.me

#6 ZigZag Conversation

文章かくのが思ったより手こずってるので別途書きます><

#7 Reverse Integer

leetcode.com

問題

  • 32bitの整数xが渡される
  • 符号はそのままに反転た数字を返す
    • 例) -123 -> -321
  • ただし,符号付き32bitを超える場合は0を返す

解答

github.com

  • まず与えられたxの符号をチェックする
  • xを文字列化し反転させ,その後↑でチェックした符号を掛けてやる
  • で,最後にInt範囲にあるかどうかをチェックする

所感

  • まあ文字列にするとあまり速くないなあという感じ
  • intのままもやってみたけどあまり速くならなかった…
    • たぶん実装力がない

#8 String to Integer (atoi)

leetcode.com

問題

  • ある文字列sが与えられる
    • 文字列には数字,アルファベット,スペースが含まれる
  • C/C++でいうところの atoi(s) と同様の処理を実装する
    • '42' -> 42, '-42' -> -42, '42hoge-42' -> 42, 'hoge42' -> 0

解答

github.com

  • まず,空白を除いた後の先頭文字が符号/数値で始まらない場合はatoi失敗なので0を返す
  • 数値を走査中かどうかのフラグを1つ,また符号を管理するための変数を1つ定義する
  • その後,sについて1文字ずつ走査を行なう
    • 数字走査中に符号が出てきた場合,数値ではなくなるためその時点で走査を終了する
    • 同様に,数字走査中に数値以外が出てきた場合はその時点で走査終了する
    • そうでない場合,出現した文字を結果変数に格納し,次の文字に進む
  • 走査終了後,範囲の指示(32ビット符号付き整数)に基づいて値を丸める

所感

  • atoiの仕様の認識漏れが多く,WAを数回だした
    • '41+12' の場合は 41 を返すべきだが 4112 をかえしてしまったり
  • これもどう早くすればいいのかイマイチわからないんだけれども,discussionを見ると素直に String#to_i すれば速いみたいなこと書いていた
    • ライブラリってすごい

#9 Palindrome Number

leetcode.com

問題

  • ある数値xが与えられたとき,このxが回文となっているかを検査する
  • 121 みたいに,ひっくり返しても同じ数字を示す場合は true, そうでなければ false を返す
  • 符号の考慮の必要あり
    • -121 だとひっくり返すと 121- とかになるのでfalse

解答

github.com

  • 何も難しいことはせず,与えらとかになるのでれた数字のto_sとto_s.reverseを比較して一致しているかどうかを見ている

所感

  • 逆にこれ以上何をするんだみたいな感じですね
    • 負の数のとき,かならずfalseになるのでそこの枝刈りをするとか,1桁の場合は必ずtrueになるとか,細かい枝刈りは可能
  • 後は桁毎にループを回して比較もできなくはないが,あまりこねくり回すと見づらくなるのでなあ…という感じ

#10 Regular Expression Matching

leetcode.com

問題

  • 文字列s,pが与えられる
    • pは「パターン」として簡易的な正規表現の文字列が与えられる
  • 文字列sに対し,pが完全一致するかどうかをチェックするものを実装する

解答

github.com

  • まず,pを正規表現とみなして,そもそも一致する部分文字列があるかどうかをチェックする
    • そもそもこの時点で一致していなければfalse
  • その後, RegExp#match の返り値である MatchData#to_s を使い,部分一致した文字列が完全一致しているか文字列で比較する
    • == を使っているので,自ずと一致 or notが返却される

所感

  • これも #9 と同様に,これ以上どうすんの感のある解答
  • たぶん, RegExp#match の$1がsと一致しているかみたいなことを書くと更にわかりやすいのかなとか思ったりはした