Leetcode
各問題の詳細は上記leetcodeから確認してください。
16問目までは追記予定。
前回
自分の初挑戦時の回答
Problem8
- 入力:任意の文字列
- 目的:文字列から数値を切り出す、それが32ビットの範囲外の場合は32ビットの最大・最小値を返す
入力が +-2
のケースを考慮できておらずテストとおらず修正してサブミット。
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).
Problem9
- 入力:任意のinteger
- 目的:整数は回文(palindrome)のようになっているか判定
以前、文字列の中の回文の最大マッチングがあり、類似問題。
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.
Problem10 (未回答)
- 入力:0以上の長さの文字列が二つ
- 目的:一方の文字列は「
*
」と「.
」で記述された正規表現になっている、もう一つの文字列が正規表現にマッチしているか判定
難しいため、一旦スキップ。
...
参照:正規表現の実装
一度みたサイトをメモ。
Problem11
- 入力:自然数のリスト
- 目的:数値と同じ高さの棒が並んでいるとして、最も面積が大きくできるような棒の組み合わせを求め、その面積を返す(要問題参照)
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.
Problem12
- 入力:整数
- 目的:決められた規則に基づいて整数をローマ数字に置き換える
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.
Problem13
- 入力:ローマ数字を表した文字列
- 目的:今度はローマ数字から整数値に変換する
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.
Problem14
- 入力:文字列のリスト
- 目的:リストに含まれる文字列で共通するプレフィックスを見つける
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.
一回目のサブミットは文字列の長さについて気を使わずに out of range を出してしまったので気をつけたい。strlist.sort()
でのソートは必要ありません.
トライ木
今回の問題では使用しなかったが、調べてる途中で見たページをメモ。 あるノードXの下の全てのノードがXと同じプレフィックスを持つような木をトライ木と呼ぶ。
トライ木
トライ木(英: trie)やプレフィックス木(英: prefix tree)とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス(接頭部)があり、ルート(根)には空の文字列が対応している。 (Wikipedia: トライ木)
トライ木の「実装の工夫」の章から実装の仕方を見ることができる。
Coding Puzzles, 3nd edition: Thinking in code (English Edition)
- 作者: codingtmd
- 発売日: 2019/02/13
- メディア: Kindle版
- この商品を含むブログを見る