概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day29「46. Permutations」
基本的にeasyのacceptanceが高い順から解いていこうかと思います。
Twitterやってます。
問題
単方向の連結リストが与えられるので、回文であるかをチェックしてください。
Example 1:
Input: 1->2
Output: falseExample 2:
Input: 1->2->2->1
Output: true
解法
最も簡単な方法としては、与えられた連結リストをひっくり返したものと一致すればTrueを、一致しなければFalseを返すというものです。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
value = []
while head:
value.append(head.val)
head = head.next
return value == value[::-1]
# Runtime: 92 ms, faster than 15.28% of Python3 online submissions for Palindrome Linked List.
# Memory Usage: 24.1 MB, less than 11.54% of Python3 online submissions for Palindrome Linked List.
今回は少し時間がなかったため、他の人の解答をdiscussから持ってきます。
例えばO(1)の解答とかですね。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head):
rev = None
fast = head
while fast and fast.next:
fast = fast.next.next
rev, rev.next, head = head, rev, head.next
tail = head.next if fast else head
isPali = True
while rev:
isPali = isPali and rev.val == tail.val
head, head.next, rev = rev, head, rev.next
tail = tail.next
return isPali
# Runtime: 92 ms, faster than 15.28% of Python3 online submissions for Palindrome Linked List.
# Memory Usage: 24.1 MB, less than 11.54% of Python3 online submissions for Palindrome Linked List.
わかりやすい解説としてはこのdiscussの内容がおすすめです。
視覚的に分かりやすいのすごい・・・
後、この本の連結リストの章にも複数の解法が載っていました。
時間がある人はチェックしてみると良いかもしれません。