Some of the code template

612

Pythonic trie
Quick way to create a trie in python

T = lambda: collections.defaultdict(T)
trie = T()

Check repeating string
Check if a string s is a repeated substring

check = (s+s).find(s, 1)
# check is the length of the shortest repeating substring
# If check == len(s), meaning that it's not a repeating string

Union Find

"""
uf = UnionFind(n)
uf.union(a,b)
for i in range(n):
	uf.find(i)
"""
class UnionFind:
	def __init__(self, n):
		self.parents = [i for i in range(n)]
		self.ranks = [1]*n
		
	def find(self, a):
		if self.parents[a] != a:
			self.parents[a] = self.find(self.parents[a])
		return self.parents[a]
	
	def union(self, a, b):
		pa, pb = self.find(a), self.find(b)
		if pa == pb: return False # No action done
		if self.ranks[a] > self.ranks[b]:
			pa, pb = pb, pa
		self.parents[pa] = self.find(pb)
		self.ranks[a] += 1
		return True

Binary Index Tree
Helpful for calculating segmented sums

"""
bitree = BITree(n)
bitree.update(index, delta)
bitree.get_sum(index)
"""


class BITree:
    def __init__(self, n):
        self.arr = [0] * (n+1)
        
    def update(self, i, delta):
        while i < len(self.arr):
            self.arr[i] += delta
            i += i&-i
            
    def get_sum(self, i):
        res = 0
        while i > 0:
            res += self.arr[i]
            i -= i&-i
        return res

DFS example account balance

# DFS with pretty brute force way
class Solution:
    def minTransfers(self, transactions: List[List[int]]) -> int:
        people = collections.Counter()
        for p1, p2, amount in transactions:
            people[p1] += amount
            people[p2] -= amount
            
        values = [v for v in people.values() if v != 0]
        
        def dfs(remaining):
            if len(remaining) == 0:
                return 0
            if remaining[0] == 0:
                return dfs(remaining[1::])
            # If there is any two element with sum = 0
            for i in range(len(remaining)):
                if remaining[0] + remaining[i] == 0:
                    remaining[i] = 0
                    return 1+dfs(remaining[1::])
            
            # No pair of elements with sum zero, brute force to the next round
            possible_res = []
            for i in range(len(remaining)):
                if remaining[0] * remaining[i] < 0:
                    possible_res.append(dfs(remaining[1:i]+[remaining[0]+remaining[i]]+remaining[i+1:]))
            return 1+min(possible_res)
        
        return dfs(values)

Morris
Traverse a tree without using extra space, but it modifies the tree elements on fly. Inorder example:

cur = root
res = []

while cur is not None:
	if cur.left is None:
		res.append(cur.val)
		cur = cur.right
	else:
		prev = cur.left
		while prev.right is not None and prev.right != cur:
			prev = prev.right

		if prev.right is None:
			prev.right = cur
			cur = cur.left

		else:
			prev.right = None
			res.append(cur.val) # Do your thing
			cur = cur.right

Manacher's algorithm
An advanced DP solution to find palindromic substring. It's based on center scanning and DP. Example LeetCode 5 https://leetcode.com/problems/longest-palindromic-substring/

S = "^#" + "#".join(list(s)) + "#$" # Reformat the string
dp = [0] * len(S)
center, R = 0, 0  # Starting center and right

for i in range(len(S)):
	mirror = center + (center - i) # Set the mirror position
	# 1. If i is still in the boundry, intialize dp[i] by dp[i] = min(R-i, dp[mirror])
	if i < R:
		dp[i] = min(R-i, dp[mirror])
	# 2. Expanding the check window by adding dp[i]
	while i+(dp[i]+1) < len(S) and S[i+(dp[i]+1)] == S[i-(dp[i]+1)]:
		dp[i] += 1
	# 3. If now the new palindrome is over the previous boundry, reset the boundry
	# This step is the key to replace the unneeded checks. if i+dp[i] > R: center = i; R = i+dp[i]
	if i + dp[i] > R:
		center = i
		R = i+dp[i]
		
	# Get the result and convert the output
	max_length = max(dp)
	index = dp.index(max_length)

Tarjan
Finding SCC or critical connections. Example https://leetcode.com/problems/critical-connections-in-a-network/

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        # TRACK EACH NODE'S RANK AND ITS LOWEST RANK
        rank = [None] * n
        lowest_rank = [None] * n
        
        # Create the graph
        g = defaultdict(list)
        for a,b in connections:
            g[a].append(b)
            g[b].append(a)   
        
        # DFS from node 0
        critical = []
        self.dfs(g, 0, None, set(), rank, lowest_rank, critical)
        return critical
        
    # Tarjan DFS
    def dfs(self, g, curr, parent, vis, rank, lowest_rank, critical):
        # Base case - node has been visted
        if curr in vis:
            return
        # Add node to visted
        vis.add(curr)
        
        # Set the node's rank and lowest rank by default
        rank[curr] = len(vis)
        lowest_rank[curr] = len(vis)
        
        # Explore its neighbours
        for nb in g.get(curr, []):
            # Exclude the parent
            if nb == parent:
                continue
                
            # DFS on the neighbour, giving the myself as the parent
            self.dfs(g, nb, curr, vis, rank, lowest_rank, critical)
            
            # Update my lowest rank
            lowest_rank[curr] = min(lowest_rank[curr], lowest_rank[nb])
            
            # Check if critical. If lowest_rank[nb] > rank[curr]
            if lowest_rank[nb] > rank[curr]:
                critical.append([curr, nb])

Comments (1)