recursion.md

递归

介绍

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

示例

reverse-string

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

funcreverseString(s []byte) {
res:=make([]byte, 0)
reverse(s, 0, &res)
fori:=0; i<len(s); i++ {
s[i] =res[i]
}
}
funcreverse(s []byte, iint, res*[]byte) {
ifi==len(s) {
return
}
reverse(s, i+1, res)
*res=append(*res, s[i])
}

swap-nodes-in-pairs

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

funcswapPairs(head*ListNode) *ListNode {
// 思路：将链表翻转转化为一个子问题，然后通过递归方式依次解决// 先翻转两个，然后将后面的节点继续这样翻转，然后将这些翻转后的节点连接起来returnhelper(head)
}
funchelper(head*ListNode)*ListNode{
ifhead==nil||head.Next==nil{
returnhead
}
// 保存下一阶段的头指针nextHead:=head.Next.Next// 翻转当前阶段指针next:=head.Nextnext.Next=headhead.Next=helper(nextHead)
returnnext
}

unique-binary-search-trees-ii

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

funcgenerateTrees(nint) []*TreeNode {
ifn==0{
returnnil
}
returngenerate(1,n)
}
funcgenerate(start,endint)[]*TreeNode{
ifstart>end{
return []*TreeNode{nil}
}
ans:=make([]*TreeNode,0)
fori:=start;i<=end;i++{
// 递归生成所有左右子树lefts:=generate(start,i-1)
rights:=generate(i+1,end)
// 拼接左右子树后返回forj:=0;j<len(lefts);j++{
fork:=0;k<len(rights);k++{
root:=&TreeNode{Val:i}
root.Left=lefts[j]
root.Right=rights[k]
ans=append(ans,root)
}
}
}
returnans
}

递归+备忘录

fibonacci-number

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N，计算 F(N)。

funcfib(Nint) int {
returndfs(N)
}
varmmap[int]int=make(map[int]int)
funcdfs(nint)int{
ifn<2{
returnn
}
// 读取缓存ifm[n]!=0{
returnm[n]
}
ans:=dfs(n-2)+dfs(n-1)
// 缓存已经计算过的值m[n]=ansreturnans
}

练习

• reverse-string
• swap-nodes-in-pairs
• unique-binary-search-trees-ii
• fibonacci-number