Scribbling

1. 초안 코드가 뭔가 복잡하다. 코드도 줄일겸 메모리를 O(1)으로 풀어보자. # 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 recoverTree(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ self.arr = [] self.helper(root) left, right = None, No..

n = 0 n = 1 n=2 n = 3 000 001 101 1100 100 1101 1001 1000 e.g. n=3 -> 100 + 1000, 101 + 1000, 001 + 1000, 000 + 1000 -> 역순 + 2의 n-1승 class Solution: def grayCode(self, n: int) -> List[int]: ret = [0] for i in range(n): ret += [x + pow(2, i) for x in reversed(ret)] return ret

개인적으로 어려웠던 문제... A. 내가 푼 방법 일단 내가 푼 방법은 아래와 같다. 1) 모든 word에 대해 graph를 그린다. (word간 글자가 1개만 차이나는 경우 연결) 2) 다익스트라 알고리즘으로 최단 경로를 찾는다. 나름 머리 써서 푼건데, 속도도 느리고 메모리 효율도 떨어져서 실망스럽다. import heapq class Solution: def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]: if endWord not in wordList: return [] if beginWord not in wordList: wordList.append(beginWord) s_idx = w..

간단하면서도 재밌는 문제 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]: smaller_train = ListNode() s_ptr = smaller_train bigger_train = ListNode() b_ptr = bigger_train cur = head while cur != None: if cur.val < x: s_ptr.next = cur s..

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head: return None new_head = ListNode() ptr = new_head reg, freq = head.val, 0 cur = head while cur != None: if reg != cur.val: if freq == 1: temp = ListNode(reg) ptr.n..

이 문제는 아래 문제와 상당히 유사하다. 33. Search in Rotated Sorted Array (https://leetcode.com/problems/search-in-rotated-sorted-array/description/) 실제 구현도 유사하지만, Time Complexity는 다른데 그 이유를 생각해보면 흥미롭다. class Solution: def search(self, nums: List[int], target: int) -> bool: left, right = 0, len(nums) - 1 while left

class Solution: def removeDuplicates(self, nums: List[int]) -> int: reg, freq = None, None k = 0 for i, num in enumerate(nums): # update reg & freq if reg != num: reg = num freq = 1 else: freq += 1 if freq

문제 링크: https://leetcode.com/problems/largest-rectangle-in-histogram/ O(N)만에 푸는 방법을 떠올리는 것은 매우 어렵다. 이 문제를 O(N)에 풀 수 있는 방법은 monotonic stack을 이용하는 것이다. Monotonic Stack이란 stack을 쌓되 stack 내부가 오름차순 혹은 내림차순으로 정렬되도록 쌓는 것이다. 이 문제에서 Monotonic Stack이 사용되는 이유는 다음과 같다. 왼쪽에서부터 오른쪽으로 가면서 블록이 하나씩 추가된다고 고려했을 때, 이전에 추가된 블록에 비해 현재 블록의 높이가 작다면, 이전 블록의 높이가 직사각형의 최대 높이가 된다. 아래 그림에서 높이 2의 블록 차례가 오면, 높이 5와 높이 6의 블록은 더 ..

어케풀었누... 1. 내 방법 A. 각 점으로부터 오른쪽으로 연결된 네모의 개수를 저장한다. 1 0 1 0 0 1 0 3 2 1 5 4 3 2 1 1 0 0 1 0 B. 모든 열에 대해서 최대 직사각형 넓이를 계산한다. class Solution: def maximalRectangle(self, matrix: List[List[str]]) -> int: if not matrix: return 0 n, m = len(matrix), len(matrix[0]) dp = [[0] * m for _ in range(n+1)] # table for i in range(n): j = m - 1 count = 1 while j >= 0: if matrix[i][j] == '0': dp[i][j] = 0 count =..

class Solution: def exist(self, board: List[List[str]], word: str) -> bool: n, m = len(board), len(board[0]) for i in range(n): for j in range(m): if self.dfs(board, i, j, word, 0): return True return False def dfs(self, board, y, x, word, k): if k == len(word): return True if y = len(board) or x = len(board[0]) or board[y][x] == '@': return False char = word[k] if board[y][x..