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

回溯算法章末总结

在这里插入图片描述

  1. 组合问题的特点
    (1)ab=ba 选中a之后,就不再选了
    (2)找出所有的组合 (长度可以不相等)

  2. 组合问题模板
    在这里插入图片描述

  3. 做回溯题步骤
    在这里插入图片描述

    (0)判断问题类型
    (1)树状图
    (2)递归三部曲
    (3)剪枝条件

  4. 组合问题中的纵横剪枝 ----> 216.组合总和III
    ==有图==

  5. 去重
    (1)横向去重
    在这里插入图片描述
    (2)set横向去重

在这里插入图片描述

代码

 public void findSubsequencesBT(int[] nums,int startIndex) {HashSet<Integer> set = new HashSet<>();for (int i = startIndex; i < nums.length; i++) {// 剪枝if (findSubsequencesPath.size()>0&&findSubsequencesPath.get(findSubsequencesPath.size()-1)[0]>nums[i]){continue;}// 此处不能是==,只能是>= 为空时也要判断去重if ((findSubsequencesPath.size()==0||findSubsequencesPath.size()>0&&findSubsequencesPath.get(findSubsequencesPath.size()-1)[0]<=nums[i])&&set.contains(nums[i])){continue;}//三件套//using[i]=true;findSubsequencesPath.add(new int[]{nums[i],i});set.add(nums[i]);if (findSubsequencesPath.size()>=2){ArrayList<Integer> temp = new ArrayList<>();for (int j = 0; j <findSubsequencesPath.size() ; j++) {temp.add(findSubsequencesPath.get(j)[0]);}ires.add(temp);}findSubsequencesBT(nums,i+1);findSubsequencesPath.remove(findSubsequencesPath.size()-1);// set 不用回溯,每层一个// using[i]=false;}}

关键
在这里插入图片描述

  1. 分割递归终止条件
    分割常用的递归出口
    (1)startIndex==数组长度
    缺点: 如果是分割有段数要求,例如ip,可能分割很多段后才到递归出口,1.1.1.1.1.1.1 再判断,白白浪费性能。
    改进:当已经分割三段时,第四段直接判断,这样可以剪掉部分,但是最后还是会一个一个试
   public void restoreIpAddressesBT(String s,int startIndex) {if (startIndex==s.length()){if (restoreIpAddressesPath.size()==4){StringBuilder sb = new StringBuilder();for (String s1 : restoreIpAddressesPath) {sb.append(s1+".");}sb.delete(sb.length()-1,sb.length());slist.add(sb.toString());}return;}for (int i = startIndex; i <s.length() ; i++) {String substring = s.substring(startIndex, i + 1);// 剪枝// 如果已经有3个了,直接看剩下的能不能凑成第四个就行if (restoreIpAddressesPath.size()==3&&valIsValid(s.substring(startIndex))==-1){return;  // 本层全不能用}if (valIsValid(substring)==-1){continue;}restoreIpAddressesPath.add(substring);restoreIpAddressesBT(s,i+1);restoreIpAddressesPath.remove(restoreIpAddressesPath.size()-1);}}

(2)如果有段数要求,直接用段数作为剪枝条件

  if (restoreIpAddressesPath.size()==4){if (startIndex==s.length()){StringBuilder sb = new StringBuilder();for (String s1 : restoreIpAddressesPath) {sb.append(s1+".");}sb.delete(sb.length()-1,sb.length());slist.add(sb.toString());}return;}

在这里插入图片描述
这样只要到段数,就会判断,不会再 1.1.1.1.1.1.1这样分

题型

组合问题

每条从根出发的子路径是一个结果

  1. 传统组合问题 每一条子路径都是一种组合 —>● 77. 组合● 216.组合总和III
  2. 从筐中取球类型–>● 17.电话号码的字母组合
  3. 组合,元素不重,元素可重复取 39. 组合总和
  4. 组合,元素重复,结果不重,横向去重–> 40.组合总和II

子集问题

  1. 组合问题之子集问题,找到所有从根节点出发的子路径,包含【】
    ---->78.子集
  2. 组合问题之递增序列,本质是子集问题,使用set去重,注意第一层时path可能为空 491.递增子序列

分割

每条路径是一个结果
5. 标准分割 --> 131.分割回文串 ● 93.复原IP地址

排列

  1. 排列,借助used数组 46.全排列 47.全排列 II

递归树

  1. 传统组合
    在这里插入图片描述

  2. 筐中取球
    在这里插入图片描述

  3. 组合,每个元素可重复
    在这里插入图片描述

  4. 组合,元素重复,结果不重,横向去重
    在这里插入图片描述

  5. 标准分割
    在这里插入图片描述
    (2)分割模板

// 131.分割回文串 public void partitionBT(String s,int startIndex) {if (startIndex==s.length()){sres.add(new ArrayList<>(spath));return;}// 引擎for (int i = startIndex; i <s.length() ; i++) {// 剪枝if (!isPalindrome(s,i,startIndex)){return;}spath.add(s.substring(i, startIndex + 1));partitionBT(s,i+1);spath.remove(spath.size()-1);// 本层下一个}}

(3)不同之处
在这里插入图片描述
6. 子集问题
78.子集
(2)子集问题模板

 // 78. 子集public void subsetsBT(int[] nums,int startIndex) {// 找所有从根节点的子路径,为处理空置,先加入ires.add(new ArrayList<>(ipath));// 递归终止条件  直接使用循环终止// 循环引擎for (; startIndex <nums.length ; startIndex++) {// 剪枝 无//三件套ipath.add(nums[startIndex]);subsetsBT(nums,startIndex+1);ipath.remove(ipath.size()-1); //  删除的是startIndex}}

(3)不同之处
在这里插入图片描述
7. 递增序列问题

在这里插入图片描述

代码

 public void findSubsequencesBT(int[] nums,int startIndex) {HashSet<Integer> set = new HashSet<>();for (int i = startIndex; i < nums.length; i++) {// 剪枝if (findSubsequencesPath.size()>0&&findSubsequencesPath.get(findSubsequencesPath.size()-1)[0]>nums[i]){continue;}// 此处不能是==,只能是>= 为空时也要判断去重if ((findSubsequencesPath.size()==0||findSubsequencesPath.size()>0&&findSubsequencesPath.get(findSubsequencesPath.size()-1)[0]<=nums[i])&&set.contains(nums[i])){continue;}//三件套//using[i]=true;findSubsequencesPath.add(new int[]{nums[i],i});set.add(nums[i]);if (findSubsequencesPath.size()>=2){ArrayList<Integer> temp = new ArrayList<>();for (int j = 0; j <findSubsequencesPath.size() ; j++) {temp.add(findSubsequencesPath.get(j)[0]);}ires.add(temp);}findSubsequencesBT(nums,i+1);findSubsequencesPath.remove(findSubsequencesPath.size()-1);// set 不用回溯,每层一个// using[i]=false;}}

关键
在这里插入图片描述
8. 排列

    public void permuteBT(int[] nums,boolean[] used) {if (ipath.size()==nums.length){ires.add(new ArrayList<>(ipath));return;}for (int i = 0; i <nums.length ; i++) {if (used[i]==true){continue;}// 剪枝// 三件套used[i]=true;ipath.add(nums[i]);permuteBT(nums,used);ipath.remove(ipath.size()-1);used[i]=false;}}

在这里插入图片描述

相关文章:

回溯算法章末总结

组合问题的特点 &#xff08;1&#xff09;abba 选中a之后&#xff0c;就不再选了 &#xff08;2&#xff09;找出所有的组合 &#xff08;长度可以不相等&#xff09; 组合问题模板 做回溯题步骤 &#xff08;0&#xff09;判断问题类型 &#xff08;1&#xff09;树状图 …...

【SpringBoot】为异步任务规划线程池

一、线程池的作用 防止资源占用无限的扩张调用过程省去资源的创建和销毁所占用的时间 在上一节中&#xff0c;我们的一个异步任务打开了一个线程&#xff0c;完成后销毁。在高并发环境下&#xff0c;不断的分配新资源&#xff0c;可能导致系统资源耗尽。所以为了避免这个问题…...

SAP ABAP 输出结果带有空格

方法一&#xff1a; 字段内容前增加空格&#xff0c;需使用全角空格&#xff0c;使用半角空格时&#xff0c;ALV显示无效&#xff0c;空格无法显示&#xff0c; 全角与半角的切换方法&#xff1a;shift空格切换&#xff0c; 如下的标记部分&#xff0c;要想通过ALV显示空格&…...

Opengl ES之踩坑记

前因 最近在尝试使用Opengl ES实现一些LUT滤镜效果&#xff0c;在实现这些滤镜效果的时候遇到一些兼容性的坑&#xff0c;踩过这些坑后我希望把这几个坑分享给读者朋友们&#xff0c; 希望同在学习Opengl ES的朋友们能少走弯路。 关于LUT滤镜相关的介绍&#xff0c;也是这个O…...

设计模式第六讲:责任链模式和迭代器模式详解

一. 责任链模式1. 背景在现实生活中&#xff0c;常常会出现这样的事例&#xff1a;一个请求有多个对象可以处理&#xff0c;但每个对象的处理条件或权限不同。例如&#xff0c;公司员工请假&#xff0c;可批假的领导有部门负责人、副总经理、总经理等&#xff0c;但每个领导能批…...

K8s 架构简介(一)

一、前言 在开始学习K8s之前&#xff0c;让我们对容器有一个基本的了解 1.1 什么是容器 一个容器镜像是一个可运行的软件包&#xff0c;其中包含了一个完整的可执行程序&#xff0c;包括代码和运行时需要应用、系统库和全部重要设置的默认值。 通过将应用程序本身&#xff…...

xshell6运行报错:由于找不到mfc110u.dll、MSVCR110.dll无法继续执行代码

今天给大家分享一下我刚装完系统遇到得问题,由于新盟的罗建雨【胡巴】老师帮我给电脑加了固态,又重装了系统,因此电脑里面得所有软件需要重装,在我重装的过程中遇到了一个小问题给大家分享一下,如果大家以后遇到也方便解决。 问题: 安装Xshell时电脑系统报错:“由于找…...

Baklib知识库管理平台,协助组织提升知识管理水平

随着信息时代和知识经济时代的到来&#xff0c;企业内部信息资料繁多冗杂&#xff0c;知识管理逐渐成为各大企业的重要工作之一&#xff0c;企业管理者无不感受到巨大的压力&#xff0c;怎么样将知识进行有效的管理&#xff0c;成为一个难点&#xff0c;并且随着信息不断的更迭…...

一文搞懂core-scheduling核心机制

cookie的原理借助于unsigned long型&#xff0c;和refcount_t引用计数器。 32位64位char *4字节8字节unsigned long4字节8字节 数据结构修改 首先看看实现core scheduling功能对数据结构有哪些修改 task_struct struct task_struct{struct rb_node core_node;unsigned long…...

IP地址在金融行业有哪些应用?

中国加入WTO以来经济得到迅速发展&#xff0c;金融行业随着经济发展体系越来越完善。随着西方金融公司和理念的加入中国金融行业开始多样化发展。金融行业在快速发展的同时也引发了许多弊端。如何维护挖掘客户更大需求&#xff1f;如何获取更多优质客户&#xff1f;如何提升网络…...

GT-suite v2016解决许可证过期问题(附新版liscense下载地址)

安装GT-suite v2016时遇到了如图报错的问题。当时的报错找不到了&#xff0c;下图是贴吧相同问题的报错图。 为了解决问题&#xff0c;先根据某网友的如下答复操作&#xff1a; 添加环境变量后仍然有相同报错。 看来需要寻找其他方法。 再尝试着卸载GT-suite v2016&#xff0c…...

小红书商业笔记与普通笔记区别是什么?小红书笔记有哪几种

主攻单一平台&#xff0c;如何迅速打造爆文。针对软文发布类别的选择&#xff0c;小红书商业笔记与普通笔记区别究竟是什么&#xff0c;今天为大家带来的详细分析&#xff0c;告诉你该如何用最少的成本&#xff0c;做出“爆文”。1、小红书的笔记类型我们都知道&#xff0c;小红…...

DataWhale-统计学习方法打卡Task01

学习教材《统计学习方法&#xff08;第二版&#xff09;》李航 统计学习方法&#xff08;第2版&#xff09; by...李航 (z-lib.org).pdf https://www.aliyundrive.com/s/maJZ6M9hrTe 点击链接保存&#xff0c;或者复制本段内容&#xff0c;打开「阿里云盘」APP &#xff0c;无…...

Java面试——Spring 事务

目录 1.什么是Spring 事务 2.Spring 事务的开启方式 3.Spring事务的实现方式/原理 4.事务传播机制 5.事务隔离级别 6.事务失效的原因 1.什么是Spring 事务 事务在逻辑上是一组操作&#xff0c;要么执行&#xff0c;要不都不执行。 如下&#xff1a; Begin; insert into…...

Python语言零基础入门教程(十九)

Python 异常处理 python提供了两个非常重要的功能来处理python程序在运行中出现的异常和错误。你可以使用该功能来调试python程序。 1、异常处理 2、断言(Assertions) python标准异常 什么是异常&#xff1f; 异常即是一个事件&#xff0c;该事件会在程序执行过程中发生&…...

重生之我是赏金猎人-SRC漏洞挖掘(一)-某SRC测试系统无脑Getshell

0x01 前言 https://github.com/J0o1ey/BountyHunterInChina 欢迎大佬们点个star 0x02 资产收集到脆弱系统 在某src挖掘过程中&#xff0c;本人通过ssl证书对域名资产进行了收集&#xff0c;通过计算域名对应ip段的权重 整理出其C段资产&#xff0c;进行了批量目录扫描 查看…...

Sciter 结合 PReact 实现组件公共逻辑抽离

Sciter 结合 PReact 实现组件公共逻辑抽离 下面例子是获取鼠标移动位置,将这部分逻辑进行抽离 一、使用高阶组件抽离公共逻辑 import {Component } from ./preact.js; export const HOCFactory = (Component) => {class HOC...

OpenTracing协议规范链接

一、官网链接 OpenTracing specificationhttps://opentracing.io/specification/不过目前OpenTracing项目已归档&#xff0c;不再维护。需要参考OpenTelemetry官网链接 Migrating from OpenTracing | OpenTelemetryBackward compatibility with OpenTracing has been a prior…...

金三银四面试必看,自动化测试如何解决日志问题

前言 前几天在员群里&#xff0c;有同学问了一个自动化测试实践中遇到的问题&#xff1a; 持续集成的自动化用例很多&#xff0c;测试环境日志level为debug&#xff0c;日志量大概40G/每天&#xff0c;定位问题时日志查询很慢&#xff0c;该怎么解决&#xff1f; 这个问题可…...

微信怎么开小店?【企业商家微信开店】

企业商家入局微信做营销已经是经营规划中必须做的一件事了&#xff0c;对于企业商家来说&#xff0c;最简单直接的方式就是开一个微信小店&#xff0c;然后通过自己宣传推广来在微信小店中成商品。那么企业商家在微信怎么开小店呢&#xff1f;下面内容分享给想在微信开店的企业…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...