LeetCode / Palindrome Linked List
最近、ニュースを見る度に過剰反応が報道されていていらついていたのでテレビを全く見なくなり、Youtube視聴に退避していたのですが、
ついに好きな旅行系Youtuberの方が投稿を休止される事態となり、残念、うんざりな思いが蓄積されていっている今日この頃です。
現実逃避に、LeetCodeの解説をします。
https://leetcode.com/problems/palindrome-linked-list/
Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?
左右対称のlinked listかどうか判定する問題。Follow upに書かれている空間計算量の制約をクリアするのが骨です。
解法1
空間計算量のことを忘れれば、逆順のリストを用意し、一致を見ればよいだけなので簡単です。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def isPalindrome(self, head: ListNode) -> bool: vals = [] while head: vals += head.val, head = head.next return vals == vals[::-1]
これでは手応えがないので、空間計算量をに減らす方法を考えます。
解法2
空間計算量をとする方法となると、必然的に1つ1つのnodeを走査する方法しかない、となります。
結論から言えば、以下の手順をとります。
- 真ん中のnodeを求める
- 真ん中のnode以降のlinked listを逆順にしたlinked listを得る
- 元のlinked listと2で得た逆順のlinked listが一致しているか確認する
class Solution: def isPalindrome(self, head: ListNode) -> bool: fast = slow = head # 1. 真ん中のnodeを求める while fast and fast.next: fast = fast.next.next slow = slow.next # 2. 真ん中のnode以降のlinked listを逆順にしたlinked listを得る rev_half_head = None while slow: tmp = slow.next slow.next = rev_half_head rev_half_head = slow slow = tmp # 3. 元のlinked listと2で得た逆順のlinked listが一致しているか確認する while rev_half_head: if rev_half_head.val != head.val: return False rev_half_head = rev_half_head.next head = head.next return True
特に手順2のlinked listを空間計算量で逆順にするところがややこしいのですが、これはもう覚えてしまった方が良いかなと個人的には思っています。
COVID-19についてFactを抑えよう
COVID-19について、データを扱う人間の端くれならFactは抑えておきたいなーと思っていたら素晴らしい報告書が。
内容もさることながら、地道な現地調査を遂行した調査団のご尽力には恐れいる。。
一番気になる致死率のチャートもあった。
- 累積では3.8%
- 流行初期は17.3%だったが2/1以降の発症では0.7%（致死率の減少は医療水準の向上によるものと推察されている）
- Wuhanでは5.8%に対し中国の他エリアでは0.7%
因みに以下論文によれば、中国におけるインフルエンザに起因する致死率は2003-2008は0.6-0.7%だったとのこと。
まあいくらFactを並べても、視界に入らない人はなぜか入らないので放っとくかと思っていたけど、
トイレットペーパーが売り切れるという謎の傍迷惑な現象を受けて、情報発信した方が良いのかと思い直す今日この頃。
というわけで、まだタイトルほどのFactは集められていないけど、少し漁ってみることとします。
ちなみに日本語記事もあるようですね。NHKグッジョブ。
LeetCode / Power of Two
https://leetcode.com/problems/power-of-two/
Given an integer, write a function to determine if it is a power of two.
Example 1:
Input: 1
Output: true
Explanation: 20 = 1
Example 2:
Input: 16
Output: true
Explanation: 24 = 16
Example 3:
Input: 218
Output: false
与えられた値が２の階乗かどうかを判定する問題。ビット演算を使った解法を初めて知ったときにはほーっと思いました。
解法1
ビット演算で解く方法。
2進法で表すと、2の階乗の値となるごとに桁が上がることを利用します。以下の通りですね。
0 0 1 1 2 01 3 11 4 100 5 101 6 110 7 111 8 1000
具体的には、値nとn-1をAND演算すると、nが2の階乗のときのみ0となることを利用します。3&4や7&8は0になりますね。
class Solution: def isPowerOfTwo(self, n: int) -> bool: if n == 0: return False elif n & (n-1) != 0: return False else: return True
解法2
シンプルなIterativeな解法も示しておきます。これでもTLEにはなりません。
class Solution: def isPowerOfTwo(self, n: int) -> bool: if n == 0: return False else: while n % 2 == 0: n /= 2 return n == 1
LeetCode / Invert Binary Tree
初年度のベンチャーはどこもそうなんだと思いますが、特に平日は心身ともに擦り減るので、ベンチャーに休日はないと言えど強制的に休日を作らないとなかなかやっていけません。
と言っても、ただボーッとしてると仕事のことを考えてしまうので、LeetCodeでもやって脳を強制リセットします。
脳の中にコンテナをいくつか作ってうまくオーケストレーションする感じ。あ、また仕事のこと考えてる。。。
https://leetcode.com/problems/invert-binary-tree/
Invert a binary tree.
Binary Treeの左右を反転させる問題です。
解法1
Recursiveな解法。
コードにしてみると至って単純で、左の部分木を右に、右の部分木を左に入れ替える処理を再帰的に行います。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if not root: return None right = self.invertTree(root.right) left = self.invertTree(root.left) root.left = right root.right = left return root
時間計算量、空間計算量ともにです。
解法2
Iterativeな解法。
stackという一時変数を用意して、左右の入れ替えを行う対象を格納していきます。
後は先ほどの解法と同様に、左の部分木を右に、右の部分木を左に入れ替えた上で、入れ替えた部分木をstackに格納し、同様の処理を行っていきます。
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def invertTree(self, root: TreeNode) -> TreeNode: stack = [root] while stack: node = stack.pop() if node: node.left, node.right = node.right, node.left stack += node.left, node.right return root
while loop中のpop前のstack, pop後のnodeの中身を見ていくと、以下のようになっています。
len(stack): 1
stack: [TreeNode{val: 4, left: TreeNode{val: 2, left: TreeNode{val: 1, left: None, right: None}, right: TreeNode{val: 3, left: None, right: None}}, right: TreeNode{val: 7, left: TreeNode{val: 6, left: None, right: None}, right: TreeNode{val: 9, left: None, right: None}}}]
node: TreeNode{val: 4, left: TreeNode{val: 2, left: TreeNode{val: 1, left: None, right: None}, right: TreeNode{val: 3, left: None, right: None}}, right: TreeNode{val: 7, left: TreeNode{val: 6, left: None, right: None}, right: TreeNode{val: 9, left: None, right: None}}}
len(stack): 2
stack: [TreeNode{val: 7, left: TreeNode{val: 6, left: None, right: None}, right: TreeNode{val: 9, left: None, right: None}}, TreeNode{val: 2, left: TreeNode{val: 1, left: None, right: None}, right: TreeNode{val: 3, left: None, right: None}}]
node: TreeNode{val: 2, left: TreeNode{val: 1, left: None, right: None}, right: TreeNode{val: 3, left: None, right: None}}
len(stack): 3
stack: [TreeNode{val: 7, left: TreeNode{val: 6, left: None, right: None}, right: TreeNode{val: 9, left: None, right: None}}, TreeNode{val: 3, left: None, right: None}, TreeNode{val: 1, left: None, right: None}]
node: TreeNode{val: 1, left: None, right: None}
len(stack): 4
stack: [TreeNode{val: 7, left: TreeNode{val: 6, left: None, right: None}, right: TreeNode{val: 9, left: None, right: None}}, TreeNode{val: 3, left: None, right: None}, None, None]
node: None
len(stack): 3
stack: [TreeNode{val: 7, left: TreeNode{val: 6, left: None, right: None}, right: TreeNode{val: 9, left: None, right: None}}, TreeNode{val: 3, left: None, right: None}, None]
node: None
len(stack): 2
stack: [TreeNode{val: 7, left: TreeNode{val: 6, left: None, right: None}, right: TreeNode{val: 9, left: None, right: None}}, TreeNode{val: 3, left: None, right: None}]
node: TreeNode{val: 3, left: None, right: None}
len(stack): 3
stack: [TreeNode{val: 7, left: TreeNode{val: 6, left: None, right: None}, right: TreeNode{val: 9, left: None, right: None}}, None, None]
node: None
len(stack): 2
stack: [TreeNode{val: 7, left: TreeNode{val: 6, left: None, right: None}, right: TreeNode{val: 9, left: None, right: None}}, None]
node: None
len(stack): 1
stack: [TreeNode{val: 7, left: TreeNode{val: 6, left: None, right: None}, right: TreeNode{val: 9, left: None, right: None}}]
node: TreeNode{val: 7, left: TreeNode{val: 6, left: None, right: None}, right: TreeNode{val: 9, left: None, right: None}}
len(stack): 2
stack: [TreeNode{val: 9, left: None, right: None}, TreeNode{val: 6, left: None, right: None}]
node: TreeNode{val: 6, left: None, right: None}
len(stack): 3
stack: [TreeNode{val: 9, left: None, right: None}, None, None]
node: None
len(stack): 2
stack: [TreeNode{val: 9, left: None, right: None}, None]
node: None
len(stack): 1
stack: [TreeNode{val: 9, left: None, right: None}]
node: TreeNode{val: 9, left: None, right: None}
len(stack): 2
stack: [None, None]
node: None
len(stack): 1
stack: [None]
node: None
これも時間計算量、空間計算量ともにです。
LeetCode / Implement Stack using Queues, Implement Queue using Stacks
重要なデータ構造の1つにStack（スタック）とQueue（キュー）がありますが、これを実装しろという問題を取り上げます。
と言っても、こちらの解説記事にあるように、スタックもキューも配列で表現することができ、データ構造としては特別なものではありません。重要なのは以下の使われ方の違いです。
スタック データ構造に入っている要素のうち、最後に push した要素を取り出す
キュー データ構造に入っている要素のうち、最初に push した要素を取り出す
上記メソッドを有するStack class, Queue classを実装します。
Implement Stack using Queues
https://leetcode.com/problems/implement-stack-using-queues/
Implement the following operations of a stack using queues.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.
Example:
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); // returns 2
stack.pop(); // returns 2
stack.empty(); // returns false
Notes:
You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
まずはstackの実装から。問題タイトルにもあるように、queueを使ってstackを実装することが求められています。
queueを使うということは、可能な操作も限定されます。only push to back, peek/pop from front, size, and is empty operations are validとあるように、pushは後ろから、popは前からに限定されます。
誤答
一応やっておくと、問題の意図を無視してstackを使ってしまっても、テストは通ってしまいます。
ただ当然ながら、stackを使ってstackを作っても何の意味もないですね。
pythonではlistがstackにあたる挙動を示します。
class MyStack: def __init__(self): """ Initialize your data structure here. """ self.stack = [] def push(self, x: int) -> None: """ Push element x onto stack. """ self.stack.append(x) def pop(self) -> int: """ Removes the element on top of the stack and returns that element. """ return self.stack.pop() def top(self) -> int: """ Get the top element. """ return self.stack[-1] def empty(self) -> bool: """ Returns whether the stack is empty. """ return len(self.stack) == 0
解法
この問題ではqueueを使ってstackを実装することを求められていますが、ポイントはpop。繰り返しになりますが、stackでは最後にpushされた要素を取り出しますが、queueでは最初にpushされた要素を取り出します。
pythonではqueue.popleft()で最初にpushされた要素を取り出せます。popleftを使って、pushを実行した際に、後にpushされた要素が先頭にくるようにqueueを並び替えるのが以下の解法です。
class MyStack: def __init__(self): self.queue = collections.deque() def push(self, x: int) -> None: q = self.queue q.append(x) for _ in range(len(q)-1): q.append(q.popleft()) def pop(self) -> int: return self.queue.popleft() def top(self) -> int: return self.queue[0] def empty(self) -> bool: return len(self.queue) == 0
時間計算量がpushで、popでは
かかることになります。
ちなみに、本問題の要求のもとでは使えませんが、以下記事にあるようにcollections.deque()にはpopメソッドも存在し、時間計算量で後方から要素を取り出し削除することが可能です。
Implement Queue using Stacks
https://leetcode.com/problems/implement-queue-using-stacks/
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Example:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
次に、Queueの実装です。今度はstackを使ってqueueを実装することを求められています。
これも可能な操作が限定されます。only push to top, peek/pop from top, size, and is empty operations are validとなっています。つまりpush, peek, popについてはlist.append(x), list[-1], list.pop()のみが許容されていることになります。
解法
2つstackを用意し、pushの際はinStackに格納、peekやpopの際はinStackの要素を逆順にして格納したoutStackを用意し、処理を行うのが以下の解法です。
class MyQueue: def __init__(self): """ Initialize your data structure here. """ self.inStack, self.outStack = [], [] def push(self, x: int) -> None: """ Push element x to the back of queue. """ self.inStack.append(x) def pop(self) -> int: """ Removes the element from in front of queue and returns that element. """ self.peek() return self.outStack.pop() def peek(self) -> int: """ Get the front element. """ if(self.outStack == []): while(self.inStack != []): self.outStack.append(self.inStack.pop()) return self.outStack[-1] def empty(self) -> bool: """ Returns whether the queue is empty. """ return len(self.inStack) == 0 and len(self.outStack) == 0
LeetCode / Contains Duplicate, Contains Duplicate Ⅱ
明日から海外旅行で浮き足立っていますが、リストから重複判定する問題シリーズを解きます。
https://leetcode.com/problems/contains-duplicate/
Given an array of integers, find if the array contains any duplicates.
Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
Example 1:
Input: [1,2,3,1]
Output: true
Example 2:
Input: [1,2,3,4]
Output: false
Example 3:
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true
リスト中に重複があればTrueを返す問題。これは簡単。
解法1
class Solution: def containsDuplicate(self, nums: List[int]) -> bool: return len(set(nums)) != len(nums)
これだけでは物足りないのでもう一問。
https://leetcode.com/problems/contains-duplicate-ii/
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
問題文の英語がわかるかどうかが勝負。インデックスi, jについて、nums[i] = nums[j]となり、かつiとjの差がk以下の要素があればTrueを返す問題。
解法1
class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: dic = {} for i, n in enumerate(nums): if n in dic and i - dic[n] <= k: return True dic[n] = i return False
LeetCode / Reversed Linked List
https://leetcode.com/problems/reverse-linked-list/
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
1つのLinked Listをsortして逆順にする問題。
解法1
Iterativeな解法。
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def reverseList(self, head: ListNode) -> ListNode: prev = None while head: curr = head head = head.next curr.next = prev prev = curr return prev
head, curr, prevの値の移り変わりは以下の通り。
head ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}
curr ListNode{val: 1, next: None}
prev ListNode{val: 1, next: None}
head ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}
curr ListNode{val: 2, next: ListNode{val: 1, next: None}}
prev ListNode{val: 2, next: ListNode{val: 1, next: None}}
head ListNode{val: 4, next: ListNode{val: 5, next: None}}
curr ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}
prev ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}
head ListNode{val: 5, next: None}
curr ListNode{val: 4, next: ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}}
prev ListNode{val: 4, next: ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}}
head None
curr ListNode{val: 5, next: ListNode{val: 4, next: ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}}}
prev ListNode{val: 5, next: ListNode{val: 4, next: ListNode{val: 3, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}}}
headの各要素を走査する間に、以下の操作が走ります。
curr = head head = head.next # headを1つ先に進める curr.next = prev # currの2つ目以降の要素に前のループで格納しておいたprevの値を入れる prev = curr # prevにcurrの値を入れる(新たな要素が1つ先頭に加わる)
解法2
Recursiveな解法。
class Solution: def reverseList(self, head): return self._reverse(head) def _reverse(self, node, prev=None): if not node: return prev n = node.next node.next = prev return self._reverse(n, node)
