Algorithm Cheatsheet (continuously updated)
Purpose:
This is a continuous updated post to summarize typical algorithms in Python3 templates. My expectation is to train my muscle memory to these Python3 algorithm implemetations so that whenever I need them in problem solving, I don’t need to think too much (just apply those algorithm implemetation templates) and make little (if not zero) mistakes.
Python3 Templates for Typical Algorithms
- Typical DFS Python3 template
#params are normally those will change in each round of dfs
#for example, a position that something inside dfs will start with
#I'd suggest a more meaningful name to use than "dfs"
#like rollFrom(postion)visited = []def dfs(current_node):
#processing current_node to generate more leads(nodes)
nodes = processing of current_node
visited.append(current_node)
for node in nodes:
if node not in visited:
dfs(params_turning_from_branch_info)dfs(start_node) #kick start dfs
Above template will check each path one by one, but sometimes I will need to abort the checking if an answer is found in some path. In that case, the template can be slightly modified to be:
#params are normally those will change in each round of dfs
#for example, a position that something inside dfs will start with
#I'd suggest a more meaningful name to use than "dfs"
#like rollFrom(postion)visited = []def dfs(current_node):
#processing current_node to generate more leads(nodes)
nodes = processing of current_node
visited.append(current_node) #during above processing, some required criteria are met
if(criteria are met):
return True
for node in nodes:
if node not in visited:
if dfs(node):
return True
return Falsereturn dfs(start_node) #kick start dfs
2. Typical BFS Python3 template
Similarly to DFS, I may use BFS to find ALL possible answers (which means I need to navigate all nodes). Also, I may just stop by the first answer, which below template applies to.
Also, below template is not using recursive calls.
visited = []
toVisit = [start_node]while(len(toVisit) > 0):
toVisitInNextLayer = [] for current_node in toVisit:
#processing node to generate more leads(nodes)
nodes = processing of current_node
visited.append(current_node)
#during above processing, some required criteria are met
if(criteria are met):
return True for node in nodes:
if node not in visited:
toVisitInNextLayer.append(node)
toVisit = toVisitInNextLayerreturn False
Extended Reading
- Python3 cheatsheet: