草庐IT

回溯理论基础及leetcode例题

Lee_ing 2023-05-08 原文

学习参考

回溯

与递归相辅相成;回溯是递归的副产品，只要有递归就会有回溯。
回溯函数也就是递归函数，指的都是一个函数。

回溯搜索法

纯暴力搜索
解决的问题

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式(与组合差别，排列有元素顺序)
棋盘问题：N皇后，解数独等等

理解

抽象的不易理解；抽象为图形结构--树形结构
N叉树【树的宽度：集合的大小（for处理）；深度：递归的深度（递归处理）】

模板

void backtracking(参数){
  if(终止条件){
    收集结果；
    return；
  }

  //单层搜索
   for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小)）{//集合元素集
      处理节点；
      backtracking(路径，选择列表);//递归函数；
      回溯操作； //（12，把2回溯，变13；没有回溯操作就会递归为123）
    }
  return；
}

递归里面嵌套for循环，for循环里又有递归

leetcode题目

组合

77.组合

for循环嵌套太多层了

树形结构

不能取前面的的：因为组合是无序的，会重复；
每个节点都是一个for循环

回溯三部曲

递归函数参数返回值
确定终止条件
单层递归逻辑

伪代码

全局变量：二维数组res【返回值】
         一维数组path【单个结果】
//确定返回值参数
void backtracking(n,k,start){//n集合大小；k需要的子集合大小；start每个取值的开始；
  //确定终止条件
  if(path.size == k){
    res.add(path);
    return;
  }
  //单层递归逻辑
  //对于1，234节点
  for(i=start,i<=n;i++){
    path.push(i);//1
    backtracking(n,k,i+1);//遍历剩下的集合234；
    path.pop();//回溯过程
  } 
}

实现
java版本

class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();

    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return res;
    }

    public void backtracking(int n,int k,int start){
        if(path.size() == k){
            res.add(new ArrayList<>(path));//容易犯错误
            return;
        }

        for(int i=start;i<=n;i++){//i<=n -(k-path.size()) + 1 会减少运行时间【剪枝操作】
            path.add(i);
            backtracking(n,k,i+1);
            path.remove(path.size()-1);
        }
        
    }
}

问题：参考
在链表path里面添加值，然后把path链表添加进res链表中，在做算法题的时候，平时使用res.add(path)，结果发现输出打印为空：

在链表path里面添加值，然后把path链表添加进res链表中，在做算法题的时候，平时使用res.add(path)，结果发现输出打印为空： res.add(new ArrayList＜＞(path))和res.add(path)的区别
共同点： 都是向res这个ArrayList中填加了一个名为path的链表
不同点： res.add(new ArrayList(path))：开辟一个独立地址，地址中存放的内容为path链表，后续path的变化不会影响到res
res.add(path)：将res尾部指向了path地址，后续path内容的变化会导致res的变化。

优化：剪枝
可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。


优化过程如下：

已经选择的元素个数：path.size();
所需需要的元素个数为: k - path.size();
列表中剩余元素（n-i） >= 所需需要的元素个数（k - path.size()）
在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1，开始遍历

例题leetcodepathstrongres算法与数据结构

