当前位置: 首页 > 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脚本…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙

Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...

前端工具库lodash与lodash-es区别详解

lodash 和 lodash-es 是同一工具库的两个不同版本&#xff0c;核心功能完全一致&#xff0c;主要区别在于模块化格式和优化方式&#xff0c;适合不同的开发环境。以下是详细对比&#xff1a; 1. 模块化格式 lodash 使用 CommonJS 模块格式&#xff08;require/module.exports&a…...