LeetCodeの記録

概要

LeetCode の勉強の記録です。Gemini により出力された模範的実装や解説を整理しています。言語は Ruby を選択しています。Paiza の問題もあります。

LeetCode: 1. Two Sum

https://leetcode.com/problems/two-sum/

• 数値の配列 nums と数値 target が与えられる。配列の数値の二つを合計して target の値となる場合のインデックスの配列を返す。インデックスの値は異なるものでなければいけない
• 数値をキー、値をインデックスとしたハッシュテーブルを作成する
• nums を each_with_index で繰り返す。繰り返し毎に、nums の数値とtarget との差を求める。その値がハッシュテーブルに存在すれば、現在のインデックスとハッシュテーブルのインデックスを返す。なければハッシュテーブルに数値とインデックスを保存して次に進む
• この場合の計算量は $O(n)$ となる

LeetCode: 2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/

• 逆順の数字を各ノードに持つ連結リストが二つ与えられる。二つの和を連結リストで返す
• リストの先頭が一の位なので、順番に足していきながら、新しい連結リストを作る。筆算のイメージなので、繰り上がりに注意する
• 与えられた二つの連結リストの長さが違う場合にも処理できるように注意する
• 連結リストは while で list.next がなくなるまで繰り返すことで順次処理ができる

LeetCode: 9. Palindrome Number

https://leetcode.com/problems/palindrome-number/

• 与えられた数値が回文になっていれば true、そうでなければ false を返す
• 負の数は回文にならないので処理しない。また、0以外の数で末尾が0のものも回文にならない
• 与えられた数値を文字列にせず、数値を反転させる
  • % 10 で剰余を求め、x * 10 で桁を上げることで反転する
  • 反転させた数値が元の数値と == であれば回文になっていると言える
• 与えられた数値を変数に一時保管する。その変数の値を /= 10 で最下位桁を取り除きながら繰り返す。一時保管した変数が 0 以下になったら終了する（while temp_x > 0）
• 与えられた数値の桁数の半分までの繰り返しにすることで、より効率的になる

Paiza: B175: ピックアップ

• ランレングス圧縮された文字列が与えられる。文字列を展開し、展開された文字列から指定された範囲の文字列を抜き出して出力する
• 圧縮された文字列からアルファベットと数値を抜き出す場合は scan を使う
• 文字列から特定の範囲の文字列を抜き出す場合は slice を使う