Scribbling

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..

class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: self.wordDict = set(wordDict) self.ret = [] self.dfs(s, []) return self.ret def dfs(self, s, path): if not s: self.ret.append(' '.join(path)) return for word in self.wordDict: k = len(word) if s[:k] == word: self.dfs(s[k:], path+[word])

단어를 분해하거나 단어에서 단어를 찾는 문제를 다룰 때 가장 먼저 해볼만한 접근은, 분해 대상 단어를 한글짜 단위로 확인해가면서 완전탐색하는 것이다. 아래는 완전 탐색 코드이다. class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: self.wordDict = set(wordDict) return self.dfs(s) def dfs(self, s): if not s: return True for i in range(1, len(s)+1): if s[:i] in self.wordDict: if self.dfs(s[i:]): return True return False 제출해보면...? 타임 아웃이다. 생각해보면 dfs의 변수로 ..

O(N) Time, O(N) Memory """ # Definition for a Node. class Node: def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None): self.val = int(x) self.next = next self.random = random """ class Solution: def copyRandomList(self, head: 'Node') -> 'Node': if not head: return cur, dic = head, {} while cur: dic[cur] = Node(x=cur.val) cur = cur.next cur = head while cur: if cur.next: dic[cur]..

면접 형식의 문제여서 문제를 맞추는 것은 어렵지 않다. 다만 어느정도로 효율적인 알고리즘(시간 및 메모리 측면)을 구현하는지가 관건이다. 가장 간단한 방법은 모든 숫자를 저장하고, 중앙값 search시마다 정렬하는 방법이다. add: O(1) find: O(nlogn) 위의 이유로 비효율적이다. class MedianFinder: def __init__(self): self.arr = [] self.count = 0 def addNum(self, num: int) -> None: self.arr.append(num) self.count += 1 def findMedian(self) -> float: self.arr.sort() if self.count % 2 == 0: return (self.arr[se..

빈도를 기억하기 위한 hashmap을 사용하자. from collections import defaultdict class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: dic = defaultdict(int) for num in nums: dic[num] += 1 temp = [] for key, val in dic.items(): temp.append([val, key]) temp.sort(key=lambda x: -x[0]) temp = temp[:k] return [t[1] for t in temp]

매우 어려운 문제였다. 다만 아래 문제를 먼저 풀면, 이 문제도 쉽게 풀 수 있다. https://focalpoint.tistory.com/179 LeetCode: 300. Longest Increasing Subsequence - 시바견의 끄적임 1. 가장 간단한 DP 형태 O(N**2)이다. class Solution: def lengthOfLIS(self, nums: List[int]) -> int: dp = [0] * len(nums) dp[0] = 1 for i in range(1, len(nums)): temp = -1 j = i - 1 while j >= 0: if n.. focalpoint.tistory.com from bisect import bisect_left class Solutio..