23.04.08 Today’s Leetcode

33. Clone Graph (medium)

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node: return node
        
        q, clones = deque([node]), {node.val: Node(node.val, [])}
        while q:
            cur = q.popleft() 
            cur_clone = clones[cur.val]            

            for ngbr in cur.neighbors:
                if ngbr.val not in clones:
                    clones[ngbr.val] = Node(ngbr.val, [])
                    q.append(ngbr)
                    
                cur_clone.neighbors.append(clones[ngbr.val])
                
        return clones[node.val]

171. Excel Sheet Column Number (easy)

class Solution:
    def titleToNumber(self, columnTitle: str) -> int:
        res = 0
        for char in columnTitle:
            res *= 26
            res += ord(char) - ord('A') + 1
        return res

297. Serialize and Deserialize Binary Tree (hard)

preorder, inorder 두 개의 데이터를 저장해서 구현할 수 도 잇을것 같다.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:


    def height(self, root):
        if not root:
            return 0
        return 1 + max(self.height(root.left), self.height(root.right))

    def serialize(self, root):
        h = self.height(root)
        data = ['#'] * (2 ** h + 1)
        q = deque()
        q.append([root, 1])
        while q:
            node, pos = q.popleft()
            if node:
                data[pos] = str(node.val)
                q.append([node.left, pos * 2])
                q.append([node.right, pos * 2 + 1])
        # print(','.join(data))
        return ','.join(data)
        
    def deserialize(self, data):
        data = data.split(',')
        n = len(data)
        if n == 1:
            return None
        d = defaultdict(None)
        print(data)
        for i in range(n - 1, 0, -1):
            if data[i] != '#':
                d[i] = TreeNode(int(data[i]))
                if i * 2 < n: 
                    d[i].left = d[i * 2]
                if i * 2 + 1 < n: 
                    d[i].right = d[i * 2 + 1]
            else:
                d[i] = None
        # print(d)
        return d[1]
        

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

324. Wiggle Sort II (medium)

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()
        n = len(nums)
        l = n - 1
        k = (n + 1) // 2
        arr1 = nums[:k]
        arr2 = nums[k:]
        arr2.reverse()
        arr1.reverse()
        i1 = i2 = 0
        for i in range(n):
            if(i % 2==0):
                nums[i] = arr1[i1]
                i1 += 1
            else:
                nums[i] = arr2[i2]
                i2 += 1