首页 > 编程语言 >代码随想录算法训练营第二十四天 | 回溯算法理论基础,77. 组合

代码随想录算法训练营第二十四天 | 回溯算法理论基础,77. 组合

时间:2024-01-05 21:58:17浏览次数:38  
标签:递归 随想录 77 start 算法 回溯 单次

一、回溯算法理论基础

学习:

1. 基本概念
回溯法是一种搜索方式

回溯的本质是穷举,是递归的副产品,即回溯算法就是递归算法

回溯解决的问题都能理解成树形结构,一般是在集合中递归查找子集。集合的大小构成树的宽度(n叉树),递归的深度构成了树的深度

2. 回溯解决的问题

(1)组合问题:N个数里面按一定规则找出k个数的集合

(2)切割问题:一个字符串按一定规则有几种切割方式

(3)子集问题:一个N个数的集合里有多少符合条件的子集

(4)排列问题:N个数按一定规则全排列,有几种排列方式

(5)棋盘问题:N皇后,解数独等等

3. 构建回溯算法模板(可比对递归)

  • 函数返回值以及参数
  • 终止条件
  • 单次循环内容

二、77. 组合

题目链接:

LeetCode 77. 组合

学习前:

思路:

  • 函数返回值以及参数:void fun(int n, int k, int start),其中start是for循环开始的数值
  • 终止条件:当list的长度与k相等,则将其加入结果集res中,注意是深拷贝
  • 单次遍历内容:从start到n依次添加值到list中,然后递归调用fun(n,k,start+1)

学习后:

进一步优化。对于单次遍历内容,for循环里面的循环判断条件从i<=n优化为i<=(n-k)+1,即当剩余的数字已经不足以满足集合的长度时,无需再遍历

三、学习总结

  1. 时间:1.5h
  2. 初步了解了回溯,以及最简单的回溯算法和剪枝

标签:递归,随想录,77,start,算法,回溯,单次
From: https://www.cnblogs.com/amulet/p/17948165

相关文章

  • 经典算法之天数问题
    这题算是非常经典的题目了。无非就是判断闰年然后计算天数而已。用两个month数组记录月份天数一三五七八十腊是31天,二月份非闰年28天,闰年29天,其余都是30天就好了。#include<stdio.h>intjudge(intyear){if(year%400==0||year%100!=0&&year%4==0......
  • 代码随想录 day10 栈模拟队列 队列模拟栈
    栈模拟队列大概了解一下思路自己就可以很快写出来了我们需要第二个辅助栈帮助我们把stackIn的顺序颠倒,这样FILO的栈颠倒后pop的顺序就和FIFO的队列顺序一致了大概就是这张图队列模拟栈题目要求使用两个队列模拟栈其实可以只需要一个队列就可以模拟栈的出栈顺序是最后......
  • C语言逆波兰式算法
    1#include<stdio.h>23//数字模式识别4#defineIS_NUM(c)(((c)>='0')&&((c)<='9')||((c)=='.'))5//符号字符识别6#defineIS_OPERATOR(c)(((c)=='+')||((c)=='-')||((c)==&......
  • 2024年小红书最新x-s-common签名算法分析以及点赞api接口测试nodejs(2024-01-05)
      2024年小红书又更新了x-s-common算法,现在的版本是:3.6.8。这个签名算法现在是越来越重要了,许多接口都要用到。比如:评论,点赞等接口,没有这个算法采集不到数据。  一、chrome逆向x-s-common算法  1、x-s-common  打开chrome,按f12,打开开发者模式,随便找一接口,全局......
  • 经典算法之图形问题
    图形问题的万金解决方法就是创建一个二维数组,然后将填数组,最后打印数组就行了。其本质还是找出图形的规律。首先来找规律,先从外形上来找。奇数高,看图形,是上下左右对称的。所以只找上半区的规律。然后首行比其他行少两个字符也就是多两个空格,最外层都是A,数组可以提前都赋值。只......
  • 排序算法
    冒泡排序思想:1、一个无序的数组,n个元素,一共需要排序n-1轮2、在每一轮中,从数组第0位开始,比较相邻两个元素,如果与需求逆序,就交换这两个元素,在每一轮中,可以将当前最大(最小)的元素交换到最后,3、直到执行完n-1轮,没有需要比较的元素为止。代码实现:publicstaticvoidbubSort(in......
  • 生物识别应用锁控二合一和三合一芯片的算法描述和特点
    主控集成电容触控按键(二合一),外接指纹模组方案特点•主控:采用集成TouchKey的芯片ACM32FP0•算法:采用金融级安全芯片ACH512/高性能算法芯片ACM32FP4•非接:采用A32NQ32C3读卡芯片•支持指纹、按键、钥匙、非接、蓝牙等多种开锁方式•指纹、密码安全存储、敏感信息不外泄•提供......
  • 在Python中,有几个库可以帮助我们自动寻找最适合的机器学习模型和参数。这里有两个主要
    在Python中,有几个库可以帮助我们自动寻找最适合的机器学习模型和参数。这里有两个主要的库:1.**lazypredict**¹:这个库可以快速地比较多种机器学习算法的性能,从而帮助我们选择最佳的算法。它可以在循环中迭代多个模型,这通常需要一些时间,但是使用lazypredict可以克服这个限制。下......
  • 【教3妹学编程-算法题】经营摩天轮的最大利润
    3妹:“打个中国结,再系个红腰带,愿善良的人们天天好运来,你勤劳生活美,你健康春常在,你一生的忙碌为了笑逐颜开。”2哥 :3妹,元旦快乐啊。3妹:2哥元旦快乐~。2哥:祝新的一年,3妹技术突飞猛进,工资涨涨涨。3妹:祝新的一年,2哥能够找到女朋友,哈哈哈......
  • Landsat 7地表温度计算:单窗算法的ENVI、ERDAS实现
    本文介绍基于ENVI与ERDAS软件,对Landsat7遥感影像数据加以单窗算法的地表温度(LST)反演操作。(基于ENVI与ERDAS的Landsat7ETM+单窗算法地表温度(LST)反演)1原理部分与前期操作准备首先说一个批量计算LST的方法——基于GEE的Landsat地表温度反演可以看谷歌地球引擎GEE批量计算Land......