递归-常规问题详解

目录

前言

递归经典题目

子集

77. 组合

46. 全排列


前言

递归在计算机算法中有很重要的地位,它可以解决条件具有重复性的问题。我们在快速排序和归并排序,都是利用了递归去解决问题的。写好一个递归代码不是太容易,很容易造成死循环最终内存泄漏。那么怎么写好递归代码呢,我总结了三点。

递归的三个关键:

  1. 定义需要递归的问题(重叠子问题)也就是说条件具有重复性。

  2. 递归边界

  3. 保护和还原现场

还是拿快排来说:快排的子问题就是分别对基准数据的左右子数据列分别排序,这个问题具有重复性,递归边界就是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. 组合

给定两个整数 nk,返回范围 [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]] = trueitem = append(item,nums[i])permuteHeper(nums,item)item = item[:len(item)-1]delete(ans_map,nums[i])}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1425122.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

吴恩达深度学习笔记:优化算法 (Optimization algorithms)2.8

目录 第二门课: 改善深层神经网络&#xff1a;超参数调试、正 则 化 以 及 优 化 (Improving Deep Neural Networks:Hyperparameter tuning, Regularization and Optimization)第二周&#xff1a;优化算法 (Optimization algorithms)2.8 Adam 优化算法(Adam optimization algor…

React 第三十七章 Scheduler 最小堆算法

在 Scheduler 中&#xff0c;使用最小堆的数据结构在对任务进行排序。 // 两个任务队列 var taskQueue: Array<Task> []; var timerQueue: Array<Task> [];push(timerQueue, newTask); // 像数组中推入一个任务 pop(timerQueue); // 从数组中弹出一个任务 time…

通过 Apple Vision Pro 释放创造力:深入研究空间计算

Apple 最新进军空间计算领域的 Apple Vision Pro,标志着重新定义我们与技术交互方式的重大飞跃。空间计算超越了传统界限,允许用户以无缝集成到物理世界的方式参与 2D 和 3D 内容。 我们可以关注两种类型的体验: 在空间中渲染 2D 内容。这涉及将现有设备窗口投影到空间领域…

QT:QML与C++交互

目录 一.介绍 二.pro文件添加模块 三.h文件 四.cpp文件 五.注册 六.调用 七.展示效果 八.代码 1.qmlandc.h 2.qmlandc.cpp 3.main.cpp 4.qml 一.介绍 在 Qt 中&#xff0c;QML 与 C 交互是非常重要的&#xff0c;因为它允许开发人员充分利用 QML 和 C 各自的优势&…

OpenAI GPT-4o:开启人工智能交互新纪元

引言 在人工智能领域&#xff0c;OpenAI一直是创新的代名词。2024年5月14日&#xff0c;OpenAI再次以GPT-4o模型震撼了科技界&#xff0c;这款全新的旗舰生成模型不仅免费向公众开放&#xff0c;更以其革命性的多模态交互能力&#xff0c;引领我们进入了一个全新的科幻时代。 …

位图和布隆过滤器:位图

在《unordered_map 和 unordered_set》 中提到过&#xff1a; 哈希是一种思想&#xff0c;通过哈希函数将数据转化为一个或多个整型 —— 映射关系&#xff1b;通过这种映射关系&#xff0c;可以做到以 O(1) 的时间复杂度查找数据。 本文即将介绍的 位图 和 布隆过滤器 就是两个…

亚马逊Prime Day旺季备货遭遇美国海关查验高峰,应对策略全攻略!

随着全球化贸易的日益繁荣&#xff0c;跨境电商企业在旺季备货时面临着巨大的挑战&#xff0c;尤其是当遇到美国海关查验潮时&#xff0c;如何应对成为众多商家关注的焦点。本文将从分析美国海关查验的原因入手&#xff0c;为商家提供一系列应对策略和建议。 一、美国海关查验潮…

​学者观察 | 从区块链应用创新看长安链发展——CCF区块链专委会荣誉主任斯雪明

导语 2024年1月27日&#xff0c;斯雪明教授在长安链发布三周年庆暨生态年会上发表演讲&#xff0c;认为在区块链发展过程中&#xff0c;不仅需要技术创新&#xff0c;同时需要有价值、有特色、有示范意义的应用创新。斯雪明教授介绍了国内区块链技术与应用发展的现状、趋势与挑…

SVN切换账号

SVN切换账号 有这么一种情况&#xff0c;对于一个新项目&#xff0c;项目紧急的情况下&#xff0c;大家会使用一个svn账号下载代码&#xff0c;开始提前熟悉业务。那么当正式开发的时候&#xff0c;每个人的svn账号也已经下发下来了&#xff0c;这个时候大家就需要切换成自己的…

