当前位置: 首页 > news >正文

回溯算法题型分类

题型一:排列、组合、子集相关问题

提示:这部分练习可以帮助我们熟悉「回溯算法」的一些概念和通用的解题思路。解题的步骤是:先画图,再编码。去思考可以剪枝的条件, 为什么有的时候用 used 数组,有的时候设置搜索起点 begin 变量,理解状态变量设计的想法。

  • 46. 全排列(中等)
  • 47. 全排列 II(中等):思考为什么造成了重复,如何在搜索之前就判断这一支会产生重复;
  • 39. 组合总和(中等)
  • 40. 组合总和 II(中等)
  • 77. 组合(中等)
  • 78. 子集(中等)
  • 90. 子集 II(中等):剪枝技巧同 47 题、39 题、40 题;
  • 60. 第 k 个排列(中等):利用了剪枝的思想,减去了大量枝叶,直接来到需要的叶子结点;
  • 93. 复原 IP 地址(中等)

题型二:Flood Fill

提示:Flood 是「洪水」的意思,Flood Fill 直译是「泛洪填充」的意思,体现了洪水能够从一点开始,迅速填满当前位置附近的地势低的区域。类似的应用还有:PS 软件中的「点一下把这一片区域的颜色都替换掉」,扫雷游戏「点一下打开一大片没有雷的区域」。

下面这几个问题,思想不难,但是初学的时候代码很不容易写对,并且也很难调试。我们的建议是多写几遍,忘记了就再写一次,参考规范的编写实现(设置 visited 数组,设置方向数组,抽取私有方法),把代码写对。

  • 733. 图像渲染(Flood Fill,中等)
  • 200. 岛屿数量(中等)
  • 130. 被围绕的区域(中等)
  • 79. 单词搜索(中等)

说明:以上问题都不建议修改输入数据,设置 visited 数组是标准的做法。可能会遇到参数很多,是不是都可以写成成员变量的问题,面试中拿不准的记得问一下面试官

题型三:字符串中的回溯问题

提示:字符串的问题的特殊之处在于,字符串的拼接生成新对象,因此在这一类问题上没有显示「回溯」的过程,但是如果使用 StringBuilder 拼接字符串就另当别论。
在这里把它们单独作为一个题型,是希望朋友们能够注意到这个非常细节的地方。

  • 17. 电话号码的字母组合(中等),题解;
  • 784. 字母大小写全排列(中等);
  • 22. 括号生成(中等) :这道题广度优先遍历也很好写,可以通过这个问题理解一下为什么回溯算法都是深度优先遍历,并且都用递归来写。

题型四:游戏问题

回溯算法是早期简单的人工智能,有些教程把回溯叫做暴力搜索,但回溯没有那么暴力,回溯是有方向地搜索。「力扣」上有一些简单的游戏类问题,解决它们有一定的难度,大家可以尝试一下。

  • 51. N 皇后(困难):其实就是全排列问题,注意设计清楚状态变量,在遍历的时候需要记住一些信息,空间换时间;
  • 37. 解数独(困难):思路同「N 皇后问题」;
  • 488. 祖玛游戏(困难)
  • 529. 扫雷游戏(困难)

相关文章:

回溯算法题型分类

题型一:排列、组合、子集相关问题 提示:这部分练习可以帮助我们熟悉「回溯算法」的一些概念和通用的解题思路。解题的步骤是:先画图,再编码。去思考可以剪枝的条件, 为什么有的时候用 used 数组,有的时候设…...

ApplicationRunner 类

优质博文:IT-BLOG-CN 在开发中可能会有这样的情景。需要在容器启动的时候执行一些内容。比如读取配置文件,数据库连接之类的。SpringBoot给我们提供了两个接口来帮助我们实现这种需求。这两个接口分别为CommandLineRunner和ApplicationRunner。他们的执…...

QT中的 容器(container)-大全

一、介绍 Qt库提供了一套通用的基于模板的容器类&#xff0c;可以用这些类存储指定类型的项。比如&#xff0c;你需要一个大小可变的QString的数组&#xff0c;则使用QVector<QString>。 这些容器类比STL&#xff08;C标准模板库&#xff09;容器设计得更轻量、更安全并…...

Docker配置镜像加速器

Ubuntu 安装&#xff0f;升级Docker客户端 推荐安装1.10.0以上版本的Docker客户端&#xff0c;参考文档docker-ce配置镜像加速器 针对Docker客户端版本大于 1.10.0 的用户 您可以通过修改daemon配置文件/etc/docker/daemon.json来使用加速器 sudo mkdir -p /etc/docker sudo t…...

飞致云1panel + 雷池WAF

可能有许多人都有这个需求&#xff1a;为自己的个人站点套上WAF&#xff0c;增加安全性&#xff0c;本文将介绍如何将1panel面板深度结合长亭雷池防火墙&#xff0c;实现为个人站点套上WAF并且自动续签ssl证书。 前提条件&#xff1a; 服务器IP已绑定域名 完整的1panel环境 …...

策略梯度简明教程

