#概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day21 「448. Find All Numbers Disappeared in an Array」
基本的にeasyのacceptanceが高い順から解いていこうかと思います。
Twitterやってます。
問題
難易度はeasy。
Top 100 Liked Questionsからの抜粋です。
連結リストについての基本的な知識を求められるような問題です。
連結リストが与えられ、その中に循環があるかどうかを判断します。
指定された連結リストの循環を表すために、末尾が接続する連結リストの位置（0から始まる）を表す整数posを使用します。なお、posが-1の場合は循環がないものとします。
Example1
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
解法
珍しくSolutionがあったのでそこに書かれているHashTable,もといHashMapの考え方を元に実装してみました。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
hashmap = {}
while head != None:
if head in hashmap:
return True
hashmap[head] = head
head = head.next
return False
# Runtime: 80 ms, faster than 9.62% of Python3 online submissions for Linked List Cycle.
# Memory Usage: 16.9 MB, less than 100.00% of Python3 online submissions for Linked List Cycle.
headの要素が空になるまでひたすらheadの要素を用意したhashmapに代入し、その次の要素をheadに代入するというものです。
仮にheadの要素がhashmapの中にあるのであればそれは循環するポイントがあるということなのでTrueを返し、最後までチェックしても存在しない場合はFalseを返す、というものです。
もう一つSolutionにあったTwoPointersというのも参考にして書いてみました。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head or not head.next:
return False
pre,cur = head,head.next
while pre != cur:
if not cur or not cur.next:
return False
pre,cur = pre.next,cur.next.next
return True
# Runtime: 84 ms, faster than 8.98% of Python3 online submissions for Linked List Cycle.
# Memory Usage: 16.9 MB, less than 100.00% of Python3 online submissions for Linked List Cycle.
そこまで速さは変わらないですね。
連結リストといえば、海外で有名なコーディング面接のバイブルともいうべきこの
世界で闘うプログラミング力を鍛える150問 ~トップIT企業のプログラマになるための本~ (日本語) 単行本（ソフトカバー）
本にも連結リストは再起的な処理が多く苦手な人が多いと書いてありましたが、確かに普段の開発で連結リストを頻繁には使わないので解くのに時間がかかりました。
ちなみに上の本は古く、今は新しい版があるのでもし買うならこちらを
世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法
買うことをお勧めします。
良さげな書き方があれば追記します。