티스토리

개발로 개발

검색하기

블로그 홈

개발로 개발

gaebalogaebal.tistory.com/m

위대한먼지 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

[LeetCode 75] 933. Number of Recent Calls Solution) class RecentCounter: def __init__(self): # This deque will save requests that are called in ping() self.requests = collections.deque() def ping(self, t: int) -> int: # First append the input t self.requests.append(t) # This while loop will pop requests that are not in the range # of the past 3000 milliseconds while not (t-3000 공감수 0 댓글수 0 2023. 11. 9.
[Top Interview 150] 210. Course Schedule II Solution)class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: # preDict is a dict that saves {crs : [prerequiste courses]} preDict = {i:[] for i in range(numCourses)} # Fills up preDict according to the given prerequisites for crs, pre in prerequisites: preDict[crs].append(pre) # visit is a set of vertices that are added to res # path is a set of ver.. 공감수 0 댓글수 0 2023. 10. 13.
[Top Interview 150] 207. Course Schedule Solution)class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: # preMap will save {course : [prerequisites]} # visitSet will save courses that were visited while DFS preMap, visitSet = collections.defaultdict(list), set() # Set up preMap according to the given prerequisites for crs, pre in prerequisites: preMap[crs].append(pre) # Helper function that will .. 공감수 0 댓글수 0 2023. 10. 12.
[Top Interview 150] 399. Evaluate Division Solution) class Solution: def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]: # dict of {key : []} # The list will contain lists of [destination, values needed to reach] adj = collections.defaultdict(list) # Example 1) {a : [[b, 2.0]], b: [[a, 0.5], [c, 3.0]], ...} # a -> b costs 2.0 # b -> c costs 3.0 # Make sure to save a -> b and t.. 공감수 0 댓글수 0 2023. 10. 6.
[Top Interview 150] 133. Clone Graph Solution)class Solution: def cloneGraph(self, node: Optional['Node']) -> Optional['Node']: # Base Case if not node: return # Dict that will save {original nodes : copied nodes} # It's used to check if we've already created a certain node oldToNew = {} # Recursively copy nodes and connect them as neighbors def dfs(node): # Checking if the current node is already copied if node in oldToNew: return.. 공감수 0 댓글수 0 2023. 10. 5.
[Top Interview 150] 130. Surrounded Regions Solution)class Solution: def solve(self, board: List[List[str]]) -> None: # rows and cols are the number of rows and columns of board # visit is a set of positions of "O" that have been visited before rows, cols, visit = len(board), len(board[0]), set() # Modifies board using BFS method def bfs(r, c): # A list of directions including itself directions = [[0,0], [0,1], [0,-1], [1,0], [-1,0]] # q .. 공감수 0 댓글수 0 2023. 9. 27.
[Top Interview 150] 200. Number of Islands Solution) class Solution: def numIslands(self, grid: List[List[str]]) -> int: # rows, cols are the actual number of rows and columns of grid # visit will save 1's that were visited when discovering islands # islands will save the number of islands rows, cols = len(grid), len(grid[0]) visit = set() islands = 0 # Helper function bfs() will BFS from the current position # (r, c) to discover the ent.. 공감수 0 댓글수 1 2023. 9. 26.
[Top Interview 150] 230. Kth Smallest Element in a BST Solution)class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: # A list that will save values of nodes in an increasing order res = [] # Helper function that will save values to res def dfs(root): # Base Case if not root: return # Append vals in inorder traversal, which gives us # the increasing order dfs(root.left) # Mark res as nonlocal for us to use it # in an inner .. 공감수 0 댓글수 0 2023. 9. 22.
[Top Interview 150] 98. Validate Binary Search Tree Solution)class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: # Variable prev will save a value of a previous node # Variable check will save a bool of whether this BST is valid prev = -2**31 - 1 check = True # Helper function that compares previous node value # with current ndoe value to validates BST def compare(root): # Marking prev and check as nonlocal to use them # in th.. 공감수 0 댓글수 0 2023. 9. 22.
[Top Interview 150] 103. Binary Tree Zigzag Level Order Traversal Solution) class Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: # Base Case if not root: return [] # zig is a list that saves nodes from right to left # zag is a list that saves nodes from left to right # res is a final list that will have zigzagged nodes' vals zig, zag, res = [], [], [] # Initialization zig.append(root) # Iterate the entire tree while zig or z.. 공감수 0 댓글수 0 2023. 9. 20.
[Top Interview 150] 102. Binary Tree Level Order Traversal Solution) class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: # res will be returned at the end # queue will save nodes level by level res, queue = [], deque() if root: queue.append(root) # Iterate tree while queue is not empty while queue: # This temporary list will save values of nodes in each level lv = [] # This for-loop will append the current level nodes' val.. 공감수 0 댓글수 0 2023. 9. 19.
[Top Interview 150] 199. Binary Tree Right Side View Solution)class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: # Base Case if not root: return None # queue will store nodes in each level # res will save values of nodes on the right side of tree queue, res = deque(), [] queue.append(root) while queue: # Append the value of nodes on the right side to res res.append(queue[0].val) for i in range(len(queue)): # Pop nodes .. 공감수 0 댓글수 0 2023. 9. 15.
[Top Interview 150] 236. Lowest Common Ancestor of a Binary Tree Solution) class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': # Base Case if not root or root == p or root == q: return root # Recursive Call l = self.lowestCommonAncestor(root.left, p, q) r = self.lowestCommonAncestor(root.right, p, q) # If p and q are descendants of a certain node # return that node if l and r: return root # If p or q i.. 공감수 0 댓글수 1 2023. 9. 14.
[Top Interview 150] 173. Binary Search Tree Iterator Solution) class BSTIterator: def __init__(self, root: Optional[TreeNode]): # arr stores h nodes (h = height of the tree) self.arr = [] # Helper function adds nodes in root => leftmost leaf branch self.findNextNodes(root) def next(self) -> int: # nextNode is the smallest number node nextNode = self.arr.pop() # If nextNode has a right child, we add nodes from # right child => leftmost child to arr.. 공감수 0 댓글수 0 2023. 9. 13.
[Top Interview 150] 129. Sum Root to Leaf Numbers Solution)class Solution: def sumNumbers(self, root: Optional[TreeNode]) -> int: # res will save the sum of all root-to-leaf numbers res = 0 # finds root-to-leaf numbers and add them to res def helper(root, cur): # Base Case if not root: return # If leaf, add the current number to res if not root.left and not root.right: # Make sure to mark res as nonlocal for the # function to recognize nonlocal.. 공감수 0 댓글수 0 2023. 9. 8.
[Top Interview 150] 114. Flatten Binary Tree to Linked List Solution)class Solution: def flatten(self, root: Optional[TreeNode]) -> None: # Base Case if not root: return # Initialization arr = [] # Helper func that adds nodes to arr in preorder def preorder(root): if not root: return None arr.append(root) preorder(root.left) preorder(root.right) preorder(root) # Connect nodes through right attribute cur = root for i in range(1, len(arr)): cur.left = None.. 공감수 0 댓글수 0 2023. 9. 7.
[Top Interview 150] 117. Populating Next Right Pointers in Each Node II Solutionclass Solution: def connect(self, root: 'Node') -> 'Node': # Base Case if not root: return # Initialization parent, children = deque(), deque() parent.append(root) while parent: # Get the children of the nodes in a previous level while parent: cur = parent.popleft() if cur.left: children.append(cur.left) if cur.right: children.append(cur.right) # Connect the children through next attribu.. 공감수 0 댓글수 0 2023. 9. 6.
[Top Interview 150] 106. Construct Binary Tree from Inorder and Postorder Traver Solution)class Solution: def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: # Base Case if not inorder or not postorder: return None # root is always the -1st element of postorder root = TreeNode(postorder[-1]) # Find the index of root in inorder mid = inorder.index(postorder[-1]) # Recursive Calls: # Adjust the ranges of left/right subtrees using mid root.left .. 공감수 0 댓글수 0 2023. 9. 5.
[Top Interview 150] 105. Construct Binary Tree from Preorder and Inorder Travers Solution) class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: # Base Case if not preorder or not inorder: return None # Root of a tree root = TreeNode(preorder[0]) # Index of root to distinguish left/right subtrees mid = inorder.index(preorder[0]) # Recursive calls to build left/right subtrees using mid root.left = self.buildTree(preorder[1:mid+1],.. 공감수 0 댓글수 0 2023. 9. 4.
[Top Interview 150] 146. LRU Cache Solution) # Doubly Linked List class ListNode: def __init__(self, key=0, val=0, nextt=None, prev=None): self.key = key self.val = val self.next = nextt self.prev = prev class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.storage = {} self.root = ListNode(0) self.tail = self.root def put(self, key: int, value: int) -> None: newNode = ListNode(key, value) self.append(n.. 공감수 0 댓글수 0 2023. 9. 3.
[Top Interview 150] 86. Partition List Solution)class Solution: def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]: # under is a list with nodes whose values are under x # over is a list with nodes whose values are over x under, over = ListNode(0), ListNode(0) dUnder, dOver = under, over while head: # If the cur node's value is greater than x connect to over if head.val >= x: over.next = head over = over.next.. 공감수 0 댓글수 0 2023. 8. 31.
[Top Interview 150] 61. Rotate List Solution) class Solution: def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: # Base Case if not head: return None # Two Pointers slow, fast = head, head # Find length and send fast to the end of the list length = 1 while fast.next: fast = fast.next length += 1 fast.next = head # Reduce k and move slow k %= length for i in range(length-k-1): slow = slow.next # Connect .. 공감수 0 댓글수 0 2023. 8. 30.
[Top Interview 150] 82. Remove Duplicates from Sorted List II Solution)class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: # Base Case if not head: return None # Dummy Node dummy = ListNode(0, head) # dup's initial value is a value that # a node cannot have in this problem prev, cur = dummy, head dup = -101 while cur.next: # If a duplicate is found, save that value if cur.val == cur.next.val: dup = cur.val # If the c.. 공감수 0 댓글수 0 2023. 8. 29.
[Top Interveiw 150] 19. Remove Nth Node from End of List Solution) class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: # Dummy node that allows us to access head dummy = ListNode(0, head) # Dictionary that saves {index:node} indexDic = {0:dummy} # Save {index:node} to indexDic nodeIndex = 1 while head: indexDic[nodeIndex] = head head = head.next nodeIndex += 1 # Find the index whose node has to be remove.. 공감수 0 댓글수 0 2023. 8. 28.
[Top Interview 150] 92. Reverse Linked List II Solution)class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: # cur iterates the linked list # checkpoint is the node right before the reversal cur, checkpoint = head, head # Move cur to a node where the reversal starts for _ in range(left - 1): checkpoint = cur cur = cur.next # reverse is the head of reversed linked list # tail is the .. 공감수 0 댓글수 0 2023. 8. 25.
[Top Interview 150] 138. Copy List with Random Pointer Solution) class Solution: def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': # Base Case if not head: return None # Checkpoints that will save the heads of each linked list original = head root = Node(head.val) # Dictionary that will save {original node : copied node} # Those paired nodes have the same value. dic = {head:root} # Deepcopy each node and link them # without conne.. 공감수 0 댓글수 0 2023. 8. 24.
[Top Interview 150] 150. Evaluate Reverse Polish Notation Solution) class Solution: def evalRPN(self, tokens: List[str]) -> int: # Initialization stack = [] for tk in tokens: if tk == "+": stack.append(stack.pop() + stack.pop()) elif tk == "*": stack.append(stack.pop() * stack.pop()) # Careful with the order of operand elif tk == "-": stack.append(-stack.pop() + stack.pop()) # Careful with the order of operand and floor division elif tk == "/": right, .. 공감수 0 댓글수 0 2023. 8. 23.
[Top Interview 150] 155. Min Stack Solution) class MinStack: def __init__(self): self.stack = [] self.minVal = float('inf') def push(self, val: int) -> None: # Append a tuple in a form of (val, previous minVal) self.stack.append((val, self.minVal)) # Update minVal if need to self.minVal = min(self.minVal, val) def pop(self) -> None: # When we pop, we might pop a tuple that has a value of minVal # so we update minVal to a previous.. 공감수 0 댓글수 0 2023. 8. 22.
[Top Interview 150] 71. Simplify Path Solution) class Solution: def simplifyPath(self, path: str) -> str: # Split so that we only have the directories path = path.split('/') # res will save canonical path res = [] for directory in path: # Need to go to the directory up a level so we pop if directory == "..": if res: res.pop() # We're still in the current directory so we don't do anything elif directory == '.': continue # Append dire.. 공감수 0 댓글수 0 2023. 8. 21.
[Top Interview 150] 452. Minimum Number of Arrows to Burst Balloons Solution) class Solution: def findMinArrowShots(self, points: List[List[int]]) -> int: # Initialization points.sort() res = [points[0]] for start, end in points[1:]: # If the cur interval and prev interval overlap # find the part that only overlaps with no leftover if start int: points.sort() res = [points[0]] for start, end in points[1:]: if start 공감수 0 댓글수 0 2023. 8. 19.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.