编程算法汇总。
介绍
总结常见的编程算法。
常见的算法
哈希表
哈希表 是一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。分类：
哈希集合是集合数据结构的实现之一，用于存储非重复值。哈希映射是映射数据结构的实现之一，用于存储(key, value)键值对。
递归
程序调用自身的编程技巧称为递归（recursion）
二分查找
二分查找法（binary-search） 是一种在 有序数组 中查找某一特定元素的搜索算法。- 搜索过程：从数组的中间元素开始
- 如果中间元素正好是要查找的元素，则搜索过程结束
- 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较
- 如果在某一步骤数组为空，则代表找不到
- 每次搜索数据量减半，时间复杂度为
O(log n)
go 示例
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
middle := (left + right) / 2
if nums[middle] == target {
return middle
}
if nums[middle] > target {
right = middle - 1
} else {
left = middle + 1
}
}
return -1
}
动态规划
动态规划（dynamic-programming）常常适用于有重叠子问题和最优子结构性质的问题，并且记录所有子问题的结果，因此动态规划方法所耗时间往往远少于朴素解法。
实现方式：
- 自顶向下即记忆化递归
- 自底向上就是递推：
dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])
存中间结果：
// https://leetcode.cn/problems/min-cost-climbing-stairs/
func minCostClimbingStairs(cost []int) int {
n := len(cost)
dp := make([]int, n+1)
dp[0], dp[1] = 0, 0
for i := 2; i <= n; i++ {
dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
}
return dp[n]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
不存中间结果，若是上楼梯问题，滚动时只用到最后两个结果：
func minCostClimbingStairs(cost []int) int {
n := len(cost)
pre, cur := 0, 0
for i := 2; i <= n; i++ {
pre, cur = cur, min(cur+cost[i-1], pre+cost[i-2])
}
return cur
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
回溯
回溯算法（backtracking）是对树形或者图形结构执行一次 深度优先遍历（DFS），实际上类似枚举的搜索尝试过程，在遍历的过程中寻找问题的解。
深度优先遍历有个特点：当发现已不满足求解条件时，就返回，尝试别的路径。
// https://leetcode.cn/problems/generate-parentheses/solution/
func generateParenthesis(n int) []string {
var ans []string
var dfs func(left, right int, path string)
dfs = func(left, right int, path string) {
if left == 0 && right == 0 {
ans = append(ans, path)
}
if left > 0 {
dfs(left-1, right, fmt.Sprintf("%s(", path))
}
if left < right {
dfs(left, right-1, fmt.Sprintf("%s)", path))
}
}
dfs(n, n, "")
return ans
}
深度优先搜索算法
深度优先搜索算法（Depth-First-Search，DFS） 是一种用于遍历或搜索 树 或 图 的算法- 使用场景：数的层次比较深的
- 优缺点：内存消耗小，但难以寻找最优解
- 实现过程：
- 对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次
- 如果我们知道了左子树和右子树的最大深度
l 和 r，那么该二叉树的最大深度即为 max(l, r)+1 而左子树和右子树的最大深度又可以以同样的方式进行计算。
- 深度优先搜索算法属于回溯思想，该思想解决问题适合用递归实现
求二叉树高度代码：
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}
广度优先搜索算法
当遇到要求 2 的 n 次方的时候，我们可以运用 Go 语言的左移运算符 « ，实现左移运算。
左移的运算规则是左移 N 位，就是乘以 2 的 N 次方。例子如下：
a := 1 « 3 // 2的3次方1 8
b := 1 « 6 // 2的6次方1 64
c := 4 « 2 // 2的2次方4 16
d := 4 « 3 // 2的3次方4 32
math.pow(2, 3)