递归思维

介绍

将大问题转化为小问题,通过递归依次解决各个小问题

示例

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
1
func reverseString(s []byte) {
2
res := make([]byte, 0)
3
reverse(s, 0, &res)
4
for i := 0; i < len(s); i++ {
5
s[i] = res[i]
6
}
7
}
8
func reverse(s []byte, i int, res *[]byte) {
9
if i == len(s) {
10
return
11
}
12
reverse(s, i+1, res)
13
*res = append(*res, s[i])
14
}
Copied!
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。 你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
1
func swapPairs(head *ListNode) *ListNode {
2
// 思路:将链表翻转转化为一个子问题,然后通过递归方式依次解决
3
// 先翻转两个,然后将后面的节点继续这样翻转,然后将这些翻转后的节点连接起来
4
return helper(head)
5
}
6
func helper(head *ListNode)*ListNode{
7
if head==nil||head.Next==nil{
8
return head
9
}
10
// 保存下一阶段的头指针
11
nextHead:=head.Next.Next
12
// 翻转当前阶段指针
13
next:=head.Next
14
next.Next=head
15
head.Next=helper(nextHead)
16
return next
17
}
Copied!
给定一个整数 n,生成所有由 1 ... n 为节点所组成的二叉搜索树。
1
func generateTrees(n int) []*TreeNode {
2
if n==0{
3
return nil
4
}
5
return generate(1,n)
6
7
}
8
func generate(start,end int)[]*TreeNode{
9
if start>end{
10
return []*TreeNode{nil}
11
}
12
ans:=make([]*TreeNode,0)
13
for i:=start;i<=end;i++{
14
// 递归生成所有左右子树
15
lefts:=generate(start,i-1)
16
rights:=generate(i+1,end)
17
// 拼接左右子树后返回
18
for j:=0;j<len(lefts);j++{
19
for k:=0;k<len(rights);k++{
20
root:=&TreeNode{Val:i}
21
root.Left=lefts[j]
22
root.Right=rights[k]
23
ans=append(ans,root)
24
}
25
}
26
}
27
return ans
28
}
Copied!

递归+备忘录

斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N,计算 F(N)。
1
func fib(N int) int {
2
return dfs(N)
3
}
4
var m map[int]int=make(map[int]int)
5
func dfs(n int)int{
6
if n < 2{
7
return n
8
}
9
// 读取缓存
10
if m[n]!=0{
11
return m[n]
12
}
13
ans:=dfs(n-2)+dfs(n-1)
14
// 缓存已经计算过的值
15
m[n]=ans
16
return ans
17
}
Copied!

练习

最近更新 1yr ago