題目列表: https://leetcode.com/problem-list/oizxjoit/
- Coin Change
tags: dp
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [10001] * (amount + 1)
dp[0] = 0
for i in range(amount + 1):
for c in coins:
if i == c:
dp[i] = 1
break
if i > c:
dp[i] = min(dp[i], dp[i - c] + 1)
return dp[amount] if dp[amount] != 10001 else -1
# time complexity: O(n * m)
# space complexity: O(n)
# n: amount, m: length of coins
def coinChange(self, coins: List[int], amount: int) -> int:
N = len(coins)
@cache
def f(i, c):
if i < 0:
return 0 if c == 0 else inf
if c < coins[i]:
return f(i - 1, c)
return min(f(i, c - coins[i]) + 1, f(i - 1, c))
ans = f(N - 1, amount)
return ans if ans < inf else -1
參考: 0-1背包 完全背包
相關題目: 494
- Longest Increasing Subsequence
tags: dp
The last value is regarded as 1, if it satisfies strict increasing order, then recursively move backward.
def f(arr):
dp = [1] * len(arr)
for i in range(len(arr) - 1, -1, -1):
for j in range(i + 1, len(arr)):
if arr[i] < arr[j]:
dp[i] = max(dp[i], 1 + dp[j])
return max(dp)
# time complexity: O(n^2)
# space complexity: O(n)
- Longest Common Subsequence
tags: 2d-dp
Create a 2D matrix, when the character match, add 1 to diagonal cell. Otherwise, take the larger value from either the left or the top cell.
tips: Increase the table size to avoid edges cases.
def lcs(text1, text2):
dp = [[0] * len(text2) for i in range(len(text1))]
for i in range(len(text1)):
for j in range(len(text2)):
if text1[i] == text2[j]:
if i > 0 and j > 0:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[len(text1) - 1][len(text2) - 1]
# time complexity: O(n * m)
# space complexity: O(n^2)
# n: length of text1
# m: length of text2
- Word Break
My first thought was to use replace to handle it, but it will cause errors when replacing multiple times. For example, with 'cbca', you can't replace 'bc' first and then replace 'ca' afterwards.
This problem needs to be handled using dp. Start from the last character and recurse backward.
def wordBreak(s, wordDict):
l = len(s)
dp = [False] * (l + 1)
dp[l] = True
for i in range(l - 1, -1, -1):
for word in wordDict:
wordLen = len(word)
if s[i: i + wordLen] == word:
dp[i] = dp[i] or dp[i + wordLen]
return dp[0]
# time complexity: O(m * n)
# space complexity: O(m)
# m: string length
# n: wordDict length
- House Robber
My first thought is to use recursion: each time, remove the i-th element and also remove i - 1 and i + 1 from the array. Recursively do this until the array length is 0, then return the maximum value. but this method will time out.
The dicision to rob the current house only depends on the first two state r1 and r2. Only keep r1 + n and r2, then shift iteratively.
def rob(nums):
r1, r2 = 0, 0
for num in nums:
tmp = max(r1 + num, r2)
r1 = r2
r2 = tmp
return r2
- House RobberII Consider it in two parts: the first part includes the first element, and the second part does not include the first element.
def robII(nums):
def robI(nums):
r1, r2 = 0, 0
for i in range(len(nums)):
tmp = max(r1 + nums[i], r2)
r1 = r2
r2 = tmp
return r2
return max(robI(nums[2: -1]) + nums[0], robI(nums[1:]))
- Unique Paths
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0] * (n+1) for i in range(m+1)]
dp[1][1] = 1
def dfs(row, col):
if row < 1 or col < 1:
return 0
if dp[row][col]:
return dp[row][col]
v = dfs(row - 1, col) + dfs(row, col - 1)
dp[row][col] = v
return v
dfs(m, n)
return dp[m][n]
# time complexity: O(m * n)
# space complexity: O(m * n) 可以優化成 O(n)
- Jump Game
def canJump(self, nums: List[int]) -> bool:
dp = [False] * len(nums)
dp[0] = True
for i in range(len(nums)):
for step in range(1, nums[i] + 1):
if i + step < len(nums):
dp[i + step] = dp[i]
return dp[len(nums) - 1]
# tc: O(n^2)
# sc: O(n)
def canJump(self, nums: List[int]) -> bool:
goal = len(nums) - 1
for i in range(len(nums) - 1, -1, -1):
if i + nums[i] >= goal:
goal = i
return True if goal == 0 else False
# tc: O(n)
# sc: O(1)
- Clone graph
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
dp = {}
def dfs(root):
if not root:
return None
if root.val in dp:
return dp[root.val]
copy = Node(root.val)
dp[root.val] = copy
for n in root.neighbors:
copy.neighbors.append(dfs(n))
return copy
return dfs(node)
# time complexity: O(n)
# space complexity: O(n) dp + O(n) dfs stack?
- Meeting Rooms
def canAttendMeetings(self, intervals: List[Interval]) -> bool:
cnt = Counter()
for interval in intervals:
start = interval.start
end = interval.end
for i in range(start, end):
cnt[i] += 1
if cnt[i] > 1:
return False
return True
# Time complexity: O(n^2) Space complexity: O(n)
def canAttendMeetings(self, intervals: List[Interval]) -> bool:
intervals.sort(key=lambda i: i.start)
N = len(intervals)
for i in range(N - 1):
end = intervals[i].end
nextStart = intervals[i + 1].start
if end > nextStart:
return False
return True
# Time complexity: O(nlogn) sort intervals
# Space complexity: O(1)
- Reverse a Linked List
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
p = None
while head:
n = head.next
head.next = p
p = head
head = n
return p
- Linked List Cycle
first pass answer
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while slow and fast:
if not slow or not fast or not fast.next or not fast.next.next:
return False
slow = slow.next
fast = fast.next.next
if slow.val == fast.val:
return True
return False
# Time complexity: O(n)
# Space complexity: O(1)
improvement
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
- Merge Two Sorted Linked Lists
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1:
return list2
if not list2:
return list1
if list1.val <= list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
# Time complexity: O(n)
# Space complexity: O(n + m) recursive call stack ?
- Longest Substring Without Repeating Characters
tags: sliding windows
def lengthOfLongestSubstring(self, s: str) -> int:
l = 0
chars = set()
res = 0
for r in range(len(s)):
while s[r] in chars:
chars.remove(s[l])
l += 1
chars.add(s[r])
res = max(res, r - l + 1)
return res
# Time complexity: O(n)
# Space complexity: O(n) set
- Longest Repeating Character Replacement
def characterReplacement(self, s: str, k: int) -> int:
cnt = Counter()
tmpK = k
for c in s:
cnt[c] += 1
ans = 0
for target in cnt.keys():
count = 0
l = 0
k = tmpK
for r in range(len(s)):
if s[r] == target:
count += 1
else:
if k > 0:
k -= 1
count += 1
else:
while s[l] == target:
l += 1
count -= 1
l += 1
ans = max(ans, count)
return ans
# First thought is replace character to most common character (it will fail with edge case)
# so I add possible replace character outside cause O(26)
# use slide window right and left to count freq O(n^2)
# Time complexity: O(26 * n^2) A-Z * len(n) * while loop
# Space complexity: O(n) counter
def characterReplacement(self, s: str, k: int) -> int:
cnt = Counter()
l = 0
ans = 0
for r in range(len(s)):
cnt[s[r]] += 1
max_freq = max(cnt.values())
max_len = sum(cnt.values())
if max_len - max_freq <= k:
ans = max(ans, max_len)
else:
cnt[s[l]] -= 1
l += 1
r -= 1
return ans
# Time complexity: O(26n)
# Space complexity: O(n)
- Group Anagrams
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
dicts = defaultdict(list)
for word in strs:
w = list(word)
w.sort()
dicts[''.join(w)].append(word)
return dicts.values()
- Valid Parentheses
def isValid(self, s: str) -> bool:
stack = []
PAIR = {
'(': ')',
'{': '}',
'[': ']'
}
for i in s:
if i in ['(', '{', '[']:
stack.append(i)
else:
if len(stack) == 0:
return False
top = stack.pop()
if PAIR[top] != i:
return False
return False if len(stack) else True
# Time complexity: O(n)
# Space complexity: O(n)
- Valid Palindrome
def isPalindrome(self, s: str) -> bool:
t = []
for c in s:
if c.isalnum():
t.append(c.lower())
N = len(t)
i = 0
j = N - 1
while i < j:
if t[i] != t[j]:
return False
i += 1
j -= 1
return True
- Palindromic Substrings
def countSubstrings(self, s: str) -> int:
def checkIsPalindromic(s):
j = len(s) - 1
for i in range(len(s)):
if s[i] != s[j]:
return False
j -= 1
return True
size = 1
ans = 0
for i in range(len(s)):
for size in range(1, len(s) - i + 1):
if checkIsPalindromic(s[i: i + size]):
ans += 1
return ans
# Time Complexity: O(n^3) for * for * checkIsPalindromic
# Space Complexity: O(1)
def countSubstrings(self, s: str) -> int:
ans = 0
for i in range(len(s)):
ans += 1
# odd
size = 1
while i >= size and i + size < len(s) and s[i - size] == s[i + size]:
ans += 1
size += 1
# even
size = 0
while i >= size and i + size + 1 < len(s) and s[i - size] == s[i + 1 + size]:
ans += 1
size += 1
return ans
# Time Complexity: O(n^2)
# Space Complexity: O(1)
- Maximum Depth of Binary Tree
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return max(self.maxDepth(root.left) + 1,
self.maxDepth(root.right) + 1
)
# time complexity: O(n)
# space complexity: O(n) worst case
- Same Tree
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if not p or not q:
return False
if p.val == q.val:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
else:
return False
- Invert Binary Tree
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(node):
if node == None:
return None
tmp = node.left
node.left = dfs(node.right)
node.right = dfs(tmp)
return node
return dfs(root)
# time complexity: O(n)
# space complexity: O(n) recursion stask
- Subtree of Another Binary Tree
def isSameTree(self, s, t):
if not s and not t:
return True
if not s or not t:
return False
if s.val == t.val:
return self.isSameTree(s.left, t.left) and (
self.isSameTree(s.right, t.right))
else:
return False
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if not root and not subRoot:
return True
if not root or not subRoot:
return False
if self.isSameTree(root, subRoot):
return True
else:
return self.isSubtree(root.left, subRoot) or (
self.isSubtree(root.right, subRoot)
)
- Top K Frequent Elements
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
cnt = Counter()
for c in nums:
cnt[c] += 1
return [v for (v, _) in cnt.most_common(k)]
- Valid Anagram
def isAnagram(self, s: str, t: str) -> bool:
cnt = Counter()
for c in s:
cnt[c] += 1
for c in t:
if c not in cnt:
return False
cnt[c] -= 1
if cnt[c] == 0:
del cnt[c]
return True if len(cnt) == 0 else False
- Sum of Two Integers
js
getSum(a, b) {
while(b){
let tmp = (a & b) << 1
a = a ^ b
b = tmp
}
return a
}