当前位置: 首页 > 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;下面内容分享给想在微信开店的企业…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

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

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