Scribbling

Binary Search class Solution: def findPeakElement(self, nums: List[int]) -> int: INT_MAX = int(1e12) nums = [-INT_MAX] + nums + [-INT_MAX] def isPeak(idx): if nums[idx] > nums[idx-1] and nums[idx] > nums[idx+1]: return True return False left, right = 1, len(nums) - 2 while left nums[mid]: right = mid - 1 else: left = mid + 1

class MinStack: def __init__(self): self.stack = [] def push(self, val: int) -> None: if not self.stack: self.stack.append([val, val]) else: self.stack.append([val, min(val, self.stack[-1][1])]) def pop(self) -> None: self.stack.pop() def top(self) -> int: return self.stack[-1][0] def getMin(self) -> int: return self.stack[-1][1] # Your MinStack object will be instantiated and called as such: # ..

class Solution: def maxProduct(self, nums: List[int]) -> int: ret = -int(1e9) prod = 1 for num in nums: prod *= num ret = max(ret, prod) if num == 0: prod = 1 prod = 1 for i in range(len(nums)-1, -1, -1): prod *= nums[i] ret = max(ret, prod) if nums[i] == 0: prod = 1 return ret

class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: culsum = 0 for i in range(len(gas)): gas[i] -= cost[i] culsum += gas[i] if culsum < 0: return -1 start_idx, culsum = 0, 0 for i in range(len(gas)): culsum += gas[i] if culsum < 0: culsum = 0 start_idx = i + 1 return start_idx

stack을 사용 class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] predefined_tokens = ['+', '-', '*', '/'] operations = [lambda x, y : x + y, lambda x, y : x - y, lambda x, y : x * y, lambda x, y : int(x / y)] for token in tokens: if token in predefined_tokens: num2 = stack.pop() num1 = stack.pop() idx = predefined_tokens.index(token) stack.append(operations[idx](num1, num2)) els..

Relatively straightforward solution, O(N) time O(1) Memory. class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: numZero, prod, zeroidx = 0, 1, 0 for i, num in enumerate(nums): if num == 0: numZero += 1 zeroidx = i else: prod *= num if numZero >= 2: return [0] * len(nums) if numZero == 1: ret = [0] * len(nums) ret[zeroidx] = prod return ret # backward pass ret = [0] * len(n..

class Solution: def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]: m, n = len(mat), len(mat[0]) starting_points = [(0, i) for i in range(n)] + [(i, 0) for i in range(1, m)] for starting_point in starting_points: array = [] y, x = starting_point while y

DFS로 쉽게 풀 수 있다. class Solution: def minReorder(self, n: int, connections: List[List[int]]) -> int: self.graph = [[] for _ in range(n)] self.connections_set = set() for u, v in connections: self.graph[u].append(v) self.graph[v].append(u) self.connections_set.add((u, v)) visited = [False] * n self.ret = 0 self.dfs(0, visited) return self.ret def dfs(self, node, visited): visited[node] = True for v..

직선 찾기 문제 핵심은... 1) 실수 처리를 회피하기 위한 slope의 처리 2) map의 활용 from collections import defaultdict import math class Solution: def maxPoints(self, points: List[List[int]]) -> int: ret = 1 for i in range(len(points)): p1 = points[i] lineDict = defaultdict(lambda: 1) for j in range(len(points)): if i == j: continue p2 = points[j] dx = p2[0] - p1[0] dy = p2[1] - p1[1] if dx == 0: slope = (0, 1) elif dy == ..

Recursion을 이용한 방법 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reorderList(self, head: Optional[ListNode]) -> None: """ Do not return anything, modify head in-place instead. """ cur = head count = 0 while cur != None: count += 1 cur = cur.next new_head, _ = self.helper(head, count) return ne..