【面试高频算法解析】算法练习2 回溯

目录

  • 前言
  • 算法解析
  • 练习题
    • 组合总和
    • 全排列II
    • 单词搜索

前言

本篇章开放目的是按算法类型学习算法,学习对应算法理论,并通过练习一些经典算法题深入理解这类算法,避免出现刷了很多算法题,还是一知半解的状态


算法解析

回溯(Backtracking)是一种通过试错来解决问题的算法思想。当它通过尝试分步去解决一个问题时,如果发现现有的分步答案不能得到有效的正确的解答时,它将取消上一步甚至是上几步的计算,再通过其他的可能的分步解答再次尝试寻找问题的答案。

回溯法通常用递归方式来实现,在解决问题的过程中尝试各种可能的分步方法。如果某一步骤失败了,回溯算法会退回到上一步骤,然后尝试另一种方法。回溯法常用于解决如下问题:

  • 组合问题:求解一个问题的所有满足条件的组合方式。
  • 排列问题:求解一个问题的所有满足条件的排列方式。
  • 划分问题:求解将一个对象分成几部分的方法。
  • 子集构造问题:求解一个集合的所有子集。
  • 棋盘问题:如八皇后问题、解数独和跳马问题等。
  • 图的遍历问题:如哈密顿路径问题、图的着色问题等。

回溯算法的关键在于解决决策树的遍历过程中,如何剪枝。剪枝通过检测是否已经不可能得到正确的解来减少不必要的计算。在实现回溯算法时,通常有以下几个步骤:

  1. 选择:选择下一个可能的分步解答。
  2. 约束:检查到目前为止的解答序列是否满足约束条件(即是否“合法”)。
  3. 目标:检查到目前为止的解答序列是否满足解答条件(即是否已经找到一个解答)。

如果以上步骤中的任何一步不能继续下去,那么就执行回溯(返回上一步),尝试其他可能的路径。这种算法可以看作穷举搜索的一种优化,它利用问题的约束条件大大减少了搜索空间。

回溯算法和深度优先搜索(DFS)有密切的关系,实际上,回溯算法可以视为带有剪枝功能的深度优先搜索。在实现时,通常使用递归方法来模拟整个决策树的深度优先遍历过程,递归结构的本质上是栈结构,与DFS的实现方式一致。


练习题

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例 1:
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]

解释:
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

示例 2:
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3:
输入: candidates = [2], target = 1
输出: []

提示:
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

官方题解


全排列II

给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

示例 1:
输入:nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,1,1]]

示例 2:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示:
1 <= nums.length <= 8
-10 <= nums[i] <= 10

官方题解


单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1:
请添加图片描述

输入:board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
输出:true

示例 2:
请添加图片描述

输入:board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE”
输出:true

示例 3:
请添加图片描述
输入:board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB”
输出:false

提示:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

进阶: 你可以使用搜索剪枝的技术来优化解决方案,使其在 board 更大的情况下可以更快解决问题?

官方题解

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

UDP通信(服务器-客户端)

一、 UDP服务器-客户端通信 UDP&#xff08;User Datagram Protocol&#xff09;是一种面向无连接的传输层协议&#xff0c;它提供了一种简单的、不可靠的数据传输服务。与TCP&#xff08;Transmission Control Protocol&#xff09;不同&#xff0c;UDP不建立连接&#xff0c;…

FusionAccess配置Lite AD

1、Lite AD的安装及配置 Lite AD流程&#xff1a; &#xff08;1&#xff09;创建一个新的Windows 10&#xff0c;安装tools&#xff0c;再安装ITA组件&#xff08;安装Lite AD会自动安装VAG/VLB&#xff09; &#xff08;2&#xff09;创建一个新的Windows 10&#xff0c;安…

线性规划中解的关系

写于&#xff1a;2024年1月2日星期二 修改于&#xff1a; 本文从两个角度对线性规划中的解做划分&#xff0c;角度一是将解划为基解、基可行解、可行解&#xff1b;角度二是将解划分为无可行解、无界解、最优解&#xff08;唯一和无穷多&#xff09;。同时&#xff0c;详细描述…

【计算机视觉网络训练技巧】你知道你拿什么图片在训练吗?训练图片可视化简易版

以下是一张图片&#xff0c;数据增广之后的示意图&#xff1a; 问题是这样的&#xff0c;当数据增广后&#xff0c;我们怎么知道图片变成什么样了呢&#xff0c;或者说我们输入到网络中的图片长什么样&#xff1f;对&#xff0c;解法很简单&#xff0c;就是在图片输入到网络时…

C++的基础语句

C前奏 1.变量的定义2.键入和输出3.运算符4.sizeof()函数5.判断6.goto语句7.总结 这个专题&#xff0c;我会用简单的语言介绍C的语法&#xff0c;并会适当的对比实现相同或相似功能的C与python代码写法上的不同。 1.变量的定义 对于python来说&#xff0c;我们可以跳过定义直接…

Efficient Classification of Very Large Images with Tiny Objects(CVPR2022补1)

文章目录 Two-stage Hierarchical Attention SamplingsummaryOne-stageTwo-Stage内存需求 Efficient Contrastive Learning with Attention Sampling Two-stage Hierarchical Attention Sampling summary 从一个大图像中按照指定的低分辨率比例和位置提取出一个小图块 一阶段…

web前端——clear可以清除浮动产生的影响

