Populating Next Right Pointers in Each Node - LeetCode 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 이진트리가 주어진다. 이진트리의 동일한 레벨을 왼쪽에서 오른쪽으로 연결하는 문제다. 1. BFS from collections import deque, defaultdict class Solution: def connect(self, root: 'Node') -> 'Node': q = deque([(root, 0)]) dict1 = d..

Binary Tree Zigzag Level Order Traversal - LeetCode 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 이진트리가 주어진다. root level을 0이라고 했을 때 0, 2, 4, 6,.... 레벨의 노드는 왼쪽에서 오른쪽으로 순회하고, 1, 3, 5, 7,... 레벨의 노드는 오른쪽에서 왼쪽으로 순회한 결과를 반환하는 문제다. 1. Deque, BFS를 사용한 풀이 from typing import * from collections impo..

Valid Sudoku - LeetCode 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 스도쿠 판이 주어진다. 빈칸을 제외하고 현재 채워진 숫자가 스도쿠에 적합한지를 반환하는 문제다. 1. 뇌를 비운 풀이 class Solution: def isValidSudoku(self, board): for i in range(len(board)): board[i] = list(map(lambda x: int(x) if x.isdigit() else 0, board[i])) rows, ..

Palindrome Partitioning - LeetCode 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 문자열이 입력된다. 입력된 문자열의 연속된 부분 문자열이 모두 Palindrome(회문, 앞에서 읽어도, 뒤에서 읽어도 같은 문자열)이 되게 하는 그 결과 목록을 반환하는 문제다. 1. DP + DFS from typing import * class Solution: def partition(self, s: str) -> List[List[str]]: answers = ..

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode 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 이진트리의 PreOrder 순회 결과와 InOrder 순회 결과를 입력하면 이진트리를 복원해서 반환하는 문제다. 1. 4개의 index 값을 이용한 DFS from typing import * class Solution: def buildTree(self, preorder: List[int], inorder: ..

def lower_bound(input_list, target_value): if not input_list: return 0 lo, hi = 0, len(input_list) while lo < hi: mid = (lo + hi) // 2 if input_list[mid] < target_value: lo = mid + 1 else: hi = mid return lo def upper_bound(input_list, target_value): if not input_list: return 0 lo, hi = 0, len(input_list) while lo < hi: mid = (lo + hi) // 2 if target_value < input_list[mid]: hi = mid else: lo = ..