はじめに
就活用にLeetCodeを始めたのですが、AtCoderやTechFULをしているだけでは関わらない知識が多く、難しいと感じました。
備忘録 兼 これから始める方々のお役にたてればよいと思い記事にすることにしました。
※解答例は Python3 です
※解答例でACは出ましたが、最適解かどうかはわかりません。参考程度にご覧ください
問題１. Two Sum
題名 ： Two Sum
難易度 ： Easy
系統 ： 全探索
概要 ： int配列(nums)中の２つの要素を足して、int変数(target)と一致する２つの要素の添字を返す
制約(3つ)
１．2 <= nums.length <= 10^4
２．-10^9 <= nums[i] <= 10^9
３．-10^9 <= target <= 10^9
解答方法(問題１)
単純に考えるとTLEになってしまう
下記のように、２重for文で回すとTLEになってしまいます。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# 1つ目の要素をiとしてnums[i]を全探索
for i in range(len(nums)):
# ２つ目の要素をjとしてnums[j]を全探索
for j in range(i+1, len(nums)):
# targetと一致したら、その添字を返す
if nums[i]+nums[j] == target:
return [i, j]
片方が決まると、もう片方も決まる 法則を利用する
今回の問題は、２つの要素を足してtargetと一致させることが目的です。
１つの要素が決まると、もう１つの要素が決まることを利用して解かなければいけません。
つまり、 target - nums[ i ] と一致する要素があれば、それが答えになります。下記が私の解答です。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# nums[i]を全探索
for i in range(len(nums)):
# target-nums[i] と一致する要素が存在しなければcontinue
if target - nums[i] not in nums:
continue
# 同じ要素を２つ選んでしまわないよう、添字が異なる場合だけ処理する
elif i != nums.index(target-nums[i]):
return [i, nums.index(target-nums[i])]
まとめ(問題１)
２つの要素を１つの変数と一致させる問題では、片方の要素が決まると、もう片方の要素も決まる法則を利用しよう。
(選ぶ要素が増えた場合でも、一番最後の要素はfor文を回す必要がなくなる)
ちなみに、これはAtCoderでも時々出る問題ですね！
問題URL
問題2. Add Two Numbers
題名 ： Add Two Numbers
難易度 ： Medium
系統 ： 連結リスト(ListNode)
概要 ： 連結リスト１(l1)と連結リスト2(l2)を反転させて、２つの連結リストの値を合計して、連結リストにして返す
制約(3つ)
１．The number of nodes in each linked list is in the range [1, 100].
２．0 <= Node.val <= 9
３．It is guaranteed that the list represents a number that does not have leading zeros.
解答方法(問題2)
連結リストに慣れていけば普通に解ける！
今回の問題は２つの連結リストを反転してintにし、合計して、さらに反転させて、連結リストに戻すという４段階をそのまま実装するだけで難なく解けます。
が、連結リストの作り方に慣れていないと少し難しいです。解答を見て、連結リストの作り方を覚えましょう。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# 連結リストの要素を繋げ、反転後、intにして返す関数
def appends(l):
res = ''
while l: # 連結リストがNoneになるまで繰り返す
res += str(l.val)
l = l.next
return int(res[::-1]) # 反転させてintにする
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
f = appends(l1)
s = appends(l2)
num = str(f + s)[::-1] # fとsを合計して反転する
# ここからが連結リストを作成する処理
ans = ListNode()
tmp = ans # tmpにansへの参照を渡す
for i in range(len(num)):
tmp.val = num[i] # tmpに値を代入する
if i == len(num)-1: # 最後は.nextに代入せずにbreakする
break
tmp.next = ListNode() # tmp.nextに新しい連結リストを作成する
tmp = tmp.next # tmpに新しい連結リストへの参照を渡す
return ans
まとめ(問題2)
連結リストは頻出のようなので、連結リストの扱い方(作り方など)は覚えておいた方がよさそうです。
連結リストは実装が難しいですが、何度も解けばすぐに慣れます！
問題URL
問題3. Longest Substring Without Repeating Characters
題名 ： Longest Substring Without Repeating Characters
難易度 ： Medium
系統 ： 全探索・コーナーケース等？
概要 ： 文字列(s)に存在する、重複する文字のない連続する部分文字列の中での、最大長を返す
制約(3つ)
１．0 <= s.length <= 5 * 10^4
２．s consists of English letters, digits, symbols and spaces.
解答方法(問題3)
そのまま実装すれば解ける！
今回の問題は問題文そのままでOKです。'abcabcbb'を例にして説明します。
連続する部分文字列の中で、重複する文字のないものを前から順に列挙すると、[ 'abc', 'bca', 'cab', 'abc', 'cb', 'b' ]があります。この中で１番長いものはlength=3なので、３を返すことでACになります。
これが頭の中でできた人は、それを実装するだけで何の問題もなくACになると思います。
さまざまなケースに対応させよう！
上記の例で列挙する部分文字列が思いつかなかった人は、問題文そのまま実装すると、何らかのケースが抜け落ちていると思われます。
今回の問題は、イメージできなくても、ケース１つ１つに対してアプローチすれば解けそうな問題です！
ケース１ → 'a', '' (１文字や0文字の場合、いわゆるコーナーケース)
ケース2 → 'bbbbb' (1種類の文字しかない場合)
ケース3 → 'aabb' (同じ文字が連続で出現する場合)
ケース4 → 'abac' (同じ文字が間隔を開けて出現する場合)
きちんと考えれば他にもあるでしょう。自分でテストケースを作成してテストしてみることも大切ですね。
(私は最初、コーナーケースが抜け落ちていました、、、)
以下、解答例です。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
exist = [] # 今見ている部分文字列を保存する配列
maxLen = 0 # 探索時点での解答の最大長を保存する変数
# 文字列(s)を全探索
for i in range(len(s)):
if not s[i] in exist: # existにs[i]が存在しなければ、appendする
exist.append(s[i])
else: # existにs[i]が存在した場合、そこから右の文字列だけを残し、appendする
if len(exist) != 1: # 1文字の時に処理すると誤動作を起こすので追記
exist = exist[exist.index(s[i])+1:]
exist.append(s[i])
if len(exist) > maxLen: # len(exist)がmaxLenより大きければ更新する
maxLen = len(exist)
return maxLen
まとめ(問題3)
さまざまなケース(コーナーケース等)に気をつけよう！という問題でした。
時間があれば、思いつく限りのテストケースを作成して、テストするとよさそうです!
問題URL
備考
１つ１つの問題に別のアルゴリズムが必要でとても勉強になるので、興味のある方はぜひLeetCodeに登録してみてください！