clear可以解决高度塌陷的问题&#xff0c;产生的副作用要小 未使用clear之前 <!DOCTYPE html> <head><meta charset"UTF-8"><title>高度塌陷相关学习</title><style>div{font-size:50px;}.box1{width:200px;height:200px;backg…

阿里云盘在线自动签到-无需部署

声明&#xff1a;本文的代码内容来源于知乎用户小猪猪和艾欧娜传播此内容是基于学术研究和学习目的&#xff0c;遵循了适用的版权规定和学术研究的合理使用原则。 作者只对源代码进行了一点点改动&#xff0c;本文主要演示如何使用金山文档的每日定时任务&#xff0c;执行阿里云…

nccl 源码安装与应用示例 附源码

1&#xff0c; 官方下载网址 注意&#xff0c;本文并不使用nv预编译的包来安装&#xff0c;仅供参考&#xff1a; NVIDIA Collective Communications Library (NCCL) | NVIDIA Developer 2&#xff0c;github网址 这里是nv开源的nccl源代码&#xff0c;功能完整&#xff0c;不…

Adobe Experience Design安装指南

XD&#xff08;Adobe Experience Design&#xff09;下载链接 https://pan.baidu.com/s/1MVcaE2GB1Q9YpgmgDxUGJw?pwd0531 1.鼠标右击【Adobe XD 55.1(64bit)】压缩包选择&#xff08;win11以上系统需先点击“显示更多选项”&#xff09;【解压到 Adobe XD 55.1(64bit)】。 …

《JVM由浅入深学习【四】 2023-12-24》JVM由简入深学习提升分享

JVM由简入深学习提升分享四 1.JVM中java堆的特点及作用2. JVM中对象如何在堆内存中分配3. JVM堆内存中的对象布局 1.JVM中java堆的特点及作用 是线程共享的一块区域虚拟机启动时就创建了是虚拟机中内存占用很大的一块存放所有的实例对象和数组GC主要的作用区域可分为新生代&am…

关于“Python”的核心知识点整理大全50

目录 python_repos.py 17.1.6 概述最受欢迎的仓库 python_repos.py 17.1.7 监视 API 的速率限制 注意 17.2 使用 Pygal 可视化仓库 python_repos.py 17.2.1 改进 Pygal 图表 python_repos.py 往期快速传送门&#x1f446;&#xff08;在文章最后&#xff09;&#xf…

09、docker 安装nacos并配置mysql存储配置信息

docker 安装nacos并配置mysql存储配置信息 1、docker启动nacos的各种方式2、Docker安装nacos3、MySQL中新建nacos的数据库4、挂载数据or配置目录5、运行 1、docker启动nacos的各种方式 内嵌derby数据源 docker run -d \ -e PREFER_HOST_MODEhostname \ -e SPRING_DATASOURCE_…

python旅游大数据分析可视化大屏 游客分析+商家分析+舆情分析 计算机毕业设计(附源码)Flask框架✅

毕业设计&#xff1a;2023-2024年计算机专业毕业设计选题汇总&#xff08;建议收藏&#xff09; 毕业设计&#xff1a;2023-2024年最新最全计算机专业毕设选题推荐汇总 &#x1f345;感兴趣的可以先收藏起来&#xff0c;点赞、关注不迷路&#xff0c;大家在毕设选题&#xff…

详解静态网页数据获取以及浏览器数据和网络数据交互流程-Python

目录 前言 一、静态网页数据 二、网址通讯流程 1.DNS查询 2.建立连接 3.发送HTTP请求 4.服务器处理请求 5.服务器响应 6.渲染页面 7.页面交互 三、URL/POST/GET 1.URL 2.GET 形式 3.POST 形式 四.获取静态网页数据 1.requests库 点关注&#xff0c;防走丢&am…

Linux vi/vim 教程

文章目录 【 1. vi/vim 的三种模式 】1.1 命令模式1.2 输入模式1.3 底线命令模式 【 2. 实例 】【 3. vim 的其他命令 】 所有的 Unix Like 系统都会内建 vi 文本编辑器&#xff0c;其他的文本编辑器则不一定会存在。目前我们使用比较多的是 vim 编辑器。vim 从 vi 发展出来&am…

深度确定性策略梯度 DDPG

深度确定性策略梯度 DDPG 深度确定性策略梯度 DDPG模型结构目标函数算法步骤适合场景 深度确定性策略梯度 DDPG A2C、A3C 都是在线策略&#xff0c;在与环境交互时&#xff0c;样本参数更新效率低&#xff0c;所以主要是应用在离散空间&#xff0c;计算量没那么大。 DDPG 专用…

aps审核-模电英文稿

模拟电子线路 Analog circuit 需要熟悉课程名&#xff0c;一句话简单概括课程内容&#xff0c;准备一些重点内容介绍。 This course mainly introduces the properties(n.性质) of semiconductors(半导体) and transistors, and then analyzes and masters amplification circ…

算法专题四:前缀和

前缀和 一.一维前缀和(模板)&#xff1a;1.思路一&#xff1a;暴力解法2.思路二&#xff1a;前缀和思路 二. 二维前缀和(模板)&#xff1a;1.思路一&#xff1a;构造前缀和数组 三.寻找数组的中心下标&#xff1a;1.思路一&#xff1a;前缀和 四.除自身以外数组的乘积&#xff…

java企业人事信息管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 java Web企业人事信息管理系统是一套完善的java web信息管理系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境 为TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为M…