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

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群集中。 具体可参…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

Go 语言并发编程基础:无缓冲与有缓冲通道

在上一章节中&#xff0c;我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道&#xff0c;它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好&#xff0…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...