递归-常规问题详解
目录
前言
递归在计算机算法中有很重要的地位,它可以解决条件具有重复性的问题。我们在快速排序和归并排序,都是利用了递归去解决问题的。写好一个递归代码不是太容易,很容易造成死循环最终内存泄漏。那么怎么写好递归代码呢,我总结了三点。
递归的三个关键:
-
定义需要递归的问题(重叠子问题)也就是说条件具有重复性。
-
递归边界
-
保护和还原现场
还是拿快排来说:快排的子问题就是分别对基准数据的左右子数据列分别排序,这个问题具有重复性,递归边界就是left>=right。
递归经典题目
子集
Leadcode 78
给你一个整数数组 nums
,数组中的元素 互不相同 。返回该数组所有可能的子集
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3] 输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
首先我们来看看这个递归的边界也就是退出条件是哪?首先我想到是子数组长度,子数组最小长度是0 ,最大长度就是数组的长度
var ans [][]int
var level int
func subsets(nums []int) [][]int {
ans=make([][]int,0)
for level=0;level<len(nums)+1;level++{
subsetsHelper(nums,0,[]int{},0)
}
return ans
}
func subsetsHelper(nums []int,start int,item []int){
if level==len(item){
copy_item:=make([]int,len(item))
copy(copy_item,item)
ans = append(ans,copy_item)
return
}
for i:=start;i<len(nums);i++{
item = append(item,nums[i])
subsetsHelper(nums,i+1,item)
item = item[:len(item)-1]
}
}
第二个角度我们也可以根据这个数据是否选。
var ans [][]int
func subsets(nums []int) [][]int {
ans = make([][]int,0)
subsetsHelper(nums,0,[]int{})
return ans
}
func subsetsHelper(nums []int,i int,item []int){
if i==len(nums){
copy_item:=make([]int,len(item))
copy(copy_item,item)
ans = append(ans,copy_item)
return
}
subsetsHelper(nums,i+1,item)
item = append(item,nums[i])
subsetsHelper(nums,i+1,item)
item = item[:len(item)-1]
}
77. 组合
给定两个整数 n
和 k
,返回范围 [1, n]
中所有可能的 k
个数的组合。
你可以按 任何顺序 返回答案。
示例 1:
输入:n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2:
输入:n = 1, k = 1 输出:[[1]]
var ans [][]int
func combine(n int, k int) [][]int {
ans = make([][]int,0)
combineHelper(n,k,1,[]int{})
return ans
}
func combineHelper(n int,k int,start int,item []int){
if len(item)==k{
copy_item:=make([]int,len(item))
copy(copy_item,item)
ans = append(ans,copy_item)
return
}
for i:=start;i<=n;i++{
item = append(item,i)
combineHelper(n,k,i+1,item)
item = item[:len(item)-1]
}
}
第二个角度1到4的数据选择还是不选择
var ans [][]int
func combine(n int, k int) [][]int {
ans = make([][]int,0)
combineHelper(n,k,[]int{},1)
return ans
}
func combineHelper(n int,k int,item []int,i int){
// 剪枝,不符合条件的提前退出
if len(item)>k || len(item)+n-i+1<k{
return
}
if i==n+1{
if k==len(item){
copy_item:=make([]int,len(item))
copy(copy_item,item)
ans = append(ans,copy_item)
}
return
}
combineHelper(n,k,item,i+1)
item = append(item,i)
combineHelper(n,k,item,i+1)
item = item[:len(item)-1]
}
46. 全排列
给定一个不含重复数字的数组 nums
,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1:
输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2:
输入:nums = [0,1] 输出:[[0,1],[1,0]]
示例 3:
输入:nums = [1] 输出:[[1]]
var ans [][]int
var ans_map map[int]bool
func permute(nums []int) [][]int {
ans = make([][]int,0,len(nums))
ans_map = make(map[int]bool,len(nums))
permuteHeper(nums,[]int{})
return ans
}
func permuteHeper(nums []int,item []int){
if len(item)==len(nums){
copy_item:=make([]int,len(item))
copy(copy_item,item)
ans = append(ans,copy_item)
return
}
for i:=0;i<len(nums);i++{
if _,ok:=ans_map[nums[i]];!ok{
ans_map[nums[i]] = true
item = append(item,nums[i])
permuteHeper(nums,item)
item = item[:len(item)-1]
delete(ans_map,nums[i])
}
}
}
原文地址:https://blog.csdn.net/xingjigongsi/article/details/138919136
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!