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メソッドも存在し、時間計算量で後方から要素を取り出し削除することが可能です。

note.nkmk.me

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)

LeetCode / Isomorphic Strings

https://leetcode.com/problems/isomorphic-strings/

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:
Input: s = "egg", t = "add"
Output: true

Example 2:
Input: s = "foo", t = "bar"
Output: false

Example 3:
Input: s = "paper", t = "title"
Output: true

Note:
You may assume both s and t have the same length.

2つの同じ長さの文字列があって、文字iを文字jに置き換えると文字列sが文字列tに変わる、という対応関係が崩れていないことをisomorphicと言うそうです。

数学では同型写像を意味するそうです（聞いたこともない用語でしたが）。

解法がたくさんあって面白いですが、計算量オーダー的にはそこまで大きな差はありません。

解答・解説

解法1

sの各文字をkey, tの各文字をvalueに持つdictと、tの各文字をkey, sの各文字をvalueに持つdictの2つを用意し、対応関係をチェックします。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s_d = {}; t_d = {}
        for i,j in zip(s,t):
            if i in s_d and s_d[i] != j:
                return False
            elif j in t_d and t_d[j] != i:
                return False
            else:
                s_d[i] = j
                t_d[j] = i
        return True

2つdictを用意するので、空間計算量はとあまり効率的ではありませんが、分かりやすい解法かと思います。

解法2

同じ2つのdictを使う手法としては以下もあります。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        d1, d2 = {}, {}
        for i, val in enumerate(s):
            d1[val] = d1.get(val, []) + [i]
        for i, val in enumerate(t):
            d2[val] = d2.get(val, []) + [i]
        return sorted(d1.values()) == sorted(d2.values())

ただ、最後のsortに時間がかかるので時間計算量の面で劣ります。

解法3

文字列に対するfindメソッドで、文字列中の各文字が初めて出てくるインデックスを返させ、2つの文字列について同じ値が返ってくるかチェックします。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        return [s.find(i) for i in s] == [t.find(j) for j in t]

ただのfindメソッドをn回繰り返すことになるので、時間計算量の面で劣ります。

解法4

文字列sと文字列t中の文字を集合としたときの要素数と、文字列sとt中の文字のペアを集合としたときの要素数が同じかどうかをチェックするという解法もあります。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        return len(set(zip(s, t))) == len(set(s)) == len(set(t))

これが時間計算量/空間計算量的にも、コードの短さ的にも最も優れているかと思います。

解法5

最後に、アスキーコードを利用する解法。

アスキーコードの要素数である256個の要素からなるリストを用意します。
文字列sの各文字xをアスキーコードiに変換し、リストのi番目に、xのsにおけるインデックス+1を値として格納します。
文字列sが"abc"なら、ord("a")が97なので、リストの97番目の要素に0+1=1を格納します。
インデックス+1とするのは、リストの各要素の初期値を0としているためです。
このインデックスが文字列sとtでずれていないかをチェックします。

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        l1, l2 = [0 for _ in range(256)], [0 for _ in range(256)]
        for i in range(len(s)):
            if l1[ord(s[i])] != l2[ord(t[i])]:
                return False
            l1[ord(s[i])] = i+1
            l2[ord(t[i])] = i+1
        return True

LeetCode / Count Primes

https://leetcode.com/problems/count-primes/

Count the number of prime numbers less than a non-negative number, n.

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

与えられた値より小さい素数の数を返す問題。

解答・解説

誤答(TLE)

TLEですが、重要な考え方その1が含まれます。それは、

nが何らかの数pで割り切れる場合、n=pqであり、qがpより小さい場合には既にqもしくはqの約数で確かめた際に素因数が検出されているはずである。したがって、素因数候補として確かめるべきはまでで十分

です。

以上の考え方を取り入れたのが下記コードで、偶数の判定を飛ばす（2以外素数でない）改善も加えています。

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, math.floor(math.sqrt(n))+1, 2):
        if n % i == 0:
            return False
    return True

class Solution:
    def countPrimes(self, n: int) -> int:
        return sum([is_prime(i) for i in range(n)])

が、これだとまだTLEになります。もう一段の高速化を考えないといけません。

解法1

さらに高速化するにあたり、エラトステネスの篩というアルゴリズムがあります。これは、

以下の素数が既知のとき、 以上 以下の素数を決定するには、 以下の整数で 以下の素数の倍数を全て取り除けば（= 篩えば）よい

というものです。

class Solution:
    def countPrimes(self, n):
        if n < 3:
            return 0
        primes = [True] * n
        primes[0] = primes[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if primes[i]:
                primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
        return sum(primes)

LeetCode / Remove Linked List Elements

https://leetcode.com/problems/remove-linked-list-elements/

Remove all elements from a linked list of integers that have value val.

Example:

Input: 1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

これがlistだったりsetだったら問題にもならないのですが、linked listならではのコードを書く必要があります。

解答・解説

誤答

各ノードを走査するための変数current_nodeを定義し、current_nodeを動かしながらvalを取り除いていくと考えます。

と、ここまでは良いのですが以下のようにやってしまうと誤答です。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        
        current_node = head
        while current_node.next != None:
            if current_node.next.val == val:
                current_node.next = current_node.next.next
            else:
                current_node = current_node.next
                
        return head

これだと、1つ目の要素をチェックできないので
Inputが[1,2,6,3,4,5,6], val=6のときは良いですが
Inputが[1,2,6,3,4,5,6], val=1のときは正しい戻り値を返せません。

解法1

シンプルに1つ目の要素をチェックする処理を追加する、のが案1です。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        
        while head is not None and head.val == val:
            head = head.next
        
        current = head
        while current is not None:
            if current.next is not None and current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next
        
        return head

解法2

誤答のコードは1つ目の要素をチェックできないことが問題だったので、1つ目の要素の前にダミーのnodeを追加したlinked listを作ってやれば問題なくなる、と考えます。

そこで、dummy_headという変数を、ListNode(-1)とheadを結合させる形で作り、dummy_headの各nodeを走査します。

最後に返す値はdummy_head.nextである点に注意します（でないと、ダミーで追加したnodeも含めて返してしまう）。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        
        dummy_head = ListNode(-1)
        dummy_head.next = head
        
        current_node = dummy_head
        while current_node.next != None:
            if current_node.next.val == val:
                current_node.next = current_node.next.next
            else:
                current_node = current_node.next
                
        return dummy_head.next