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

【20230227】回溯算法小结

回溯法又叫回溯搜索法,是搜索的一种方式。

回溯法本质是穷举所有可能。如果想让回溯法高效一些,可以加一些剪枝操作。

回溯算法解决的经典问题:

  • 组合问题

  • 切割问题

  • 子集问题

  • 排列问题

  • 棋盘问题

如何去理解回溯法?

回溯法解决的问题都可以抽象为树形结构,回溯法解决的是在集合中递归查找子集,集合的大小构成树的宽度,递归的深度构成树的深度。

递归就要有终止条件,所以必然是一颗高度有限的树(N叉树)

回溯法模板

回溯三部曲

  • 回溯函数模板返回值以及参数(一般返回值都为void)

  • 回溯函数终止条件

if(终止条件){存放结果;return;
}
  • 回溯搜索的遍历过程

for(选择:本层集合中的元素(树中节点孩子的数量就是集合的大小)){处理节点;backtracking(路径,选择列表);//递归回溯,撤销处理结果
}

组合问题

组合

在for循环中,i的结束条件可以优化,即:

列表剩余元素个数n-i+1>=所需元素个数k-path.size(),i<=n-k+path.size()+1。

组合总和

无重复数

可重复取

组合总和II

有重复数

不可重复取

组合总和III

无重复数

不可重复取

组合总和IV

无重复数

可重复取,且有排列(动规问题)

组合总和III

电话号码的字组合

数字与字母的映射问题可以用map,也可以用一个二维数组;

将char型转为int型,用char-‘0’的方式。

组合总和

可以重复使用元素,所以startIndex直接等于i就行了,不能直接每次都从0开始(这是排列的情况,会有重复出现);

组合总和II

集合中出现了重复元素,如果用之前的常规做法,会出现下面重复的情况,因此需要去重工作。

组合总和IV

用回溯超时了,是动态规划问题。


切割问题

分割回文串

  1. 如何切割的问题--确定分割点,例如abcdef,切割一个a后,在bvdef中再去切割第二段

  1. 如何判断为回文串--写一个bool型函数,专门用来判断

注意:截取子字符串substr(n,m)表示从下标n开始取m个元素

复原IP地址

  1. 如何切割的问题,确定切割点,插入.号,用已经插入.号的数量来判断是否结束

  1. 如何判断是否为有效IP地址

注意一些细节问题:

string中插入 insert 擦除erase,因为已经插入.号,因此下一层递归开始应该在i+2处

除了只有一个0以外,以0开头的数字不合法;大于255不合法;

    bool isValid(string& s,int left,int right){if(left>right)  return false;if(s[left]=='0'&&left!=right) return false;int x=stoi(s.substr(left,right-left+1));if(x<=255)  return true;else return false;}

子集问题

子集 (不含重复元素)

子集问题是找树的所有节点,而组合和分割问题都是收集树的叶子节点。

每个节点都需要保存,所以先存,再判断终止条件。

子集II (含有重复元素)

在同一层中不可选取相同元素,属于树层去重。

其实树层去重可以不用used数组,直接排序后判断相邻的数是否相同就可以完成树层去重。

注意:去重都需要排序!!!

递增子序列

需要解决的问题:

  1. 去重问题,仍然是树层的去重,但是不能对数组进行排序了,于是用哈希表进行去重;

  1. 选取的是符合条件的每个节点,其实可以与之前的联系起来,相当于可以不用写终止条件;


排列问题

全排列(没有重复元素)

排列问题就不需要startIndex了,需要使用used数组,来确定该数字在path中已经被取过了。

全排列II(有重复元素)

使用used数组+哈希表进行树枝去重和数层去重。


棋盘问题

重新安排行程

一个起飞机场对应多个降落机场、并且降落机场是有序的。所以映射后的降落机场用map去存。

map中所有元素都是pair,pair中第一个元素为key值(键值),第二个元素为value(实值)。

