[Medium] Design

These problems may require you to implement a given interface of a class, and may involve using one or more data structures. These are great exercises to improve your data structure skills.

We recommend: Serialize and Deserialize Binary Tree and Insert Delete GetRandom O(1).

[1] 251. Flatten 2D Vector

My Answer 1: Accepted (Runtime: 76 ms - 87.54% / Memory Usage: 20 MB - 62.32%)

class Vector2D:

    def __init__(self, v: List[List[int]]):
        self.data = []
        
        for i in range(len(v)):
            for j in range(len(v[i])):
                self.data.append(v[i][j])
                           
        self.pointer = 0

    def next(self) -> int:
        if self.pointer < len(self.data):
            self.pointer += 1
            return self.data[self.pointer-1]
        
        return #None

    def hasNext(self) -> bool:
        if self.pointer < len(self.data):
            return True
        else:
            return False

# Your Vector2D object will be instantiated and called as such:
# obj = Vector2D(v)
# param_1 = obj.next()
# param_2 = obj.hasNext()

그냥.. self.data 에 순서대로 저장하고 pointer 로 next 를 가리키도록

if self.pointer < len(self.data): 면 더이상 next 가 없다는 의미

[2] 297. Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Hard... 형이 왜 거기서 나와...?

My Answer 1: Accepted (Runtime: 128 ms - 55.01% / Memory Usage: 18.9 MB - 42.93%)

# 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 serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        data = ""
        
        # level-order 로 data 에 저장
        queue = [root]
        while queue:
            r = queue.pop(0)
            
            # r 이 null 이 아니면 그대로 저장
            if r:
                data += str(r.val) + ","
                queue.append(r.left)
                queue.append(r.right)
            
            # r 이 null 이면 null 을 알려주기 위해 쉼표만 저장
            else:
                data += ","
        
        return data

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        # 쉼표 기준으로 data split
        data = data.split(',')
        data.pop()      # 맨 마지막에 쉼표가 하나 더 붙어서 제거해주기
        
        # case: [] 처리
        if data[0] == "":
            return
        
        # 맨 처음값으로 루트 생성
        result = TreeNode(data[0])
        queue = [result]
        i = 1
        
        # level-order 로 left, right 채워주기
        while queue:
            r = queue.pop(0)
            
            # r 이 존재하고 data[i] 가 존재할 때 append
            
            if i < len(data) and r:	# left
                if data[i]:
                    r.left = TreeNode(data[i])
                    queue.append(r.left)
            i += 1
            
            if i < len(data) and r:	#right
                if data[i]:
                    r.right = TreeNode(data[i])
                    queue.append(r.right)
            i += 1
            
        return result

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

이거 전에 아예 뭔소린지 몰랐던 문제로 기억하는데 이젠 풀 수 있게 됐네요~~^^

[3] 380. Insert Delete GetRandom O(1)

Implement the RandomizedSet class:

• bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
• bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
• int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

Follow up: Could you implement the functions of the class with each function works in average O(1) time?

My Answer 1: Accepted (Runtime: 440 ms - 10.45% / Memory Usage: 18.7 MB - 6.95%)

import random

class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = set()

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val in self.data:
            return False
        
        self.data.add(val)
        return True

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val not in self.data:
            return False
        
        self.data.remove(val)
        return True

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        result = random.sample(self.data, 1)
        return result[0]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

이건 쫌 쉬웠네요

리스트보단 빠르지 않을까 해서 set() 이용 (별 차이 없음)

존재 여부 확인해서 insert, remove

random.sample 이용해서 1개만 random 으로 추출

시간 복잡도 높이려면

self.data_map = {} # dictionary, aka map, aka hashtable, aka hashmap
self.data = [] # list aka array

두개를 만들어서 사용하면 됨
val 값이 존재하는지 data_map 에서 확인하고 random.choice(self.data) 하면 끗

• 그냥 self.data = [] 만 사용하면 효과가 없음 => in 에서 뭔가.. 느린 듯

[4] 348. Design Tic-Tac-Toe

My Answer 1: Accepted (Runtime: 96 ms / Memory Usage: 16.9 MB)

class TicTacToe:

    def __init__(self, n: int):
        """
        Initialize your data structure here.
        """
        self.data = [["" for _ in range(n)] for _ in range(n)]

    def move(self, row: int, col: int, player: int) -> int:
        """
        Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins.
        """
        draw = ""
        
        if player == 1:
            draw = "X"
        else:
            draw = "O"

        # 그려주기
        self.data[row][col] = draw

        length = len(self.data)
        ans = 0
        
        for i in range(length):
            if draw != self.data[i][col]:
                ans = 0
                break
            else:
                ans = player

        if ans != 0:
            return ans

        for j in range(length):
            if draw != self.data[row][j]:
                ans = 0
                break
            else:
                ans = player

        if ans != 0:
            return ans

        # (row, col) 이 대각선에 있는 경우
        if row == col or row+col == length-1:
            for i in range(length):
                if draw != self.data[i][i]:
                    ans = 0
                    break
                else:
                    ans = player

            if ans != 0:
                return ans

            for i in range(length):
                if draw != self.data[i][length-i-1]:
                    ans = 0
                    break
                else:
                    ans = player
                    
        return ans
        


# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)

data 라는 n*n 크기의 리스트를 만들어주고

입력받은 (i,j) 에 player 번호에 맞는 값으로 그려줌 => self.data[row][col] = draw

(i,j) 가 속한 row 와 col 들을 봐주고
(i,j) 가 대각선 라인에 있는 경우는 대각선까지 확인 후 ans return

생각보다 디자인 ㄱㅊ은듯

다 풀었다~~