めも

メモ.

Leetcodeを進める:問8〜問14

Leetcode

leetcode.com

各問題の詳細は上記leetcodeから確認してください。

16問目までは追記予定。

前回

paper.hatenadiary.jp

自分の初挑戦時の回答

Problem8

  • 入力:任意の文字列
  • 目的:文字列から数値を切り出す、それが32ビットの範囲外の場合は32ビットの最大・最小値を返す

入力が +-2 のケースを考慮できておらずテストとおらず修正してサブミット。

gist.github.com

Runtime: 44 ms, faster than 77.82% of Python3 online submissions for String to Integer (atoi).
Memory Usage: 13.1 MB, less than 90.30% of Python3 online submissions for String to Integer (atoi).

Submission Detail

Problem9

  • 入力:任意のinteger
  • 目的:整数は回文(palindrome)のようになっているか判定

以前、文字列の中の回文の最大マッチングがあり、類似問題。

gist.github.com

Runtime: 64 ms, faster than 94.01% of Python3 online submissions for Palindrome Number.
Memory Usage: 13.3 MB, less than 50.78% of Python3 online submissions for Palindrome Number.

Submission Detail

Problem10 (未回答)

  • 入力:0以上の長さの文字列が二つ
  • 目的:一方の文字列は「*」と「.」で記述された正規表現になっている、もう一つの文字列が正規表現にマッチしているか判定

難しいため、一旦スキップ。

...

参照:正規表現の実装

一度みたサイトをメモ。

Problem11

  • 入力:自然数のリスト
  • 目的:数値と同じ高さの棒が並んでいるとして、最も面積が大きくできるような棒の組み合わせを求め、その面積を返す(要問題参照)

gist.github.com

Runtime: 56 ms, faster than 91.58% of Python3 online submissions for Container With Most Water.
Memory Usage: 14.3 MB, less than 93.20% of Python3 online submissions for Container With Most Water.

Submission Detail

Problem12

  • 入力:整数
  • 目的:決められた規則に基づいて整数をローマ数字に置き換える

gist.github.com

Runtime: 44 ms, faster than 98.88% of Python3 online submissions for Integer to Roman.
Memory Usage: 13.1 MB, less than 92.15% of Python3 online submissions for Integer to Roman.

Submission Detail

Problem13

  • 入力:ローマ数字を表した文字列
  • 目的:今度はローマ数字から整数値に変換する

gist.github.com

Runtime: 76 ms, faster than 37.26% of Python3 online submissions for Roman to Integer.
Memory Usage: 13 MB, less than 99.75% of Python3 online submissions for Roman to Integer.

Submission Detail

Problem14

  • 入力:文字列のリスト
  • 目的:リストに含まれる文字列で共通するプレフィックスを見つける

gist.github.com

Runtime: 36 ms, faster than 89.85% of Python3 online submissions for Longest Common Prefix.
Memory Usage: 13.2 MB, less than 58.50% of Python3 online submissions for Longest Common Prefix.

Submission Detail

一回目のサブミットは文字列の長さについて気を使わずに out of range を出してしまったので気をつけたい。strlist.sort()でのソートは必要ありません.

トライ木

今回の問題では使用しなかったが、調べてる途中で見たページをメモ。 あるノードXの下の全てのノードがXと同じプレフィックスを持つような木をトライ木と呼ぶ。

トライ木

トライ木(英: trie)やプレフィックス木(英: prefix tree)とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス(接頭部)があり、ルート(根)には空の文字列が対応している。 (Wikipedia: トライ木)

トライ木の「実装の工夫」の章から実装の仕方を見ることができる。