func revers(head *Node) *Node {
if nil == head {
return nil
}
var pre, cur, aft *Node
cur = head
aft = cur.next
for nil != aft {
pre = cur
cur = aft
aft = cur.next
cur.next = pre
}
head.next = nil
return cur
}// 时间复杂度 nlogn 空间复杂度由于递归存在 logn
func quick(in []int, l, r int) {
i := l
j := r
var tmp int
if i < j {
tmp = in[i]
for i != j {
for j > i && in[j] < tmp {
j--
}
in[i] = in[j]
for i < j && in[i] > tmp {
i++
}
in[j] = in[i]
}
in[i] = tmp
quick(in, l, i-1)
quick(in, i+1, r)
}
}
O(1) < O(log2N) < O(N) < O(N * logN) < O(N^2) < O(N^3) < O(N!)
一般用来求最优解
- 判断是否可用递归来解
递归问题解决思路
- 先定义一个函数
- 接下来寻找问题与子问题间的关系
- 将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中
- 根据问题与子问题的关系，推导出时间复杂度,如果发现递归时间复杂度不可接受，则需转换思路对其进行改造，看下是否有更靠谱的解法
- 分析在递归的过程中是否存在大量的重复子问题
- 采用备忘录的方式来存子问题的解以避免大量的重复计算（剪枝）
- 改用自底向上的方式来递推，即 dp 解法
// 通用模版
result = []
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择