有关回溯理论基础及leetcode例题的更多相关文章

  1. postman接口测试工具-基础使用教程 - 2

    1.postman介绍Postman一款非常流行的API调试工具。其实，开发人员用的更多。因为测试人员做接口测试会有更多选择，例如Jmeter、soapUI等。不过，对于开发过程中去调试接口，Postman确实足够的简单方便，而且功能强大。2.下载安装官网地址:https://www.postman.com/下载完成后双击安装吧，安装过程极其简单，无需任何操作3.使用教程这里以百度为例,工具使用简单，填写URL地址即可发送请求，在下方查看响应结果和响应状态码常用方法都有支持请求方法:getpostputdeleteGet、Post、Put与Delete的作用get：请求方法一般是用于数据查询，

  2. 软件测试基础 - 2

    Ⅰ软件测试基础一、软件测试基础理论1、软件测试的必要性所有的产品或者服务上线都需要测试2、测试的发展过程3、什么是软件测试找bug，发现缺陷4、测试的定义使用人工或自动的手段来运行或者测试某个系统的过程。目的在于检测它是否满足规定的需求。弄清预期结果和实际结果的差别。5、测试的目的以最小的人力、物力和时间找出软件中潜在的错误和缺陷6、测试的原则28原则：20%的主要功能要重点测（eg：支付宝的支付功能，其他功能都是次要的）80%的错误存在于20%的代码中7、测试标准8、测试的基本要求功能测试性能测试安全性测试兼容性测试易用性测试外观界面测试可靠性测试二、质量模型衡量一个优秀软件的维度①功能性功

  3. ES基础入门 - 2

    ES一、简介1、ElasticStackES技术栈：ElasticSearch：存数据+搜索；QL；Kibana：Web可视化平台，分析。LogStash：日志收集，Log4j:产生日志；log.info(xxx)。。。。使用场景：metrics：指标监控…2、基本概念Index（索引）动词：保存（插入）名词：类似MySQL数据库，给数据Type（类型）已废弃，以前类似MySQL的表现在用索引对数据分类Document（文档）真正要保存的一个JSON数据{name:"tcx"}二、入门实战{"name":"DESKTOP-1TSVGKG","cluster_name":"elasticsear

  4. Python 刷Leetcode题库，顺带学英语单词（31） - 2

    ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem

  5. 【网络】-- 网络基础 - 2

    （本文是网络的宏观的概念铺垫）目录计算机网络背景网络发展认识"协议"网络协议初识协议分层OSI七层模型TCP/IP五层(或四层)模型报头以太网碰撞路由器IP地址和MAC地址IP地址与MAC地址总结IP地址MAC地址计算机网络背景网络发展        是最开始先有的计算机，计算机后来因为多项技术的水平升高，逐渐的计算机变的小型化、高效化。后来因为计算机其本身的计算能力比较的快速：独立模式：计算机之间相互独立。    如：有三个人，每个人做的不同的事物，但是是需要协作的完成。    而这三个人所做的事是需要进行协作的，然而刚开始因为每一台计算机之间都是互相独立的。所以前面的人处理完了就需要将数据

  6. IDEA使用LeetCode插件 - 2

    前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit

  7. 【Elasticsearch基础】Elasticsearch索引、文档以及映射操作详解 - 2

    文章目录概念索引相关操作创建索引更新副本查看索引删除索引索引的打开与关闭收缩索引索引别名查询索引别名文档相关操作新建文档查询文档更新文档删除文档映射相关操作查询文档映射创建静态映射创建索引并添加映射概念es中有三个概念要清楚，分别为索引、映射和文档（不用死记硬背，大概有个印象就可以）索引可理解为MySQL数据库；映射可理解为MySQL的表结构；文档可理解为MySQL表中的每行数据静态映射和动态映射上面已经介绍了，映射可理解为MySQL的表结构，在MySQL中，向表中插入数据是需要先创建表结构的；但在es中不必这样，可以直接插入文档，es可以根据插入的文档（数据），动态的创建映射（表结构），这就

  8. c++基础-运算符 - 2

    目录1关系运算符2运算符优先级3关系表达式的书写代码实例：下面是面试中可能遇到的问题：1关系运算符C++中有6个关系运算符，用于比较两个值的大小关系，它们分别是：运算符描述==等于!=不等于小于>大于小于等于>=大于等于这些运算符返回一个布尔值，即true或false。例如，当x等于y时，x==y的结果为true，否则结果为false。2运算符优先级在C++中，关系运算符的优先级高于赋值运算符，但低于算术运算符。以下是关系运算符的优先级，从高到低排列：运算符描述>,,>=,关系运算符==,!=相等性运算符&&逻辑与`如果在表达式中有多个运算符，则按照优先级顺序依次进行运算。3关系表达式的书写在

  9. 计算机必读基础书籍 - 2

    一.计算机组成原理    这本书利用组合逻辑、同步时序逻辑电路设计的相关知识，从逻辑门开始逐步构建运算器、存储器、数据通路和控制器，最终集成为完整的CU原型系统，使读者从设计者的角度理解计算机部件构成及运行的基本原理，掌握软硬件协同的概念。    全书共9章，主要内容包括计算机系统概述、数据信息的表示、运算方法与运算器、存储系统、指令系统、中央处理器、指令流水线、总线系统、输入输出系统。1.计算机系统概述1.1计算机发展历程    计算机是一种能够按照事先存储的程序，自动、高速、准确地对相关信息进行处理的电子设备。1946年2月，世界上第一台电子数字计算机ENIAC(ElectronicNum

  10. 0基础学习软件测试有哪些建议 - 2

    其实现在基础的资料和视频到处都是，就是看你有没有认真的去找学习资源了，去哪里学习都是要看你个人靠谱不靠谱，再好的教程和老师，你自己学习不进去也是白搭在正式选择之前，大可以在各种学习网站里面找找学习资源先自己学习一下为什么选择学软件测试？同学们理由众多！大概分这几类：①不受开发语言、行业产品变化限制；②入门更简单，对零基础、女生都友好；③软件项目都需要测试人员，职业生涯稳；④学习周期短，但薪资并不低。要想“肩扛”一条线？需掌握三大技能：技能1：掌握测试流程，熟悉系统框架能提前与开发人员一起制定测试计划，通过测试左移，推动代码评审，代码审计，单元测试，自动化冒烟测试，来保证研发阶段的质量。技能2：

随机推荐