Scribbling

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

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 nums[j] < nums[i]: temp = max(temp, dp[j]) j -= 1 if temp != -1: dp[i] = temp + 1 else: dp[i] = 1 return max(dp) O(N**2)답게 빠르지 않다. 개선을 해보자. 2. LIS 알고리즘 (1)의 알고리즘은 하나의 숫자에 대해 계산함에 있어 이전에 나온 모든 숫자를 다 조사한다. 그러다보니 ..

1. Bottom-up Solution + predefining palindromic matrix class Solution: def minCut(self, s: str) -> int: dp = self.build_palindrome(s) n = len(s) self.cut = [2002] * n for end in range(n): if dp[0][end]: self.cut[end] = 0 continue for start in range(1, end+1): if dp[start][end]: self.cut[end] = min(self.cut[end], self.cut[start-1] + 1) return self.cut[-1] def build_palindrome(self, word): n = len..

class Solution: def partition(self, s: str) -> List[List[str]]: self.ret = [] self.dfs(s, []) return self.ret def dfs(self, s, path): if not s: self.ret.append(path) return for i in range(1, len(s)+1): first, second = s[:i], s[i:] if self.is_Palindromic(first): self.dfs(second, path+[first]) def is_Palindromic(self, s): return s == s[::-1]