Template Summary.
Template of 0-1 Knapsack Problem
0-1 knapsack problem:
- 2-d dp array:
- Outer for loop is iterating items, inner for loop is iterating capacities of knapsack. They CAN switch the position.
- 1-d dp array:
- Outer for loop is iterating items, inner for loop is iterating capacities of knapsack. They CANNOT switch the position.
Using 2-d dp array:
def test_0x_knapsack(bag_size, weight, value) -> int:
rows, cols = len(weight), bag_size + 1
dp = [[0 for _ in range(cols)] for _ in range(rows)]
# initialization
for i in range(rows):
dp[i][0] = 0
first_item_weight, first_item_value = weight[0], value[0]
for j in range(1, cols):
if first_item_weight <= j:
dp[0][j] = first_item_value
# loop items before iterating capacities
for i in range(1, len(weight)):
cur_weight, cur_val = weight[i], value[i]
for j in range(1, cols):
if cur_weight > j: # item is heavier than the capacity
dp[i][j] = dp[i - 1][j]
else:
# recurrence relation
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cur_weight] + cur_val)
dp[rows-1][cols-1]
Using 1-d dp array (rolling array):
def test_01_knapsack():
weight = [1, 3, 4]
value = [15, 20, 30]
bag_weight = 4
dp = [0] * (bag_weight + 1)
# iterating items before iterating capacities
for i in range(len(weight)):
for j in range(bag_weight, weight[i] - 1, -1):
# recurrence relation
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
print(dp)
Template of 0-x Knapsack Problem
Brief summary of knapsack problems:
0-1 knapsack problem:
- 2-d dp array:
- Outer for loop is iterating items, inner for loop is iterating capacities of knapsack. They CAN switch the position.
- 1-d dp array:
- Outer for loop is iterating items, inner for loop is iterating capacities of knapsack. They CANNOT switch the position.
- 2-d dp array:
0-x knapsack problem:
1-d dp array or 2-d dp array:
Outer for loop is iterating items, inner for loop is iterating capacities of knapsack. They CAN switch the position.
Since we can have multiple copies of the same item, the inner for loop should NOT be in the reverse order any more.
O-x Knapsack code template
# loop items before iterating capacities
def test_complete_pack1():
weight = [1, 3, 4]
value = [15, 20, 30]
bag_weight = 4
dp = [0]*(bag_weight + 1)
for i in range(len(weight)):
for j in range(weight[i], bag_weight + 1):
# recurrence relation
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
return dp[bag_weight]
# loop capacities before iterating items
def test_complete_pack2():
weight = [1, 3, 4]
value = [15, 20, 30]
bag_weight = 4
dp = [0]*(bag_weight + 1)
for j in range(bag_weight + 1):
for i in range(len(weight)):
if j >= weight[i]:
# recurrence relation
dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
return dp[bag_weight]
Template of Combination and Permutation
Combination(n, d)
def Combination(nums, d, n, s, path, ans):
if d == n:
ans.append(path)
return
for i in range(s, len(nums)):
path.push(nums[i])
Combination(nums, d+1, n, i+1, path, ans)
path.pop()
Permutation(n, d)
def Permutation(nums, d, n, used, path, ans):
if d == n:
ans.append(path)
return
for i in range(0, len(nums)):
if used[i]: continue
used[i] = True
path.push(nums[i])
Permutation(nums, d+1, n, path, ans)
path.pop()
used[i] = False
Template of Recursion
def backtracking(parameters)
if (stop condition):
result
return
for (choose：elements in current tree level):
deal with node
backtracking(path，list) # recursion
backtrack and retrieve
Template of Union-Find Set
class UnionFind:
def __init__(self):
self.father = {}
def find(self,x):
root = x
while self.father[root] != None:
root = self.father[root]
# optimization: path compression O(log*n)
while x != root:
original_father = self.father[x]
self.father[x] = root
x = original_father
return root
def merge(self,x,y,val):
root_x,root_y = self.find(x),self.find(y)
if root_x != root_y:
self.father[root_x] = root_y
def is_connected(self,x,y):
return self.find(x) == self.find(y)
def add(self,x):
if x not in self.father:
self.father[x] = None
Template for Recursive Merge Sort
List1 = [1,3,5], List2 = [2,4], merge in ascending order.
def merge(a,b):
if not b: return a
if not a: return b
if a[0] < b[0]:
return a[0] + merge(a[1:], b)
else:
return a[0] + merge(a, b[1:])
(1) merge([1,3,5], [2,4]) = [1] + merge([3,5], [2,4]) = [1, 2, 3, 4, 5]
(2) merge([3,5], [2,4]) = [2] + merge([3,5], [4]) = [2, 3, 4, 5]
(3) merge([3,5], [4]) = [3] + merge([5], [4]) = [3, 4, 5]
(4) merge([5], [4]) = [4] + merge([5], []) = [4, 5]
(4) merge([5], []) = [5]
Time complexity:
- For array: O(n^2). Because getting subarray a[1:] takes O(n).
- For array: O(n). Because getting sub linked list takes O(1), using
.next().
Template of Copying a Linked List
dum is the head of the new linked list and it stays intact. We use double pointer pre and cur to copy a linked list.
def copyLinkedList(self, head: 'Node') -> 'Node':
cur = head
dum = pre = Node(0)
while cur:
node = Node(cur.val) # copy node at cur
pre.next = node # link pre to cur
cur = cur.next # move cur to cur.next
pre = node # move pre to pre.next
return dum.next
Template for Addition of Linked Lists
dummy = tail = ListNode(0)
carry = 0
while l1 or l2 or carry: # carry: 0 or 1
sum = l1.val + l2.val + carry # need to add 0 if lengths differ
tail.next = ListNode(sum % 10)
tail = tail.next
carry = sum // 10
l1, l2 = l1.next, l2.next
return dummy.next
Time complexity O(max(n,m)), space complexity O(max(n,m)).
Template for Binary Search
Sometime we need f(m) to determine whether m is the solution. g(m) is used to determine the side of the solution. Usually g(m) is given in the problem. We can consider binary_search works to “find the smallest l such that g(m) is true”.
Time complexity of binary_search is O(log(r-l) * (f(m) + g(m))), space complexity is O(1). Note that the time and space complexity of g(m) depends on the problem, and the space complexity O(1) does not include the space complexity of g(m).
def binary_search(l, r): # [l,r)
while l < r:
m = l + (r - l) // 2
if f(m):
return m
if g(m):
r = m # new range [l, m)
else:
l = m + 1 # new range [m+1, r)
return l
Application of this Template
1] Find the index of a specified element in a sorted unique array.
def binary_tree(array, val):
l = 0
r = len(array)
while l < r:
m = l + (r - l) // 2
if array[m] == val:
return m
if array[m] > val:
l = m
else:
r = m + 1
return -1 # not found
2] Find the lower bound and upper bound of a val in a sorted array.
lower_bound works to find the first index such that A[index] > = val. upper_bound works to find the first index such that A[index] > val.
def lower_bound(array, val):
l = 0
r = len(array)
while l < r:
m = l + (r - l) // 2
if A[m] >= val:
r = m
else:
l = m + 1
return l
def upper_bound(array, val):
l = 0
r = len(array)
while l < r:
m = l + (r - l) // 2
if A[m] > val:
r = m
else:
l = m + 1
return l
Two Ways of Defining Range
Binary Search: given a function g, returns the smallest m in the given range such that g(m) is True. Find a split point m such that for all n (n >= m), conditions are satisfied, then m will become the answer.
[l, r)In this case, strictly speaking, r should be n + 1, and can overflow if n = 2^31 -1. Sometimes, it’s doable to let r = n, after binary searching if the answer cannot be foun d from 1 to n-1, then n must be the answer so we return n.
def binary_search(l, r): while l < r: m = l + (r - l) // 2 if g(m): r = m # range [l, m) else: l = m + 1 # range [m + 1, r) return l[l, r]def binary_search(l, r): while l <= r: m = l + (r - l) // 2 if g(m): r = m - 1 # range [l, m - 1] else: l = m + 1 # range [m + 1, r] return l
