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
생각보다 디자인 ㄱㅊ은듯
다 풀었다~~
0개의 댓글