所有元素都会根据元素的键值自动排序。

unordered_map<string,map<string,int>> targets

相关文章:

【20230227】回溯算法小结

回溯法又叫回溯搜索法&#xff0c;是搜索的一种方式。回溯法本质是穷举所有可能。如果想让回溯法高效一些&#xff0c;可以加一些剪枝操作。回溯算法解决的经典问题&#xff1a;组合问题切割问题子集问题排列问题棋盘问题如何去理解回溯法&#xff1f;回溯法解决的问题都可以抽…...

centos安装rocketmq

centos安装rocketmq1 下载rocketmq二进制包2 解压二进制包3 修改broker.conf4 修改runbroker.sh和runserver.sh的JVM参数5 启动NameServer和Broker6 安装rockermq dashboard(可视化控制台)1 下载rocketmq二进制包 点击rocketmq二进制包下载地址&#xff0c;下载完成之后通过ft…...

汇编语言程序设计(二)之寄存器

系列文章 汇编语言程序设计&#xff08;一&#xff09; 寄存器 在学习汇编的过程中&#xff0c;我们经常需要操作寄存器&#xff0c;那么寄存器又是什么呢&#xff1f;它是用来干什么的&#xff1f; 它有什么分类&#xff1f;又该如何操作&#xff1f;… 你可能会有许多的…...

华为OD机试Golang解题 - 单词接龙 | 独家

华为Od必看系列 华为OD机试 全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典文章目录 华为Od必看系列使用说明本期题目…...

Elasticsearch的搜索命令

Elasticsearch的搜索命令 文章目录Elasticsearch的搜索命令数据准备URI Searchq&#xff08;查询字符串&#xff09;analyzer&#xff08;指定查询字符串时使用的分析器&#xff09;df&#xff08;指定查询字段&#xff09;_source&#xff08;指定返回文档的字段&#xff09;s…...

为什么人们宁可用Lombok,也不把成员设为public?

目录专栏导读一、从零了解JavaBean1、基本概念2、JavaBean的特征3、JavaBean的优点二、定义最简单的JavaBean三、思考一个问题&#xff0c;为何属性是private&#xff0c;然后用get/set方法&#xff1f;四、下面系统的分析以下&#xff0c;why?五、不和谐的声音&#xff0c;禁…...

【Redis】Redis 如何实现分布式锁

Redis 如何实现分布式锁1. 什么是分布式锁1.1 分布式锁的特点1.2 分布式锁的场景1.3 分布式锁的实现方式2. Redis 实现分布式锁2.1 setnx expire2.2 set ex px nx2.3 set ex px nx 校验唯一随机值&#xff0c;再删除2.4 Redisson 实现分布式锁1. 什么是分布式锁 分布式锁其实…...

C++ 断言

文章目录前言assertstatic_assert前言 断言(Assertion)是一种常用的编程手段&#xff0c;用于排除程序中不应该出现的逻辑错误。它是一种很好的Debug工具。其作用是判断表达式是否为真。C提供了assert和static_assert来进行断言。在C库中也有断言&#xff0c;其中断言与C的相同…...

C++修炼之练气期第五层——引用

目录 1.引用的概念 2.引用的性质 3.常量引用 4.使用场景 1.作参数 2.作返回值 5.传值与传引用的效率比较 6.值和引用作为返回值的性能比较 7.引用与指针 指针与引用的不同点 要说C语言中哪个知识点最难学难懂&#xff0c;大部分人可能和我一样的答案——指针。C既然…...

从企业数字化发展的四个阶段,看数字化创新战略

《Edge: Value-Driven Digital Transformation》一书根据信息技术与企业业务发展的关系把企业的数字化分为了四个阶段&#xff1a; 技术与业务无关技术作为服务提供者开始合作科技引领差异化优势以技术为业务核心 下图展示了这四个阶段的特点&#xff1a; 通过了解和分析各个…...

