递归模版
def recursion(level, param1, param2, ...):
# 递归终止条件 recursion terminator
if level > MAX_LEVEL:
print_result
return
# 到了这层梦境, 在这层梦境要做的事情 process logic in current level
process_data(level, data, ...)
# 下探新的梦境 drill down
self.recursion(level + 1, p1, p2, ...)
# 还原下探之后可能对本层的影响, 还原状态 reverse the current level status if needed
reverse_status(level)
DFS 深度优先遍历 - 递归写法
visited = set()
def dfs(node, visited):
visited.add(node)
# 处理当前节点 process current node here
...
for next_node in node.children():
if not next_node in visited:
self.dfs(next_node, visited)
BFS 广度优先遍历 - 递归写法
def BFS(gragh, start, end):
queue = []
queue.append([start])
visited.add(start)
while queue:
node = queue.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node)
queue.push(nodes)
# other processing work
...
二分查找
left, right = 0, len(array) - 1
while left <= right:
mid = left + (right - left) / 2
if array[mid] == target:
# 如果查找到了就直接返回 find the target
break or return result
elif array[mid] < target:
left = mid + 1
else:
right = mid - 1
DP 动态规划 (TODO 这个不清楚)
// 状态定义
dp = new int[m+1][n+1];
// 初始状态
dp[0][0] = x;
dp[0][1] = y;
...
// DP 状态的推导
for i = 0; i <= n; ++i {
for j = 0; j <= m; ++j {
// 递推方程示例
...
d[i][j] = min {dp[i - 1][j], dp[i][j - 1], etc.}
}
}
return dp[m][n]; // 最优解
位运算
- X & 1 == 1 OR == 0 判断奇偶 (X % 2 == 1)
- X = X & (X - 1) => 清零最低位的 1
- X & -X => 得到最低位的 1
排序
选择排序 (Selection Sort)
int main()
{
// i j
int arr[] = {9, 5, 2, 7, 1, 6};
int length = sizeof(arr) / sizeof(arr[0]); // 数组长度
for (int i = 0; i < length; i++)
{
int minIndex = i;
// 寻找 [j(i+1), length) 区间最小值
for (int j = i + 1; j < length; j++)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
// 交换 i 位置和 minIndex(找到的最小数的索引) 位置中的值
// swap(arr[i], arr[minIndex]);
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
// 打印排序后的结果
for (int i = 0; i < length; i++)
{
cout << arr[i] << ' ';
}
return 0;
}
// 1 2 5 6 7 9
冒泡排序 (Bubble Sort)
TODO
插入排序 (Insertion Sort)
TODO
归并排序 (Merge Sort)
TODO
快速排序 (Quick Sort)
TODO