Meta¶
Table of Contents¶
- 215. Kth Largest Element in an Array (Medium)
- 162. Find Peak Element (Medium)
- 199. Binary Tree Right Side View (Medium)
- 88. Merge Sorted Array (Easy)
- 1. Two Sum (Easy)
- 50. Pow(x, n) (Medium)
- 125. Valid Palindrome (Easy)
- 71. Simplify Path (Medium)
- 56. Merge Intervals (Medium)
- 129. Sum Root to Leaf Numbers (Medium)
- 138. Copy List with Random Pointer (Medium)
- 146. LRU Cache (Medium)
- 121. Best Time to Buy and Sell Stock (Easy)
- 23. Merge k Sorted Lists (Hard)
- 31. Next Permutation (Medium)
- 34. Find First and Last Position of Element in Sorted Array (Medium)
- 76. Minimum Window Substring (Hard)
- 133. Clone Graph (Medium)
- 65. Valid Number (Hard)
- 20. Valid Parentheses (Easy)
- 19. Remove Nth Node From End of List (Medium)
- 14. Longest Common Prefix (Easy)
- 207. Course Schedule (Medium)
- 2. Add Two Numbers (Medium)
- 3. Longest Substring Without Repeating Characters (Medium)
- 173. Binary Search Tree Iterator (Medium)
- 26. Remove Duplicates from Sorted Array (Easy)
- 4. Median of Two Sorted Arrays (Hard)
- 15. 3Sum (Medium)
- 9. Palindrome Number (Easy)
215. Kth Largest Element in an Array¶
import heapq
import random
from typing import List
class Solution:
@staticmethod
def _partition(nums: List[int], left: int, right: int) -> tuple[int, int]:
"""Split a range into values smaller than, equal to, and greater than pivot."""
pivot = nums[(left + right) // 2]
smaller = current = left
greater = right
while current <= greater:
if nums[current] < pivot:
nums[smaller], nums[current] = nums[current], nums[smaller]
smaller += 1
current += 1
elif nums[current] > pivot:
nums[current], nums[greater] = nums[greater], nums[current]
greater -= 1
else:
current += 1
return smaller, greater
def sort(self, nums: List[int], k: int) -> int:
"""Built-in sort: O(n log n) time, O(n) space in Python."""
nums.sort(reverse=True)
return nums[k - 1]
def findKthLargest(self, nums: List[int], k: int) -> int:
"""LeetCode entry point using randomized in-place quickselect."""
return self.quick_select_in_place(nums, k)
def min_heap(self, nums: List[int], k: int) -> int:
"""Min-heap: O(n log k) time, O(k) space."""
min_heap = []
for num in nums:
heapq.heappush(min_heap, num)
if len(min_heap) > k:
heapq.heappop(min_heap)
return min_heap[0]
def quick_sort(self, nums: List[int], k: int) -> int:
"""In-place quicksort: O(n log n) average time, O(log n) average space."""
ranges = [(0, len(nums) - 1)]
while ranges:
left, right = ranges.pop()
if left >= right:
continue
equal_start, equal_end = self._partition(nums, left, right)
left_range = (left, equal_start - 1)
right_range = (equal_end + 1, right)
# Process the smaller range first to keep the stack small.
if left_range[1] - left_range[0] > right_range[1] - right_range[0]:
left_range, right_range = right_range, left_range
ranges.append(right_range)
ranges.append(left_range)
return nums[-k]
def quick_select_recursive(self, nums: List[int], k: int) -> int:
"""
Find the kth largest using recursive list partitions.
k largest
3, 2, 1, 5, 6, 4
0 1 2 3 4 5
Time: O(n) average, O(n^2) worst case.
Space: O(n) average for partitions and recursion.
"""
pivot = random.choice(nums)
left = [number for number in nums if number > pivot]
mid = [number for number in nums if number == pivot]
right = [number for number in nums if number < pivot]
if len(left) >= k:
return self.quick_select_recursive(left, k)
if len(left) + len(mid) >= k:
return pivot
return self.quick_select_recursive(right, k - len(left) - len(mid))
def quick_select_in_place(self, nums: List[int], k: int) -> int:
"""
Find the kth largest using randomized in-place quickselect.
The kth largest is the (n - k)th smallest using a zero-based index.
Time: O(n) average, O(n^2) worst case.
Space: O(1), because partitioning is iterative and in place.
"""
target = len(nums) - k
def partition(left: int, right: int) -> int:
pivot = random.randint(left, right)
nums[pivot], nums[right] = nums[right], nums[pivot]
pivot = nums[right]
store = left
for index in range(left, right):
if nums[index] < pivot:
nums[index], nums[store] = nums[store], nums[index]
store += 1
nums[store], nums[right] = nums[right], nums[store]
return store
left, right = 0, len(nums) - 1
while left <= right:
pivot_index = partition(left, right)
if pivot_index == target:
return nums[pivot_index]
if pivot_index < target:
left = pivot_index + 1
else:
right = pivot_index - 1
raise RuntimeError("quickselect failed to find the target")
if __name__ == "__main__":
solution = Solution()
methods = (
solution.findKthLargest,
solution.sort,
solution.min_heap,
solution.quick_sort,
solution.quick_select_recursive,
solution.quick_select_in_place,
)
cases = (
([3, 2, 1, 5, 6, 4], 2, 5),
([3, 2, 3, 1, 2, 4, 5, 5, 6], 4, 4),
([-1, -1], 2, -1),
([1], 1, 1),
)
for method in methods:
for nums, k, expected in cases:
assert method(nums.copy(), k) == expected
162. Find Peak Element¶
199. Binary Tree Right Side View¶
from collections import deque
from typing import List, Optional
from binarytree import Node as TreeNode
from binarytree import build
# Binary Tree BFS
def rightSideViewBFS(root: Optional[TreeNode]) -> List[int]:
if not root:
return []
q = deque([root])
res = []
while q:
n = len(q)
for i in range(n):
node = q.popleft()
if i == n - 1:
res.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return res
# Binary Tree DFS
def rightSideViewDFS(root: Optional[TreeNode]) -> List[int]:
"""后序遍历，先右后左，遇到的第一个节点就是该深度的最右侧节点"""
ans = []
def dfs(node, depth):
if node is None:
return
if depth == len(ans): # 这个深度首次遇到
ans.append(node.val)
dfs(node.right, depth + 1)
dfs(node.left, depth + 1)
dfs(root, 0)
return ans
if __name__ == "__main__":
root = [1, 2, 2, 3, 4, None, 3, None, None, 5]
root = build(root)
print(root)
# ____1
# / \
# 2__ 2
# / \ \
# 3 4 3
# /
# 5
assert rightSideViewBFS(root) == [1, 2, 3, 5]
assert rightSideViewDFS(root) == [1, 2, 3, 5]
88. Merge Sorted Array¶
from typing import List
class merge:
@staticmethod
def lr(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p1, p2, t = m - 1, n - 1, m + n - 1
while p1 >= 0 or p2 >= 0:
if p1 == -1:
nums1[t] = nums2[p2]
p2 -= 1
elif p2 == -1:
nums1[t] = nums1[p1]
p1 -= 1
elif nums1[p1] > nums2[p2]:
nums1[t] = nums1[p1]
p1 -= 1
else:
nums1[t] = nums2[p2]
p2 -= 1
t -= 1
if __name__ == "__main__":
nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3
merge.lr(nums1, m, nums2, n)
assert nums1 == [1, 2, 2, 3, 5, 6]
#include <cassert>
#include <vector>
using namespace std;
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1, t = m + n - 1;
while (p1 >= 0 || p2 >= 0) {
if (p1 == -1) {
nums1[t] = nums2[p2];
p2--;
} else if (p2 == -1) {
nums1[t] = nums1[p1];
p1--;
} else if (nums1[p1] > nums2[p2]) {
nums1[t] = nums1[p1];
p1--;
} else {
nums1[t] = nums2[p2];
p2--;
}
t--;
}
}
};
int main() {
Solution solution;
vector<int> nums1 = {1, 3, 6, 0, 0, 0};
vector<int> nums2 = {2, 5, 6};
vector<int> output = {1, 2, 3, 5, 6, 6};
solution.merge(nums1, 3, nums2, 3);
assert(nums1 == output);
return 0;
}
1. Two Sum¶
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
"""Hash Map: O(n) time, O(n) space.
Store seen values so each number can find its complement in one pass.
"""
hashmap = {} # val: idx
for idx, val in enumerate(nums):
comp = target - val
if comp in hashmap:
return [hashmap[comp], idx]
hashmap[val] = idx
return []
def test_two_sum():
s = Solution()
assert s.twoSum([2, 7, 11, 15], 9) == [0, 1]
assert s.twoSum([3, 2, 4], 6) == [1, 2]
assert s.twoSum([3, 3], 6) == [0, 1]
assert s.twoSum([1, 2, 3, 4, 5], 10) == []
assert s.twoSum([-1, -2, -3, -4, -5], -8) == [2, 4]
#include <cassert>
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (size_t i = 0; i < nums.size(); i++) {
int diff = target - nums[i];
if (map.find(diff) != map.end()) {
return {map[diff], (int)i};
}
map[nums[i]] = (int)i;
}
return {-1, -1};
}
};
int main() {
Solution solution;
vector<int> nums = {2, 7, 11, 15};
int target = 9;
vector<int> result = solution.twoSum(nums, target);
assert((result == vector<int>{0, 1}));
return 0;
}
50. Pow(x, n)¶
# Iterative
def myPowIterative(x: float, n: int) -> float:
if n == 0:
return 1
if n < 0:
x = 1 / x
n = -n
result = 1
cur = x
while n > 0:
if n % 2 == 1:
result *= cur
cur *= cur
n //= 2
return result
# Recursive
def myPowRecursive(x: float, n: int) -> float:
if n == 0:
return 1
if n < 0:
x = 1 / x
n = -n
if n % 2 == 0:
return myPowRecursive(x * x, n // 2)
else:
return x * myPowRecursive(x * x, n // 2)
x = 2.00000
n = 10
print(myPowIterative(x, n)) # 1024.0
print(myPowRecursive(x, n)) # 1024.0
125. Valid Palindrome¶
# List Comprehension
def isPalindrome(s: str) -> bool:
s = [char.lower() for char in s if char.isalnum()]
return s == s[::-1]
# Left Right Pointers
def isPalindromeLR(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
s = "A man, a plan, a canal: Panama"
print(isPalindrome(s)) # True
print(isPalindromeLR(s)) # True
71. Simplify Path¶
def simplify_path_stack(path: str) -> str:
if not path:
return "/"
stack = []
for p in path.split("/"):
if p == "" or p == ".":
continue
if p != "..":
stack.append(p)
elif stack:
stack.pop()
return "/" + "/".join(stack)
def test_simplify_path_stack():
assert simplify_path_stack("/home/") == "/home"
assert simplify_path_stack("/../") == "/"
assert simplify_path_stack("/home//foo/") == "/home/foo"
assert simplify_path_stack("/a/./b/../../c/") == "/c"
56. Merge Intervals¶
def merge(intervals: list[list[int]]) -> list[list[int]]:
"""
Merge all overlapping intervals.
| G----H
| E===========F
| C--------D
| A========B
|
|-----------------------------------
Draw the above to explain the process to the interviewer.
Time complexity: O(nlogn) due to sorting.
Space complexity: O(n) for the result list.
"""
n = len(intervals)
if n <= 1:
return intervals
intervals.sort(key=lambda x: x[0])
res = [intervals[0]]
for i in range(1, n):
if intervals[i][0] <= res[-1][1]:
res[-1][1] = max(res[-1][1], intervals[i][1])
else:
res.append(intervals[i])
return res
print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
# [[1, 6], [8, 10], [15, 18]]
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// Interval
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
for (auto& range : intervals) {
if (!res.empty() && range[0] <= res.back()[1]) {
res.back()[1] = max(res.back()[1], range[1]);
} else {
res.emplace_back(range);
}
}
return res;
}
int main() {
vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
vector<vector<int>> res = merge(intervals);
for (auto& range : res) {
cout << range[0] << ", " << range[1] << endl;
}
return 0;
}
129. Sum Root to Leaf Numbers¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
class sumNumbers:
def dfs(self, root: Optional[TreeNode]) -> int:
self.res = 0
def dfs(node, cur):
if not node:
return
cur = cur * 10 + node.val
if not node.left and not node.right:
self.res += cur
return
dfs(node.left, cur)
dfs(node.right, cur)
dfs(root, 0)
return self.res
if __name__ == "__main__":
root = [1, 2, 3]
root = build(root)
print(root)
# 1
# / \
# 2 3
assert sumNumbers().dfs(root) == 25
138. Copy List with Random Pointer¶
from typing import Optional
class Node:
def __init__(self, x: int, next: "Node" = None, random: "Node" = None):
self.val = int(x)
self.next = next
self.random = random
def copyRandomList(head: "Optional[Node]") -> "Optional[Node]":
if not head:
return None
# Copy nodes and link them together
cur = head
while cur:
new_node = Node(cur.val)
new_node.next = cur.next
cur.next = new_node
cur = new_node.next
# Copy random pointers
cur = head
while cur:
cur.next.random = cur.random.next if cur.random else None
cur = cur.next.next
# Separate the original and copied lists
cur = head
new_head = head.next
while cur:
new_node = cur.next
cur.next = new_node.next
new_node.next = new_node.next.next if new_node.next else None
cur = cur.next
return new_head
146. LRU Cache¶
from collections import OrderedDict
class DoublyListNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
"""
Design and implement a data structure for Least Recently Used (LRU) cache.
It should support the following operations: get and put.
"""
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.head = DoublyListNode()
self.tail = DoublyListNode()
self.head.next = self.tail
self.tail.prev = self.head
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def add_to_last(self, node):
self.tail.prev.next = node
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev = node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self.remove(node)
self.add_to_last(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.val = value
self.remove(node)
self.add_to_last(node)
else:
node = DoublyListNode(key=key, val=value)
self.cache[key] = node
self.add_to_last(node)
if len(self.cache) > self.cap:
lru = self.head.next
del self.cache[lru.key]
self.remove(lru)
class LRUCacheOrderedDict:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.cap = capacity
def get(self, key: int):
if key not in self.cache:
return -1
self.cache.move_to_end(key, last=True)
return self.cache[key]
def put(self, key: int, value: int):
if key in self.cache:
self.cache.move_to_end(key, last=True)
elif len(self.cache) >= self.cap:
self.cache.popitem(last=False)
self.cache[key] = value
def test_lru_cache():
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
assert cache.get(1) == 1
cache.put(3, 3)
assert cache.get(2) == -1
cache.put(4, 4)
assert cache.get(1) == -1
assert cache.get(3) == 3
assert cache.get(4) == 4
updated = LRUCache(2)
updated.put(1, 1)
updated.put(2, 2)
updated.put(1, 10)
updated.put(3, 3)
assert updated.get(1) == 10
assert updated.get(2) == -1
single = LRUCache(1)
single.put(1, 1)
single.put(2, 2)
assert single.get(1) == -1
assert single.get(2) == 2
def test_lru_cache_ordered_dict():
cache = LRUCacheOrderedDict(2)
cache.put(1, 1)
cache.put(2, 2)
assert cache.get(1) == 1
cache.put(3, 3)
assert cache.get(2) == -1
cache.put(4, 4)
assert cache.get(1) == -1
assert cache.get(3) == 3
assert cache.get(4) == 4
#include <cassert>
#include <iostream>
#include <unordered_map>
using namespace std;
class Node {
public:
int key;
int val;
Node *prev;
Node *next;
Node(int k = 0, int v = 0) : key(k), val(v), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
int cap;
unordered_map<int, Node *> cache;
Node *head;
Node *tail;
void remove(Node *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void insert_to_last(Node *node) {
tail->prev->next = node;
node->prev = tail->prev;
tail->prev = node;
node->next = tail;
}
void move_to_last(Node *node) {
remove(node);
insert_to_last(node);
}
public:
LRUCache(int capacity) {
this->cap = capacity;
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (cache.find(key) != cache.end()) {
Node *node = cache[key];
move_to_last(node);
return node->val;
}
return -1;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
Node *node = cache[key];
node->val = value;
move_to_last(node);
} else {
Node *newNode = new Node(key, value);
cache[key] = newNode;
insert_to_last(newNode);
if ((int)cache.size() > cap) {
Node *removed = head->next;
remove(removed);
cache.erase(removed->key);
delete removed;
}
}
}
};
int main() {
LRUCache lru(2);
lru.put(1, 1);
lru.put(2, 2);
assert(lru.get(1) == 1); // returns 1
lru.put(3, 3); // evicts key 2
assert(lru.get(2) == -1); // returns -1 (not found)
lru.put(4, 4); // evicts key 1
assert(lru.get(1) == -1); // returns -1 (not found)
assert(lru.get(3) == 3); // returns 3
assert(lru.get(4) == 4); // returns 4
return 0;
}
121. Best Time to Buy and Sell Stock¶
"""
- Return the maximum profit that can be achieved from buying on one day and selling on another day.
"""
from typing import List
# Brute Force
def maxProfitBF(prices: List[int]) -> int:
max_profit = 0
n = len(prices)
for i in range(n):
for j in range(i + 1, n):
max_profit = max(max_profit, prices[j] - prices[i])
return max_profit
# DP
def maxProfitDP(prices: List[int]) -> int:
dp = [[0] * 2 for _ in range(len(prices))]
dp[0][0] = -prices[0] # buy
dp[0][1] = 0 # sell
for i in range(1, len(prices)):
dp[i][0] = max(dp[i - 1][0], -prices[i]) # the lowest price to buy
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
return dp[-1][1]
# Greedy
def maxProfitGreedy(prices: List[int]) -> int:
max_profit = 0
seen_min = prices[0]
for i in range(1, len(prices)):
max_profit = max(max_profit, prices[i] - seen_min)
seen_min = min(seen_min, prices[i])
return max_profit
# Fast Slow Pointers
def maxProfitFS(prices: List[int]) -> int:
max_profit = 0
slow, fast = 0, 1
while fast < len(prices):
if prices[fast] > prices[slow]:
max_profit = max(max_profit, prices[fast] - prices[slow])
else:
slow = fast
fast += 1
return max_profit
# |------------|------- |---------|
# | Approach | Time | Space |
# |------------|--------|---------|
# | Brute Force| O(n^2)| O(1) |
# | DP | O(n) | O(n) |
# | Greedy | O(n) | O(1) |
# | Fast Slow | O(n) | O(1) |
# |------------|--------|---------|
prices = [7, 1, 5, 3, 6, 4]
print(maxProfitBF(prices)) # 5
print(maxProfitDP(prices)) # 5
print(maxProfitGreedy(prices)) # 5
print(maxProfitFS(prices)) # 5
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int maxProfitMemo(vector<int> &prices) {
if (prices.size() <= 1) return 0;
int seen_min = prices[0];
int res = 0;
for (int &price : prices) {
res = max(res, price - seen_min);
seen_min = min(seen_min, price);
}
return res;
}
};
int main() {
vector<int> prices = {7, 1, 5, 3, 6, 4};
Solution obj;
cout << obj.maxProfitMemo(prices) << endl;
return 0;
}
23. Merge k Sorted Lists¶
"""
- Prerequisite: 21. Merge Two Sorted Lists
- Video explanation: [23. Merge K Sorted Lists - NeetCode](https://youtu.be/q5a5OiGbT6Q?si=SQ2dCvsYQ3LQctPh)
"""
import copy
import heapq
from typing import List, Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
def merge_k_lists_divide_conquer(
lists: List[Optional[ListNode]],
) -> Optional[ListNode]:
if not lists or len(lists) == 0:
return None
def mergeTwo(l1, l2):
dummy = ListNode()
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 if l1 else l2
return dummy.next
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i + 1] if i + 1 < len(lists) else None
merged.append(mergeTwo(l1, l2))
lists = merged
return lists[0]
def merge_k_lists_heap(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
dummy = ListNode()
cur = dummy
min_heap = [] # (val, idx, node)
for idx, head in enumerate(lists):
if head:
heapq.heappush(min_heap, (head.val, idx, head))
while min_heap:
_, idx, node = heapq.heappop(min_heap)
cur.next = node
cur = cur.next
node = node.next
if node:
heapq.heappush(min_heap, (node.val, idx, node))
return dummy.next
def test_merge_k_lists() -> None:
n1 = list_from_array([1, 4])
n2 = list_from_array([1, 3])
n3 = list_from_array([2, 6])
lists = [n1, n2, n3]
lists1 = copy.deepcopy(lists)
lists2 = copy.deepcopy(lists)
assert (list_to_array(merge_k_lists_divide_conquer(lists1))) == [
1,
1,
2,
3,
4,
6,
]
assert (list_to_array(merge_k_lists_heap(lists2))) == [1, 1, 2, 3, 4, 6]
31. Next Permutation¶
from typing import List
def nextPermutation(nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
i = n - 1
while i > 0 and nums[i - 1] >= nums[i]:
i -= 1
if i != 0:
j = n - 1
while nums[j] <= nums[i - 1]:
j -= 1
nums[i - 1], nums[j] = nums[j], nums[i - 1]
left, right = i, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
nums = [1, 2, 3]
nextPermutation(nums)
print(nums) # [1, 3, 2]
nums = [1, 2, 3, 4, 6, 5]
nextPermutation(nums)
print(nums) # [1, 2, 3, 5, 4, 6]
34. Find First and Last Position of Element in Sorted Array¶
from bisect import bisect_left
from typing import List
class searchRange:
"""
找 lower bound 和 upper bound
看灵神对这道题的题解，分类讨论区间的写法
target 的 upper bound 是 target + 1 的 lower bound - 1
这样就能统一用 lower bound 的写法
"""
# [left, right]
def bisect_left_closed(self, nums, target):
"""
闭区间写法
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
# [left, right)
def bisect_left_right_open(self, nums, target):
"""
左闭右开区间写法
"""
left, right = 0, len(nums)
while left < right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid
else:
left = mid + 1
return left
# (left, right)
def bisect_left_open(self, nums, target):
"""
推荐开区间写法
"""
left, right = -1, len(nums)
while left + 1 < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid
else:
right = mid
return right
def search_range(self, nums: List[int], target: int) -> List[int]:
# edge case
if not nums:
return [-1, -1]
lower = self.bisect_left_closed(nums, target)
upper = self.bisect_left_closed(nums, target + 1) - 1
return [lower, upper] if lower <= upper else [-1, -1]
def search_range_bisect(self, nums: List[int], target: int) -> List[int]:
"""用 python bisect 库函数"""
# edge case
if not nums:
return [-1, -1]
lower = bisect_left(nums, target)
upper = bisect_left(nums, target + 1) - 1
return [lower, upper] if lower <= upper else [-1, -1]
if __name__ == "__main__":
nums = [5, 7, 7, 8, 8, 10]
target = 8
sol = searchRange()
assert sol.search_range(nums, target) == [3, 4]
assert sol.search_range_bisect(nums, target) == [3, 4]
#include <vector>
#include <iostream>
using namespace std;
class Solution
{
int bisect_left(vector<int> &nums, int target)
{
int left = 0, right = (int)nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] < target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return left;
}
public:
vector<int> searchRange(vector<int> &nums, int target)
{
int left = bisect_left(nums, target);
if (left == (int)nums.size() || nums[left] != target)
{
return {-1, -1};
}
int right = bisect_left(nums, target + 1) - 1;
return {left, right};
}
};
int main()
{
vector<int> nums = {5, 7, 7, 8, 8, 10};
int target = 8;
Solution s;
vector<int> res = s.searchRange(nums, target);
cout << res[0] << ", " << res[1] << endl;
return 0;
}
76. Minimum Window Substring¶
from collections import Counter
def minWindow(s: str, t: str) -> str:
if not t or not s:
return ""
counts = Counter(t)
required = len(counts)
left, right = 0, 0
formed = 0
window_counts = dict()
result = float("inf"), None, None
while right < len(s):
char = s[right]
window_counts[char] = window_counts.get(char, 0) + 1
if char in counts and window_counts[char] == counts[char]:
formed += 1
while left <= right and formed == required:
char = s[left]
if right - left + 1 < result[0]:
result = (right - left + 1, left, right)
window_counts[char] -= 1
if char in counts and window_counts[char] < counts[char]:
formed -= 1
left += 1
right += 1
return "" if result[0] == float("inf") else s[result[1] : result[2] + 1]
s = "ADOBECODEBANC"
t = "ABC"
print(minWindow(s, t)) # BANC
133. Clone Graph¶
from collections import deque
from typing import Optional
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
class CloneGraph:
def dfs(self, node: Optional["Node"]) -> Optional["Node"]:
hashmap = {}
def dfs(node):
if node in hashmap:
return hashmap[node]
res = Node(node.val)
hashmap[node] = res
for nei in node.neighbors:
res.neighbors.append(dfs(nei))
return res
return dfs(node) if node else None
def bfs(self, node: Optional["Node"]) -> Optional["Node"]:
if not node:
return None
hashmap = {node: Node(node.val)}
q = deque([node])
while q:
cur = q.popleft()
for nei in cur.neighbors:
if nei not in hashmap:
hashmap[nei] = Node(nei.val)
q.append(nei)
hashmap[cur].neighbors.append(hashmap[nei])
return hashmap[node]
65. Valid Number¶
20. Valid Parentheses¶
# Stack
def is_valid(s: str) -> bool:
if len(s) % 2:
return False
pairs = {
"(": ")",
"{": "}",
"[": "]",
}
stack = []
for ch in s:
if ch in pairs:
stack.append(ch)
elif not stack or ch != pairs[stack.pop()]:
return False
return True if not stack else False
def test_is_valid():
assert is_valid("()[]{}")
assert not is_valid("(]")
assert not is_valid("([)]")
assert is_valid("{[]}")
#include <cassert>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
bool isValid(string s) {
unordered_map<char, char> map{{')', '('}, {'}', '{'}, {']', '['}};
stack<char> stack;
if (s.length() % 2 == 1) return false;
for (char& ch : s) {
if (stack.empty() || map.find(ch) == map.end()) {
stack.push(ch);
} else {
if (map[ch] != stack.top()) {
return false;
}
stack.pop();
}
}
return stack.empty();
}
};
int main() {
Solution s;
assert(s.isValid("()") == true);
assert(s.isValid("()[]{}") == true);
assert(s.isValid("(]") == false);
assert(s.isValid("([)]") == false);
assert(s.isValid("{[]}") == true);
return 0;
}
19. Remove Nth Node From End of List¶
"""
- Given the `head` of a linked list, remove the `n-th` node from the end of the list and return its head.
"""
from typing import Optional
from leetpattern.utils import ListNode, list_from_array, list_to_array
# Linked List
def removeNthFromEnd(head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
fast, slow = dummy, dummy
for _ in range(n):
fast = fast.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
def test_removeNthFromEnd() -> None:
head = list_from_array([1, 2, 3, 4, 5])
assert (list_to_array(removeNthFromEnd(head, 2))) == [1, 2, 3, 5]
14. Longest Common Prefix¶
from typing import List
class longestCommonPrefix:
def horizontal_scan(self, strs: List[str]) -> str:
if not strs:
return ""
prefix = strs[0]
for i in range(1, len(strs)):
while not strs[i].startswith(prefix):
prefix = prefix[:-1]
if not prefix:
return ""
return prefix
def vertical_scan(self, strs: List[str]) -> str:
if not strs:
return ""
for i in range(len(strs[0])):
char = strs[0][i]
for j in range(1, len(strs)):
if i >= len(strs[j]) or strs[j][i] != char:
return strs[0][:i]
return strs[0]
def divide_conquer(self, strs: List[str]) -> str:
if not strs:
return ""
def merge(left, right):
n = min(len(left), len(right))
for i in range(n):
if left[i] != right[i]:
return left[:i]
return left[:n]
def find(strs, start, end):
if start == end:
return strs[start]
mid = start + (end - start) // 2
left = find(strs, start, mid)
right = find(strs, mid + 1, end)
return merge(left, right)
return find(strs, 0, len(strs) - 1)
def binary_search(self, strs: List[str]) -> str:
if not strs:
return ""
def isCommonPrefix(strs, length):
prefix = strs[0][:length]
return all(s.startswith(prefix) for s in strs)
minLen = min(len(s) for s in strs)
low, high = 0, minLen
while low < high:
mid = low + (high - low) // 2
if isCommonPrefix(strs, mid + 1):
low = mid + 1
else:
high = mid
return strs[0][:low]
if __name__ == "__main__":
solution = longestCommonPrefix()
strs = ["flower", "flow", "flight"]
assert solution.horizontal_scan(strs) == "fl"
assert solution.vertical_scan(strs) == "fl"
assert solution.divide_conquer(strs) == "fl"
assert solution.binary_search(strs) == "fl"
207. Course Schedule¶
from collections import defaultdict, deque
from typing import List
# BFS (Kahn's Algorithm)
def canFinishBFS(numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
indegree = defaultdict(int)
for crs, pre in prerequisites:
graph[pre].append(crs)
indegree[crs] += 1
q = deque([i for i in range(numCourses) if indegree[i] == 0])
count = 0
while q:
crs = q.popleft()
count += 1
for nxt in graph[crs]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
q.append(nxt)
return count == numCourses
# DFS + Set
def canFinishDFS1(numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
for crs, pre in prerequisites:
graph[crs].append(pre)
visiting = set()
def dfs(crs):
if crs in visiting: # cycle detected
return False
if graph[crs] == []:
return True
visiting.add(crs)
for pre in graph[crs]:
if not dfs(pre):
return False
visiting.remove(crs)
graph[crs] = []
return True
for crs in range(numCourses):
if not dfs(crs):
return False
return True
# DFS + List
def canFinishDFS2(numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = defaultdict(list)
for pre, crs in prerequisites:
graph[crs].append(pre)
# 0: init, 1: visiting, 2: visited
status = [0] * numCourses
def dfs(crs):
if status[crs] == 1: # cycle detected
return False
if status[crs] == 2:
return True
status[crs] = 1
for pre in graph[crs]:
if not dfs(pre):
return False
status[crs] = 2
return True
for crs in range(numCourses):
if not dfs(crs):
return False
return True
prerequisites = [[0, 1], [0, 2], [1, 3], [1, 4], [3, 4]]
print(canFinishBFS(5, prerequisites)) # True
print(canFinishDFS1(5, prerequisites)) # True
print(canFinishDFS2(5, prerequisites)) # True
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
// BFS
bool canFinishBFS(int numCourses, vector<vector<int>> &prerequisites) {
vector<vector<int>> graph(numCourses);
vector<int> indegree(numCourses, 0);
for (auto &pre : prerequisites) {
graph[pre[1]].push_back(pre[0]);
indegree[pre[0]]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
int cnt = 0;
while (!q.empty()) {
int cur = q.front();
q.pop();
cnt++;
for (int nxt : graph[cur]) {
indegree[nxt]--;
if (indegree[nxt] == 0) {
q.push(nxt);
}
}
}
return cnt == numCourses;
}
// DFS
bool canFinishDFS(int numCourses, vector<vector<int>> &prerequisites) {
vector<vector<int>> graph(numCourses);
for (auto &pre : prerequisites) {
graph[pre[1]].push_back(pre[0]);
}
// 0: not visited, 1: visiting, 2: visited
vector<int> state(numCourses, 0);
function<bool(int)> dfs = [&](int pre) -> bool {
state[pre] = 1; // visiting
for (int crs : graph[pre]) {
if (state[crs] == 1 || (state[crs] == 0 && dfs(crs))) {
return true;
}
}
state[pre] = 2; // visited
return false;
};
for (int i = 0; i < numCourses; i++) {
if (state[i] == 0 && dfs(i)) {
return false;
}
}
return true;
}
};
int main() {
Solution sol;
vector<vector<int>> prerequisites = {{1, 0}, {2, 1}, {3, 2}, {4, 3},
{5, 4}, {6, 5}, {7, 6}, {8, 7},
{9, 8}, {10, 9}};
int numCourses = 11;
cout << sol.canFinishBFS(numCourses, prerequisites) << endl;
cout << sol.canFinishDFS(numCourses, prerequisites) << endl;
return 0;
}
2. Add Two Numbers¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
class Solution:
def addTwoNumbers(
self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
"""Digit Carry Simulation: O(max(m, n)) time, O(max(m, n)) space.
Walk both reversed lists while carrying overflow into the next digit.
"""
dummy = ListNode()
cur = dummy
carry = 0
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
carry, val = divmod(v1 + v2 + carry, 10)
cur.next = ListNode(val)
cur = cur.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
def test_add_two_numbers():
s = Solution()
l1 = LinkedList([2, 4, 3]).head
l2 = LinkedList([5, 6, 4]).head
assert LinkedList(s.addTwoNumbers(l1, l2)).to_array() == [7, 0, 8]
l1 = LinkedList([0]).head
l2 = LinkedList([0]).head
assert LinkedList(s.addTwoNumbers(l1, l2)).to_array() == [0]
l1 = LinkedList([9, 9, 9, 9, 9, 9, 9]).head
l2 = LinkedList([9, 9, 9, 9]).head
assert LinkedList(s.addTwoNumbers(l1, l2)).to_array() == [
8,
9,
9,
9,
0,
0,
0,
1,
]
#include <cassert>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy;
ListNode* cur = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
if (l1) {
carry += l1->val;
l1 = l1->next;
}
if (l2) {
carry += l2->val;
l2 = l2->next;
}
cur->next = new ListNode(carry % 10);
cur = cur->next;
carry /= 10;
}
return dummy.next;
}
};
int main() {
Solution sol;
ListNode* l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
ListNode* l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
ListNode* result = sol.addTwoNumbers(l1, l2);
vector<int> expected = {7, 0, 8};
for (int val : expected) {
assert(result != nullptr && result->val == val);
result = result->next;
}
assert(result == nullptr); // End of list
return 0;
}
3. Longest Substring Without Repeating Characters¶
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
"""Sliding Window: O(n) time, O(min(n, charset)) space.
Jump the left edge past each repeated character's previous index.
"""
left = 0
res = 0
seen = {}
for right, ch in enumerate(s):
if ch in seen and seen[ch] >= left:
left = seen[ch] + 1
seen[ch] = right
res = max(res, right - left + 1)
return res
def lengthOfLongestSubstringSet(self, s: str) -> int:
"""Sliding Window Set: O(n) time, O(min(n, charset)) space.
Shrink until the current character is unique in the window.
"""
left = 0
res = 0
window = set()
for right, ch in enumerate(s):
while ch in window:
window.remove(s[left])
left += 1
window.add(ch)
res = max(res, right - left + 1)
return res
def test_length_of_longest_substring():
s = Solution()
cases = [
("abcabcbb", 3),
("bbbbb", 1),
("pwwkew", 3),
("", 0),
(" ", 1),
("abba", 2),
("dvdf", 3),
]
for text, expected in cases:
assert s.lengthOfLongestSubstring(text) == expected
assert s.lengthOfLongestSubstringSet(text) == expected
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
int lengthOfLongestSubstring(string s) {
int n = s.length();
int res = 0;
int left = 0;
unordered_set<char> window;
for (int right = 0; right < n; right++) {
char ch = s[right];
while (window.find(ch) != window.end()) {
window.erase(s[left]);
left++;
}
window.insert(ch);
res = max(res, right - left + 1);
}
return (int)res;
}
int main() {
string s = "abcabcbb";
cout << lengthOfLongestSubstring(s) << endl; // 3
s = "bbbbb";
cout << lengthOfLongestSubstring(s) << endl; // 1
s = "pwwkew";
cout << lengthOfLongestSubstring(s) << endl; // 3
return 0;
}
173. Binary Search Tree Iterator¶
from typing import Optional
from binarytree import Node as TreeNode
from binarytree import build
# BST
class BSTIterator:
def __init__(self, root: Optional[TreeNode]):
self.stack = []
self._leftmost_inorder(root)
def _leftmost_inorder(self, root):
while root:
self.stack.append(root)
root = root.left
def next(self) -> int:
topmost_node = self.stack.pop()
if topmost_node.right:
self._leftmost_inorder(topmost_node.right)
return topmost_node.val
def hasNext(self) -> bool:
return len(self.stack) > 0
root = build([7, 3, 15, None, None, 9, 20])
print(root)
# 7__
# / \
# 3 15
# / \
# 9 20
obj = BSTIterator(root)
print(obj.next()) # 3
print(obj.next()) # 7
print(obj.hasNext()) # True
26. Remove Duplicates from Sorted Array¶
from typing import List
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
"""Two Pointers: O(n) time, O(1) space.
Keep `left` at the last unique value and overwrite the next position
whenever `right` finds a different value.
Example: nums = [0, 0, 1, 1, 2]
start: left = 0, unique prefix = [0]
right 0: 0 == 0 -> unchanged
right 1: 0 == 0 -> unchanged
right 2: 1 != 0 -> left = 1, prefix = [0, 1]
right 3: 1 == 1 -> unchanged
right 4: 2 != 1 -> left = 2, prefix = [0, 1, 2]
Return 3; the first three values are [0, 1, 2].
"""
if not nums:
return 0
n = len(nums)
left = 0
for right in range(n):
if nums[right] != nums[left]:
left += 1
nums[left] = nums[right]
return left + 1
def test_remove_duplicates():
s = Solution()
for fn in (s.removeDuplicates,):
cases = [
([], []),
([1], [1]),
([1, 1, 2], [1, 2]),
([0, 0, 1, 1, 1, 2, 2, 3, 3, 4], [0, 1, 2, 3, 4]),
]
for nums, expected in cases:
k = fn(nums)
assert k == len(expected)
assert nums[:k] == expected
#include <cassert>
#include <vector>
using namespace std;
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int fast = 1, slow = 1;
int n = nums.size();
while (fast < n) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
};
int main() {
Solution solution;
vector<int> nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
assert(solution.removeDuplicates(nums) == 5);
return 0;
}
4. Median of Two Sorted Arrays¶
from typing import List
# Brute Force
def findMedianSortedArraysBF(nums1: List[int], nums2: List[int]) -> float:
nums = sorted(nums1 + nums2)
n = len(nums)
if n % 2 == 0:
return (nums[n // 2 - 1] + nums[n // 2]) / 2
else:
return nums[n // 2]
# Binary Search
def findMedianSortedArraysBS(nums1: List[int], nums2: List[int]) -> float:
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
imin, imax, half_len = 0, m, (m + n + 1) // 2
while imin <= imax:
i = (imin + imax) // 2
j = half_len - i
if i < m and nums2[j - 1] > nums1[i]:
imin = i + 1
elif i > 0 and nums1[i - 1] > nums2[j]:
imax = i - 1
else:
if i == 0:
max_of_left = nums2[j - 1]
elif j == 0:
max_of_left = nums1[i - 1]
else:
max_of_left = max(nums1[i - 1], nums2[j - 1])
if (m + n) % 2 == 1:
return max_of_left
if i == m:
min_of_right = nums2[j]
elif j == n:
min_of_right = nums1[i]
else:
min_of_right = min(nums1[i], nums2[j])
return (max_of_left + min_of_right) / 2
# |--------------|-----------------|--------------|
# | Approach | Time | Space |
# |--------------|-----------------|--------------|
# | Brute Force | O((n+m)log(n+m))| O(n+m) |
# | Binary Search| O(log(min(n,m)))| O(1) |
# |--------------|-----------------|--------------|
nums1 = [1, 3]
nums2 = [2]
print(findMedianSortedArraysBF(nums1, nums2)) # 2.0
print(findMedianSortedArraysBS(nums1, nums2)) # 2.0
15. 3Sum¶
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
"""Two Pointers: O(n^2) time, O(1) space.
Sort, fix one element, then two-pointer scan for complement.
"""
n = len(nums)
if n <= 2:
return []
res = []
nums.sort()
for k in range(n - 2):
if k > 0 and nums[k] == nums[k - 1]:
continue
i, j = k + 1, n - 1
while i < j:
total = nums[k] + nums[i] + nums[j]
if total > 0:
j -= 1
elif total < 0:
i += 1
else:
res.append([nums[k], nums[i], nums[j]])
while i < j and nums[i] == nums[i + 1]:
i += 1
while i < j and nums[j] == nums[j - 1]:
j -= 1
i += 1
j -= 1
return res
def test_three_sum():
s = Solution()
for fn in (s.threeSum,):
assert fn([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
assert fn([0, 1, 1]) == []
assert fn([0, 0, 0]) == [[0, 0, 0]]
assert fn([]) == []
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> res;
int n = nums.size();
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1, right = n - 1;
while (left < right) {
int total = nums[i] + nums[left] + nums[right];
if (total > 0)
right--;
else if (total < 0)
left++;
else {
res.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
}
return res;
}
int main() {
vector<int> nums = {-1, 0, 1, 2, -1, -4};
vector<vector<int>> res = threeSum(nums);
for (auto& v : res) {
for (int i : v) {
cout << i << " ";
}
cout << endl;
}
return 0;
}
9. Palindrome Number¶
"""
- Return true if the given number is a palindrome. Otherwise, return false.
"""
# Reverse
def isPalindromeReverse(x: int) -> bool:
if x < 0:
return False
return str(x) == str(x)[::-1]
# Left Right Pointers
def isPalindromeLR(x: int) -> bool:
if x < 0:
return False
x = list(str(x)) # 121 -> ['1', '2', '1']
left, right = 0, len(x) - 1
while left < right:
if x[left] != x[right]:
return False
left += 1
right -= 1
return True
# |------------|------- |---------|
# | Approach | Time | Space |
# |------------|--------|---------|
# | Reverse | O(N) | O(N) |
# | Left Right | O(N) | O(1) |
# |------------|--------|---------|
x = 121
print(isPalindromeReverse(x)) # True
print(isPalindromeLR(x)) # True