Scribbling

가장 먼저 떠오른 방법은 Priority Queue를 사용하는 것. Time Complexity: O(N*logN) import heapq class PriorityQueue: def __init__(self): self.pq = [] self.removals = [] def insert(self, elem): heapq.heappush(self.pq, -elem) def gettop(self): return -self.pq[0] def remove(self, elem): if elem == -self.pq[0]: heapq.heappop(self.pq) while self.removals and self.pq[0] == self.removals[0]: heapq.heappop(self.pq) heapq..

아래 너튜버분께 매번 배우게 되는 것 같다. https://www.youtube.com/watch?v=GSBLe8cKu0s&t=3s 아래는 위의 영상에 나온 알고리즘의 파이썬 코드이다. from functools import cmp_to_key import heapq class Solution: def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]: # [loc, height, isEnd] points = [] for l, r, h in buildings: points.append([l, h, 0]) points.append([r, h, 1]) def compare(p1, p2): if p1[0] != p2[0]: return p1[0]..

Iterative가 빠르다. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: cur, prv = head, None while cur: nxt = cur.next cur.next = prv prv = cur cur = nxt return prv

class Solution: def isHappy(self, n: int) -> bool: def calc(x): ret = 0 while x > 0: ret += (x % 10)**2 x //= 10 return ret numSet = set([n]) x = n while True: x = calc(x) if x == 1: return True if x in numSet: return False numSet.add(x)

class Solution: def hammingWeight(self, n: int) -> int: ret = 0 for i in range(32): ret += n & 1 n >>= 1 return ret

class Solution: def titleToNumber(self, columnTitle: str) -> int: ret = 0 order = 1 for char in columnTitle[::-1]: ret += order * (ord(char) - 64) order *= 26 return ret

class Solution: def isPalindrome(self, s: str) -> bool: s = s.lower().strip() if not s: return True l, r = 0, len(s) - 1 while l < r: if not s[l].isalnum(): l += 1 continue if not s[r].isalnum(): r -= 1 continue if s[l] != s[r]: return False l += 1 r -= 1 return True

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: return self.isMirror(root.left, root.right) def isMirror(self, left, right): if left == None and right == None: return True if left == None or right == None: ret..

코드가 너무 복잡하다. # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': self.ret = None self.dfs(root, p, q) return self.ret def dfs(self, node, p, q): if node == None: return None l = self.dfs(node.left, p, q) if..

BST이기 때문에 Inorder-Traverse하면 된다. K번째 원소를 찾으면 순회를 중단한다. 때문에 O(K)이다. # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: self.ret = 0 self.k = k self.traverse(root) return self.ret # returns whether traverse ..