vulnhub five86-1

总结:私钥登录&#xff0c;隐藏文件很多 目录 下载地址 漏洞分析 信息收集 网站渗透 爆破密码 提权 下载地址 Five86-1.zip (Size: 865 MB)Download (Mirror): https://download.vulnhub.com/five86/Five86-1.zip使用&#xff1a;下载以后打开压缩包&#xff0c;使用vm直…...

28个案例问题分析---01---redis没有及时更新问题--Redis

redis没有及时更新问题一&#xff1a;背景介绍二&#xff1a;前期准备pom依赖连接Redis工具类连接mysql工具类三&#xff1a;过程使用redis缓存&#xff0c;缓存用户年龄业务对应流程图使用redis缓存用户年龄对应代码四&#xff1a;总结一&#xff1a;背景介绍 业务中使用redis…...

[1.3_3]计算机系统概述——系统调用

文章目录第一章 计算机系统概述系统调用&#xff08;一&#xff09;什么是系统调用&#xff0c;有何作用&#xff08;二&#xff09;系统调用与库函数的区别&#xff08;三&#xff09;小例子&#xff1a;为什么系统调用是必须的&#xff08;四&#xff09;什么功能要用到系统调…...

Vue基础学习 第一个Vue程序 el挂载点 v-指令(1)

Vue简介 Vue是一个Javascript框架Vue框架可以简化Dom操作响应式数据驱动 &#xff1a; 页面是由数据生成的&#xff0c;当数据出现改动&#xff0c;页面也会即时改变 第一个Vue程序 Vue中文文档官网&#xff1a;https://v2.cn.vuejs.org/v2/guide/ 根据官方文档的说法&#…...

前端页面性能

提升页面性能的方法资源压缩合并&#xff0c;减少HTTP请求非核心代码异步加载异步加载方式&#xff1f;1)动态脚本加载、2)defer、3)async&#xff08;在加载js的时候在script标签上添加这两个属性,<script src"./test.js" charset"utf-8" defer><…...

2023-03-04 反思

摘要: 当前的时期确实比较特殊&#xff0c;不但是对于一个生命周期的最后的挣扎&#xff0c;更是在经历了各种浮浮沉沉的波澜之后还有更多的波浪。 精神分析-GRY: 非常奇怪的一个跳梁小丑, 不过我个人认为用这个标签是对跳梁小丑的侮辱和上层管理者对于这种人的纵容有很大关系…...

奇思妙想:超链接唤起本地应用

文章目录分析实现参考很多人的博客都有这样的小玩意&#xff0c;点击之后就可以直接与博主进行对话&#xff0c;而且无需添加好友。 先研究一下网页源代码&#xff1a; <a href"tencent://message/?uin88888888&Siteqq&Menuyes">联系我</a>很明…...

初识数据结构——“数据结构与算法”

各位CSDN的uu们你们好呀&#xff0c;今天小雅兰进入一个全新的内容的学习&#xff0c;就是算法和数据结构啦&#xff0c;话不多说&#xff0c;让我们进入数据结构的世界吧 什么是数据结构&#xff1f; 什么是算法&#xff1f; 数据结构和算法的重要性 如何学好数据结构和算…...

华为OD机试Golang解题 - 计算网络信号

华为Od必看系列 华为OD机试 全流程解析+经验分享,题型分享,防作弊指南)华为od机试,独家整理 已参加机试人员的实战技巧华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典文章目录 华为Od必看系列使用说明本期题目…...

ESP32编译及运行错误记录

1、打印格式不对 一般都是因为日志中某个参数打印格式不匹配造成。 ESP_LOGI(TAG, "[APP] Free memory: %lu bytes", esp_get_free_heap_size());//将之前的%d 改为%lu 2、配置载不对 这里选择了蓝牙模块需要引入蓝牙组件才能编译通过 idf.py menuconfig Component…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...