일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- Protocol
- 컴퓨터의 구조
- Convert Sorted List to Binary Search Tree
- data science
- Class
- 715. Range Module
- 30. Substring with Concatenation of All Words
- attribute
- 밴픽
- 시바견
- LeetCode
- 43. Multiply Strings
- Substring with Concatenation of All Words
- iterator
- DWG
- 파이썬
- 운영체제
- shiba
- t1
- Generator
- Decorator
- Python Implementation
- Python Code
- Python
- 315. Count of Smaller Numbers After Self
- kaggle
- concurrency
- Regular Expression
- 109. Convert Sorted List to Binary Search Tree
- 프로그래머스
- Today
- Total
목록Computer Science/Coding Test (225)
Scribbling
Several solutions and short analysis of each one. 1. List + Binary Search The most straightforward solution, however, time complexity is O(N**2). class Solution: def countSmaller(self, nums: List[int]) -> List[int]: from bisect import insort, bisect_left arr = [] count = [] for i in range(len(nums) - 1, -1, -1): num = nums[i] idx = bisect_left(arr, num) count.append(idx) insort(arr, num) return ..
Key idea: one's number of candies is affected by all the left and right neighbors. So we iterate the list twice, forward and backward. class Solution: def candy(self, ratings: List[int]) -> int: n = len(ratings) candies = [1] * n # forward pass for i in range(1, n): if ratings[i] > ratings[i-1]: candies[i] = candies[i-1] + 1 # backward pass for i in range(n-2, -1, -1): if ratings[i] > ratings[i+..
# 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 findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]: self.ret = [] self.dfs(root) return self.ret def dfs(self, node): if node.left and node.right: h = max(self.dfs(node.left), self.dfs(node.right)) + 1 e..
O(N) Time complexity, O(1) Memory Solution using Recursion # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # 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 sortedListToBST(self, he..
Perhaps, the most thinkable solution would be DFS or BFS. Traverse all the '1' points and update mins and maxs. Time complexity would be O(M*N) in this case. class Solution: def minArea(self, image: List[List[str]], x: int, y: int) -> int: m, n = len(image), len(image[0]) ymin, ymax, xmin, xmax = m, -1, n, -1 dy, dx = [0, 1, 0, -1], [1, 0, -1, 0] stack, visited = [(x, y)], set() while stack: i, ..
First solution is using regular expression. Below is some useful patterns. Integer: ^[+-]?\d+$ Flaot: ^[+-]?((\d+(\.\d*)?)|(\.\d+))$ Sicnetific notation: ^[+-]?((\d+(\.\d*)?)|(\.\d+))[eE][+-]?\d+$ class Solution: def isNumber(self, s: str) -> bool: import re pat = re.compile('(^[+-]?((\d+(\.\d*)?)|(\.\d+))$)|(^[+-]?((\d+(\.\d*)?)|(\.\d+))[eE][+-]?\d+$)') return re.match(pat, s) Second solution i..
A solution using sliding window. class Solution: def findSubstring(self, s: str, words: List[str]) -> List[int]: from collections import Counter ret = [] wordSet = set(words) n, m = len(words), len(words[0]) for i in range(m): wordCounter = Counter(words) k = j = i while j + m = n * m: if s[k:k+m] in wordSet: wordCounter[s[k:k+m]] += 1 k += m word = s[j:j+m] if word in wordSet: wordCounter[word]..
class Solution: def removeElement(self, nums: List[int], val: int) -> int: length = len(nums) i = 0 while i
First thing to try is iterating nums1, nums2, nums3 and looking for the corresponding element in nums4. This will result in O(N**3) time complexity, which raises TLE. class Solution: def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int: from collections import Counter c = Counter(nums4) ret = 0 for n1 in nums1: for n2 in nums2: for n3 in nums3: re..
Idea: Any characters that have frequencies less than k work as a breakpoints, meaning that the substring we're looking for can't include that particular character. So, recursively look for substrings while excluding those characters. Time complexity is O(N). from collections import Counter class Solution: def longestSubstring(self, s: str, k: int) -> int: return self.helper(s, k) def helper(self..