Scribbling

고립된 O를 X로 만드는 문제이다. "고립된"은 board의 경계와 이어지지 않는 O들이다. 고로 경계의 O와 이어진 O들을 제외하고, 모두 X 처리해준다. from collections import deque class Solution: def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ dy = [0, 1, 0, -1] dx = [1, 0, -1, 0] island = set() m, n = len(board), len(board[0]) for i in range(m): for j in range(n): if board[i][j] == "O": islan..

DFS로 푼다. # 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 sumNumbers(self, root: Optional[TreeNode]) -> int: self.sum = 0 self.dfs(root, '0') return self.sum def dfs(self, node, num: str): if node.left == None and node.right == None: self.sum += int(num + str(nod..

O(N) 알고리즘. class Solution: def longestConsecutive(self, nums: List[int]) -> int: longest = 0 nums = set(nums) for num in nums: if num - 1 not in nums: cnt = 1 while num + 1 in nums: num += 1 cnt += 1 longest = max(longest, cnt) return longest class Solution: def longestConsecutive(self, nums: List[int]) -> int: numSet = set(nums) longest = 0 while nums: cnt = 1 l = r = nums.pop() numSet.discard(..

아래 문제와 거의 같다. https://focalpoint.tistory.com/101 LeetCode: 126. Word Ladder II - 시바견의 끄적임 개인적으로 어려웠던 문제... A. 내가 푼 방법 일단 내가 푼 방법은 아래와 같다. 1) 모든 word에 대해 graph를 그린다. (word간 글자가 1개만 차이나는 경우 연결) 2) 다익스트라 알고리즘으로 최단 경 focalpoint.tistory.com class Solution: def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int: wordSet = set(wordList) wordSet.discard(beginWord) if endWord no..

At each node, we have to do two jobs. First: update the global sum with the path going through node, node's left child, and node's right child Second: either choose node's left child or node's right child to return a partial path than can be connected to current node's parent - here we can't choose both left child and right child because if we choose both of them, that path can't be connected to..

LeetCode에서 푼 문제 중 가장 어려웠다... 당연히 빡대가리 내 머리로는 못 풀었고, 다른 사람 풀이 보고 이해하는 데에도 한참 걸렸다. DP로 풀어야하는데, 점화식은 아래와 같다. O(NK) Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/655837/Python-Very-Detailed-Explanation-with-thought-process-DP 위 점화식에 대한 예제이다. P = [3, 3, 5, 0 0, 3, 1, 4], K = 3 class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: if not prices: return..

class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ n = len(prices) leftprofit, rightprofit = [0] * n, [0] * n leftmin = prices[0] for i in range(1, n): price = prices[i] leftmin = min(leftmin, price) leftprofit[i] = max(leftprofit[i-1], price - leftmin) rightmax = prices[-1] for i in range(n-2, -1, -1): price = prices[i] rightmax = max(rightmax, pric..

class Solution: def maxProfit(self, prices: List[int]) -> int: profit, prev = 0, prices[0] for i in range(1, len(prices)): if prices[i] >= prev: profit += prices[i] - prev prev = prices[i] return profit

전형적인 DP 문제 class Solution: def minimumTotal(self, triangle: List[List[int]]) -> int: dp = [[0] * (i+1) for i in range(len(triangle))] dp[0][0] = triangle[0][0] for i in range(1, len(triangle)): dp[i][0] = dp[i-1][0] + triangle[i][0] for j in range(1, i): dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] dp[i][-1] = dp[i-1][-1] + triangle[i][-1] return min(dp[len(triangle)-1])

""" # Definition for a Node. class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val = val self.left = left self.right = right self.next = next """ class Solution: def connect(self, root: 'Node') -> 'Node': self.helper(root) return root def helper(self, node): if not node: return leftmost, prev = None, None cur = node while cur: if c..