策略梯度方法 (PG&#xff1a;Policy Gradient) 是强化学习 (RL&#xff1a;Reinforcement Learning) 中常用的算法。 1、从库里的本能开始 PG的原理很简单&#xff1a;我们观察&#xff0c;然后行动。人类根据观察采取行动。 引用斯蒂芬库里的一句话&#xff1a; 你必须依靠…...

鸿蒙原生应用/元服务开发-利用picker选择器来多选相册图片

前言 在之前的时候&#xff0c;测试一个应用进入相册选择图片demo&#xff0c;利用了startAbilityForResult()方法&#xff0c;启动相对应的Ability来完成效果&#xff0c;但是这种方法有限制&#xff0c;一次只能获取一张图片&#xff0c;在完成某些功能测试的时候就很不方便。…...

java:封装统一的响应体code、data、msg、paging

背景 我们在写接口的时候一般不会直接返回给前端数据&#xff0c;而是会有响应体&#xff0c;比如 code、data、msg&#xff0c;这样就有一个统一的结构方便前端处理&#xff0c;那么今天就来封装一个统一的响应体 封装基本响应体 1、在 config 包里新建 ApiResponse.java …...

leetcode算法之栈

目录 1.删除字符串中的所有相邻重复项2.比较含退格的字符串3.基本计算器II4.字符串解码5.验证栈序列 1.删除字符串中的所有相邻重复项 删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {string ret;//使用数组模拟栈操作for(auto …...

电脑上mp4视频文件无缩略图怎么办

前言&#xff1a;有时候电脑重装后电脑上的mp4视频文件无缩略图&#xff0c;视频文件数量比较多的时候查找比较麻烦 以下方法亲测有效&#xff1a; 1、下载MediaPreview软件 2、软件链接地址&#xff1a;https://pan.baidu.com/s/1bzVJpmcHyGxXNjnzltojtQ?pwdpma0 提取码&…...

【Centos8】配置网络镜像源

文章目录 配置 yum 源配置网络 yum 源备份下载阿里 centos-base.repo 到 /etc/yum.repos.d/安装 EPEL 源测试安装 配置 yum 源 # 检查是否安装了 yum rpm -qa|grep yum# 查看本地已安装的所有软件包 yum list installed# 查看软件包安装位置 # 查看某个东西的软件包 rpm -qa|g…...

深入学习Synchronized各种使用方法

文章目录 前言一、synchronized关键字通用在下面四个地方&#xff1a;1.1synchronized修饰实例方法1.2synchronized修饰静态方法&#xff1a;1.3synchronized修饰实例方法的代码块1.4synchronized修饰静态方法的代码块2.读入数据 二.Sychronized关键特性2.1互斥2.2 刷新内存2.3…...

【idea】设置鼠标滚轮控制缩放大小

1、点击file 选择Setting 2、点击Editor 下面的 General 3、勾选 Mouse Control 下面的 Change font size with CtrlMouse Wheel in 4、点级apply 5、按 ctrl键 鼠标滚轮缩放字体的大小...

合并两个有序数组(leetcode_刷题1)

目录 题目&#xff1a;合并两个有序数组 题目分析方向1&#xff1a; 题目分析方向2&#xff1a; 题目&#xff1a;合并两个有序数组 题目要求&#xff1a; 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2&#xff0c;另有两个整数 m 和 n &#xff0c;分别表示 nums…...

麒麟linux将图片批量生成PDF的方法

笔者手里有一批国产linu系统&#xff0c;目前开始用在日常的工作生产环境中&#xff0c;我这个老程序猿勉为其难的充当运维的或网管的角色。 国产linux系统常见的为麒麟Linux&#xff0c;统信UOS等&#xff0c;基本都是基于debian再开发的linux。 问题描述&#xff1a; wind…...

Linux——vim编辑文件时——.swp文件解决方案

test.cpp样例 当我们vim test.cpp进入编辑文件。 却忘记了保存退出 再次进入就会出现一下画面 当你摁下Enter键位 出现以下几个选项 O——是只读不写 E——是正常打开文件但不会载入磁盘内容 R——覆盖——是加载存储磁盘的文件(当我们忘记保存时&#xff0c;系统会自动帮我…...

【Maven】清理 maven 仓库

初始情况下&#xff0c;我们的本地仓库是没有任何jar包的&#xff0c;此时会从私服去下载&#xff08;如果没有配置&#xff0c;就直接从中央仓库去下载&#xff09;。 可能由于网络的原因&#xff0c;jar包下载不完全&#xff0c;这些不完整的jar包都是以lastUpdated结尾。此…...

APOLLO自动驾驶技术沙龙:未来已来,共创智能交通新时代

在这次Apollo会议上&#xff0c;我深刻地感受到了人工智能自动驾驶技术领域的最新进展和未来趋势。作为一名从事软件开发工作的人员&#xff0c;我深感荣幸能够参加这次盛会。 前言 本次活动是百度Apollo社区工程师齐聚首钢Park&#xff0c;带来现场实操与技术分享。主要围绕Ap…...

Java面试题12

1.redis 怎么实现分布式锁&#xff1f; Redis可以通过以下方式实现分布式锁&#xff1a; 使用RedLock算法&#xff1a;多个Redis节点组合使用&#xff0c;通过竞争锁来达到分布式锁的效果。使用SETNX命令&#xff1a;利用SETNX&#xff08;SET if Not eXists&#xff09;命令…...

ubuntu上创建服务启动python脚本

场景 最近在使用ubuntu服务器部署MySQL和同步数据&#xff0c;同步数据使用的是python&#xff0c;但是我不能直接操作服务器&#xff0c;只能通过Xshell远程访问服务器&#xff0c;但是启动python脚本的时候如果关掉xshell会停止Python脚本&#xff0c;所以如果要让python脚本…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

Matlab实现任意伪彩色图像可视化显示

Matlab实现任意伪彩色图像可视化显示 1、灰度原始图像2、RGB彩色原始图像 在科研研究中&#xff0c;如何展示好看的实验结果图像非常重要&#xff01;&#xff01;&#xff01; 1、灰度原始图像 灰度图像每个像素点只有一个数值&#xff0c;代表该点的​​亮度&#xff08;或…...