プログラミングトレーニング(06/12/2021)

プログラミングトレーニング(06/12/2021)

競技プログラミングの練習メモです。

[LeetCode][Easy] 344. Reverse String


https://leetcode.com/problems/reverse-string/

簡単

class Solution:
    def reverseString(self, s: List[str]) -> None:
        l, r = 0, len(s) - 1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -= 1
        return s

[LeetCode][Medium] 430. Flatten a Multilevel Doubly Linked List


https://leetcode.com/problems/flatten-a-multilevel-doubly-linked-list/

普通に DFS の問題だけど、curr.child = None の処理を忘れると正解にならない。というか、不正解の場合のエラ〜メッセージが何のことか分からなくてハマった。

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head:
            return head
        
        stack = [head]
        prev = None
        while stack:
            curr = stack.pop()
            if prev:
                prev.next, curr.prev = curr, prev
            prev = curr
            if curr.next:
                stack.append(curr.next)
            if curr.child:
                stack.append(curr.child)
                curr.child = None
            
        return head

[LeetCode][Medium] 138. Copy List with Random Pointer


https://leetcode.com/problems/copy-list-with-random-pointer/

一発で解けたけど、Space O(N) なのと、あまり綺麗なコードではないな。。

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        hash_table_n1 = dict()
        hash_table_n2 = dict()
        
        if not head:
            return None

        n1 = head
        n2 = Node(0, None, None)
        n2_head = n2
        idx = 0
        while n1:
            n2.next = Node(n1.val, None, None)
            hash_table_n1[n1] = idx
            hash_table_n2[idx] = n2.next
            
            n1 = n1.next
            n2 = n2.next
            idx += 1

        n1 = head
        n2 = n2_head.next
        while n1:
            if n1.random:
                n2.random = hash_table_n2[hash_table_n1[n1.random]]

            n1 = n1.next
            n2 = n2.next
            
        return n2_head.next

回答見てお勉強。こんな感じでシンプルに解けるのか。

class Solution:
    def __init__(self):
        self.visited = {}

    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        
        if head in self.visited:
            return self.visited[head]
        
        node = Node(head.val, None, None)
        self.visited[head] = node
        
        node.next = self.copyRandomList(head.next)
        node.random = self.copyRandomList(head.random)
        
        return node

[LeetCode][Easy] 144. Binary Tree Preorder Traversal


https://leetcode.com/problems/binary-tree-preorder-traversal/

pre-order さえ理解していればあとは dfs するだけ。

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        self.dfs(root, ans)
        return ans
    
    def dfs(self, node, ans):
        if not node:
            return
        
        ans.append(node.val)
        self.dfs(node.left, ans)
        self.dfs(node.right, ans)

[LeetCode][Easy] 94. Binary Tree Inorder Traversal


https://leetcode.com/problems/binary-tree-inorder-traversal/

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        self.dfs(root, ans)
        return ans
    
    def dfs(self, node, ans):
        if not node:
            return

        self.dfs(node.left, ans)
        ans.append(node.val)
        self.dfs(node.right, ans)


See also