Scribbling

어렵다... Greedy한 접근법이 필요하다. 내 머리론 못 풀었고, 아래 풀이를 바탕으로 코드를 작성했다. https://leetcode.com/problems/binary-tree-cameras/discuss/211180/JavaC%2B%2BPython-Greedy-DFS [Java/C++/Python] Greedy DFS - LeetCode Discuss Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 핵심은 아래와 같다. - Leaf Node에 카메라를 둘 이유가 전혀 없..

개인적으론 정말 정말 어렵다... 아래 선생님께서 매우 친절하게 잘 알려주신다... https://www.youtube.com/watch?v=LPFhl65R7ww&t=641s 핵심을 정리하면 아래와 같다. - nums1과 nums2 중 길이가 작은 리스트에 대해 binary search를 한다. - nums1과 nums2를 partition 하되, nums1의 left partition과 nums2의 left partition은 전체 길이의 절반 혹은 절반 + 1이 되도록 partition한다. 즉, nums1의 partition p1이 결정되면, p2도 자동으로 결정된다. p2 = (m + n + 1) // 2 - p1 - p1이 0 혹은 m이 되는 경우의 corner case를 처리한다. p1이 0이..

오늘 도둑은 binary tree를 털고 있다. # 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 rob(self, root: Optional[TreeNode]) -> int: a, b = self.dfs(root) return max(a, b) def dfs(self, node): if not node.left and not node.right: return 0, node.val if node.left and node.right..

O(N*logK) Time Complexity Solution using heap. class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: import heapq h = [] for num in nums: if len(h) < k: heapq.heappush(h, num) else: heapq.heappush(h, num) heapq.heappop(h) return h[0] A better approach is to quick selection, runs within O(N) time on average. But this runs with O(N) memory. import random class Solution: def fin..

class TrieNode: def __init__(self): self.children = {} self.endFlag = False class Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str) -> None: node = self.root for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] node.endFlag = True def search(self, word: str) -> bool: node = self.root for char in word: if char not i..

class Solution: def singleNumber(self, nums: List[int]) -> int: num = nums[0] for i in range(1, len(nums)): num ^= nums[i] return num

단순 구현 문제로 생각했는데, 시간 초과가 발생한다. 메모리를 더 써서 시간을 줄여야 한다. class Solution: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: m, n = len(board), len(board[0]) ret = [] for word in words: found_flag = False for i in range(m): for j in range(n): if board[i][j] == word[0]: visited = [[False] * n for _ in range(m)] visited[i][j] = True if self.dfs(board, visited, i, j, word[1:]): r..

위상 정렬 문제다. result의 길이를 통해 위상 정렬 성공 여부를 파악 가능하다. class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: indegrees = [0] * numCourses graph = [[] for _ in range(numCourses)] for v, u in prerequisites: graph[u].append(v) indegrees[v] += 1 ret = [] q = [] for node, indegree in enumerate(indegrees): if indegree == 0: q.append(node) while q: u = q.pop() ret...

척보면 binary search 문제이다. class Solution: def shipWithinDays(self, weights: List[int], days: int) -> int: max_capacity = 0 for w in weights: max_capacity += w ret = max_capacity l, r = 0, max_capacity while l capacity: num_days += 1 tempsum = w return (num_days

"Eratosthenes Algorithm"을 사용한다. class Solution: def countPrimes(self, n: int) -> int: if n