Scribbling

Heapq만을 사용한 Priority Queue의 Time Complexity는 아래와 같다. Find max/min - O(1) Insert - O(logN) Remove - O(N) Remove Operation에 Linear Time이 필요하다는 것이 아쉽다. 이를 해결하기 위한 Custom Priority Queue를 만들었다. 이는 두 개의 Priority Queue를 사용하는 방식이다. 하나의 Queue는 원래 목적인 max/min heap로 사용하고, 나머지 하나의 queue를 쓰레기통으로 사용한다. Time Complexity는 아래와 같다. Find max/min - O(1) Insert - O(logN) Remove - O(logN) 다른 연산은 그다지 어렵지 않으니 Remove 연산만..

아래 너튜버분께 매번 배우게 되는 것 같다. 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 ..