gaki gaki

class Solution: def maxArea(self, height: List[int]) -> int: ret = 0 n = len(height) left = 0 right = n - 1 while (left < right): ret = max(ret, min(height[left], height[right]) * (right - left)) if (height[left]

import heapq arr = [0,2,40,112,11,1] heapq._heapify_max(arr); // max_heap 형태로 만들어줌 arr[0] 은 max 값. // 112 maxV = heapq._heapreplace_max(arr, value e.g.:120); // arr 에서 max 값을 삭제하고, value 를 넣어 max 힙으로 만듦 // maxV = 112, arr = [120, .....]

import heapq class Solution: def isPossible(self, target: List[int]) -> bool: heapq._heapify_max(target) s = sum(target) while (target[0] != 1): sub = s- target[0] if (sub >= target[0] or sub == 0): return False iterNum = max( ((target[0]-1) // sub),1) temp = target[0] - (sub * iterNum) if (temp < 1): return False v = heapq._heapreplace_max(target, temp) s = sum(target) return True

class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: ret = [] n = len(nums) nums = sorted(nums) def rec(length, subset, items): if (len(subset) == length): if ((subset) not in ret): ret.append((subset)) return ; if (items == []): return ; for i in range(len(items)): rec(length, subset + [items[i]], items[i+1:]) for length in range(n + 1): rec(length, [], nums[:]) return ..

from collections import Counter class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: C = Counter(p) length = len(p) n = len(s) left = 0 right = length - 1 Temp = Counter(s[left: right + 1]) ret = [] while (right < n): if (Temp == C): ret.append(left) if (right == n - 1): return ret Temp[s[left]] -= 1 left += 1 right += 1 Temp[s[right]] += 1

안녕하세요. gaki 입니다. 오늘은 가장 긴 펠렌드롬을 O(N) 의 시간복잡도로 찾을 수 있는 Manacher's 알고리즘에 대해서 이야기 해보겠습니다. 1. O(N^2) 으로 가장 긴 펠렌드롬 찾는 방법 2. Manacher's 알고리즘의 접근 방법 3. LeetCode 문제풀이 1. O(N^2) 으로 가장 긴 펠린드롬을 찾는 방법 먼저 Manacher's 알고리즘에 대해서 알아보기 전에, 이 알고리즘이 왜 유용한지에 대해서 설명해보겠습니다. babad 위와 같은 문자열이 있다고 가정해봅시다. 이 문자열에서 가장 긴 펠렌드롬을 찾으려면 어떻게 해야할까요? 아니, 그 전에 펠렌드롬이 뭔지 알아야겠죠? 펠렌드롬은 거꾸로 뒤집어도 원래의 문자열과 같은 문자열을 의미합니다. 가령, ABBCBBA 라는 문자열..

class Solution: def uniquePaths(self, r: int, c: int) -> int: if (r == 1 or c == 1): return 1 dp = [[1] * c for _ in range(r)] for i in range(1, r): for j in range(1, c): dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[r-1][c-1]

from collections import defaultdict class Solution: def setZeroes(self, matrix: List[List[int]]) -> None: """ Do not return anything, modify matrix in-place instead. """ n = len(matrix) m = len(matrix[0]) rows = defaultdict(int) cols = defaultdict(int) for i in range(n): for j in range(m): if (matrix[i][j] == 0): rows[i] = 1 cols[j] = 1 for i in range(n): for j in range(m): if (rows[i] == 1 or c..