概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day34「118. Pascal's Triangle」
基本的にeasyのacceptanceが高い順から解いていこうかと思います。
Twitterやってます。
問題
160. Intersection of Two Linked Lists
Top 100 Liked QuestionsのEasy問題の最後から二つ目の問題です。
問題としては、2つの単方向連結リストの共通部分が始まるノードを見つけてくださいというものです。
例が図で解説されており、諸事情でこちらに直接載せることはできないので各々が確認して頂けると幸いです。
解法
最初こう書いたら、
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if headA == None or headB == None:
return None
LNA = headA
LNB = headB
while LNA != LNB:
if LNA == None:
LNA = headB
else:
LNA.next
if LNB == None:
LNB == headA
else:
LNB.next
return LNA
# Time Limit Exceeded
時間切れになったので、以下のようにwhile以降を内包表記で書き直してみたら行けました。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if headA == None or headB == None:
return None
LNA = headA
LNB = headB
while LNA != LNB:
LNA = headB if LNA == None else LNA.next
LNB = headA if LNB == None else LNB.next
return LNA
# Runtime: 168 ms, faster than 75.08% of Python3 online submissions for Intersection of Two Linked Lists.
# Memory Usage: 29.1 MB, less than 100.00% of Python3 online submissions for Intersection of Two Linked Lists.
なお、この問題の公式の解説の解き方ではBruteForce,HashMap,Two Pointerのいずれかを使うと良いよ！ってなってます。
気になるかたはそちらをチェックすることもお勧めします。
こっちの書き方の方が良いよ！とかこの言語で書いてみたよ！とかがあれば是非コメントしてみてください。