C# .Net8 switch 的用法

在 .net 8中&#xff0c;switch 不需要再和传统的写法一样了&#xff0c;会更加的方便 创建一个 .net 8 控制台项目 switch 的写法没必要和以前一样 namespace SwitchTest {internal class Program{static void Main(string[] args){int day 3;var week day switch{1 > &…

AIGC文生视频:Sora模型报告总结

作为世界模拟器的视频生成模型 我们探索视频数据生成模型的大规模训练。具体来说&#xff0c;我们在可变持续时间、分辨率和宽高比的视频和图像上联合训练文本条件扩散模型。我们利用对视频和图像潜在代码的时空补丁进行操作的变压器架构。我们最大的模型 Sora 能够生成一分钟…

继承的奥秘:面向对象编程中的血脉传承与智慧抉择

1. 概述 在面向对象编程&#xff08;OOP&#xff09;中&#xff0c;继承是构建复杂软件系统的基石之一。它允许我们定义一个类&#xff08;称为父类或基类&#xff09;作为其他类&#xff08;称为子类或派生类&#xff09;的基础&#xff0c;子类能够自动获得父类的属性和方法…

Stable Diffusion超详细教程!本地部署 Stable Diffusion

前言 目前市面上比较权威&#xff0c;并能用于工作中的AI绘画软件其实就两款&#xff1a; Midjourney&#xff08;MJ&#xff09;Stable-Diffusion&#xff08;SD&#xff09; MJ需要付费使用&#xff0c;而SD开源免费&#xff0c;但是上手难度和学习成本略大&#xff0c;并…

抖店商品详情API接口(店铺|标题|主图|价格|SKU属性等)

抖店商品详情API接口(店铺|标题|主图|价格|SKU属性等) 抖店商品详情API接口是指通过调用抖音开放平台提供的接口&#xff0c;获取抖店上商品的详细信息的方法。 抖店开放平台提供了一系列的接口&#xff0c;可以用于获取商品的基本信息、价格、库存、销量、评价等各种信息。以…

【前段】开发五子棋小游戏全流程

使用前端技术开发五子棋小游戏 在这篇博文中&#xff0c;我们将详细介绍如何使用HTML、CSS和JavaScript开发一个简单的五子棋小游戏。我们将展示如何初始化棋盘、处理用户交互以及实现胜负判定。特别是&#xff0c;我们将着重介绍胜负判定的逻辑实现。 完整代码我放在了这里&a…

AI应用案例:吸烟打电话行为识别推理

使用百度PaddlePaddle&#xff08;现更名为PaddlePaddle-GPU或PaddlePaddle-CPU&#xff09;框架来构建精准的人员抽烟、打电话动作识别模型&#xff0c;并将其应用于加油站监控场景&#xff0c;你可以遵循以下步骤&#xff1a; 数据准备&#xff1a; 收集抽烟和打电话行为的图…

【Linux网络编程】传输层中的TCP和UDP(UDP篇)

【Linux网络编程】传输层中的TCP和UDP&#xff08;UDP篇&#xff09; 目录 【Linux网络编程】传输层中的TCP和UDP&#xff08;UDP篇&#xff09;传输层再谈端口端口号范围划分认识知名端口号netstatiostatpidofxargs UDP协议UDP协议端格式UDP的特点面向数据报UDP的缓冲数据UDP使…

基于springboot实现大学生就业需求分析系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现大学生就业需求分析系统演示 摘要 信息数据从传统到当代&#xff0c;是一直在变革当中&#xff0c;突如其来的互联网让传统的信息管理看到了革命性的曙光&#xff0c;因为传统信息管理从时效性&#xff0c;还是安全性&#xff0c;还是可操作性等各个方面来讲…

linux系统查看服务器硬件信息

1、查看服务器型号、序列号 # dmidecode|grep "System Information" -A9 | egrep "Manufacturer|Product|Serial" 2、查看主板型号 # dmidecode |grep -A16 "System Information$" 或 dmidecode -t1 3、查看BIOS信息 # dmidecode -t bios 4、…

绘唐2跟绘唐3有什么区别

绘唐2跟绘唐3有什么区别 这款产品的最大亮点在于其高度精准的语音克隆能力&#xff0c;利用先进的模型&#xff0c;能够捕捉到用户独特的音调、音高和调制方式&#xff0c;使用户能够以前所未有的方式复制和利用自己的声音。仅需10秒钟的录制时间&#xff0c;即可实现声音的克…