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

算法系列--递归,回溯,剪枝的综合应用(2)

💕"对相爱的人来说,对方的心意,才是最好的房子。"💕
作者:Lvzi
文章主要内容:算法系列–递归,回溯,剪枝的综合应用(2)
在这里插入图片描述

大家好,今天为大家带来的是算法系列--递归,回溯,剪枝的综合应用(2)

一.括号⽣成

题目链接

括号生成

题目描述

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且有效的括号组合。

示例:

  • 输入:n = 3
    输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

  • 输入:n = 1
    输出:[“()”]

提示:

  • 1 <= n <= 8

分析:
在这里插入图片描述

代码:

class Solution {List<String> ret;// 返回值StringBuffer path;// 记录搜索路径int maxLevel, lcnt, rcnt;// max表示最大层数  lcnt表示左括号的数量  rcnt表示右括号的数量public List<String> generateParenthesis(int n) {ret = new ArrayList<>();path = new StringBuffer();if (n == 0) return ret;maxLevel = 2 * n;dfs(1, lcnt, rcnt,n);return ret;}private void dfs(int level, int lcnt, int rcnt,int n) {// 递归出口if(level > maxLevel) {ret.add(path.toString());return;}if(lcnt < n) {path.append("(");dfs(level + 1,lcnt+1, rcnt,n);path.deleteCharAt(path.length() - 1);// 回溯}if(rcnt < n && lcnt > rcnt) {path.append(")");dfs(level + 1, lcnt, rcnt+1,n);path.deleteCharAt(path.length() - 1);// 回溯}}
}

二.目标和

题目链接

目标和

题目描述

给你一个非负整数数组 nums 和一个整数 target

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ,然后串联起所有整数,可以构造一个表达式:

例如,nums = [2, 1] ,可以在 2 之前添加 ‘+’ ,在 1 之前添加 ‘-’ ,然后串联起来得到表达式 "+2-1"

返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

示例:

  • 输入:nums = [1,1,1,1,1], target = 3
    输出:5
    解释:一共有 5 种方法让最终目标和为 3
    -1 + 1 + 1 + 1 + 1 = 3
    +1 - 1 + 1 + 1 + 1 = 3
    +1 + 1 - 1 + 1 + 1 = 3
    +1 + 1 + 1 - 1 + 1 = 3
    +1 + 1 + 1 + 1 - 1 = 3

  • 输入:nums = [1], target = 1
    输出:1

提示:

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

分析:

思路同子集相同,子集中我们的决策策略是选不选当前的数,本题采用+当前数/-当前数

在这里插入图片描述

代码:

class Solution {int path, ret, target;public int findTargetSumWays(int[] nums, int _target) {target = _target;dfs(nums,0);return ret;}private void dfs(int[] nums, int pos) {if(pos == nums.length) {if(path == target)  ret += 1;return;}// +path += nums[pos];dfs(nums,pos + 1);path -= nums[pos];//回溯// -path -= nums[pos];dfs(nums,pos + 1);path += nums[pos];// 回溯}
}

本题的最优解法其实是动态规划,具体可见我的这篇文章
算法系列–动态规划–背包问题(2)–01背包拓展题目

(有限制条件下的组合问题,且一个数只能选择一次–01背包问题)


3.组合总和

题目链接

组合总和

题目描述

给你一个无重复元素的整数数组 candidates 和一个目标整数 target,找出 candidates 中可以使数字和为目标数 target 的所有不同组合,并以列表形式返回。你可以按任意顺序返回这些组合。

candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

示例:

  • 输入:candidates = [2,3,6,7], target = 7
    输出:[[2,2,3],[7]]
    解释:
    2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
    7 也是一个候选, 7 = 7 。
    仅有这两种组合。

  • 输入: candidates = [2,3,5], target = 8
    输出: [[2,2,2,2],[2,3,3],[3,5]]

  • 输入: candidates = [2], target = 1
    输出: []

提示:

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素互不相同
  • 1 <= target <= 40

分析:
在这里插入图片描述

(如果本题是要求组合总和的最多组合数就是一个完全背包问题)

代码:

class Solution {List<List<Integer>> ret;List<Integer> path;// 保存搜索路径int sum, target;// sum记录搜索路径上的和public List<List<Integer>> combinationSum(int[] nums, int _target) {ret = new ArrayList<>();path = new ArrayList<>();target = _target;dfs(nums,0);return ret;}private void dfs(int[] nums, int pos) {if(sum >= target) {// 递归出口if(sum == target) {ret.add(new ArrayList<>(path));}return;}for(int i = pos; i < nums.length; i++) {path.add(nums[i]); sum += nums[i];dfs(nums,i);// 递归path.remove(path.size() - 1); sum -= nums[i];// 回溯}}
}

4.字⺟⼤⼩写全排列

题目链接

字⺟⼤⼩写全排列

题目描述

784. 字母大小写全排列

给定一个字符串 s,通过将字符串 s 中的每个字母转变大小写,我们可以获得一个新的字符串。

返回所有可能得到的字符串集合。以任意顺序返回输出。

示例:

  • 输入:s = “a1b2”
    输出:[“a1b2”, “a1B2”, “A1b2”, “A1B2”]

  • 输入: s = “3z4”
    输出: [“3z4”,“3Z4”]

提示:

  • 1 <= s.length <= 12
  • s 由小写英文字母、大写英文字母和数字组成

解题思路

这道题可以使用回溯算法来解决。我们可以逐个遍历字符串中的每个字符,然后对于每个字符有两种选择:保持原大小写或者转换大小写。通过递归实现所有可能的组合。

代码实现(Java)

class Solution {List<String> ret;StringBuffer path;public List<String> letterCasePermutation(String s) {ret = new ArrayList<>();path = new StringBuffer();dfs(s,0);return ret;}private void dfs(String s, int pos) {if(pos == s.length()) {ret.add(path.toString());return;}// 不改变char ch = s.charAt(pos);path.append(ch);dfs(s, pos + 1);path.deleteCharAt(path.length() - 1);// 改变(非数字字符)if(ch < '0' || ch > '9') {char tmp = change(ch);path.append(tmp);dfs(s, pos + 1);path.deleteCharAt(path.length() - 1);}}private char change(char ch) {if(ch >= 'a' && ch <= 'z') return ch -= 32;else return ch += 32;}
}

5.优美的排列

题目链接

优美的排列

题目描述

526. 优美的排列

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm(下标从 1 开始),只要满足下述条件之一,该数组就是一个优美的排列:

  1. perm[i] 能够被 i 整除
  2. i 能够被 perm[i] 整除

给你一个整数 n ,返回可以构造的优美排列的数量。

示例:

输入:n = 2

输出:2

解释:

  • 第 1 个优美的排列是 [1,2]:
    • perm[1] = 1 能被 i = 1 整除
    • perm[2] = 2 能被 i = 2 整除
  • 第 2 个优美的排列是 [2,1]:
    • perm[1] = 2 能被 i = 1 整除
    • i = 2 能被 perm[2] = 1 整除

解题思路

这道题可以使用回溯算法来解决。我们可以尝试将数字填充到数组的每个位置上,同时检查当前位置是否满足条件。如果满足条件,继续递归处理下一个位置;否则,回溯到上一个位置重新尝试其他数字。

  • check[i]:用于标记数字是否被使用过
  • ret:返回值

代码实现(Java)

class Solution {int ret;// 返回值boolean[] check;// 用于标记已经使用过的数字public int countArrangement(int n) {check = new boolean[n + 1];dfs(1,n);return ret;}private void dfs(int pos, int n) {// pos是下标if(pos == n + 1) {// 递归出口ret += 1;return;}for(int i = 1; i <= n; i++) {if(check[i] == false && (pos % i == 0 || i % pos == 0)) {check[i] = true;// 将使用过的数字标记dfs(pos + 1, n);// 递归下一个位置check[i] = false;// 回溯}}}
}

在这段代码中:

  • pos 表示当前递归到的位置,也就是在填充数组时当前正在考虑的位置。
  • i 则表示尝试填充到当前位置 pos 上的数字。

具体来说:

  • pos 从1开始,代表数组中的位置,递归函数会尝试将数字填充到这些位置上。
  • i 从1到n,代表可以填充到当前位置的数字,即数组中的元素。

6. 组合

题目链接

组合

题目描述

给定两个整数 nk,返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按任何顺序返回答案。

示例 1:

输入:n = 4, k = 2
输出:

[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2:

输入:n = 1, k = 1
输出:[[1]]

提示:

  • 1 <= n <= 20
  • 1 <= k <= n

分析:
在这里插入图片描述

代码:

class Solution {List<List<Integer>> ret;List<Integer> path;int k, n;public List<List<Integer>> combine(int nn, int kk) {n = nn; k = kk;ret = new ArrayList<>();path = new ArrayList<>();dfs(1);return ret;}private void dfs(int start) {if(path.size() == k) {ret.add(new ArrayList<>(path));return;}for(int i = start; i <= n; i++) {path.add(i);// 添加当前数字dfs(i + 1);// 递归下一个数字path.remove(path.size() - 1);// 回溯}}
}

总结:

  • 对于递归回溯这样的问题,一定要把决策树画的详细,要明确每一步的目的是什么,是根据什么进行递归的

对于这种递归回溯剪枝综合应用的题目来说,其分析思路是比较固定的:

  1. 画出详细的决策树(越详细越好,把所有的情况都写出来)
  2. 分析每一个子问题都是在干啥
  3. 设计全局变量和dfs(其实dfs是这种问题最难的一步,dfs的设计本质上是一个递归的问题),dfs的设计包括三个方面:函数头,函数体,递归出口
  4. 考虑回溯和剪枝

相关文章:

算法系列--递归,回溯,剪枝的综合应用(2)

&#x1f495;"对相爱的人来说&#xff0c;对方的心意&#xff0c;才是最好的房子。"&#x1f495; 作者&#xff1a;Lvzi 文章主要内容&#xff1a;算法系列–递归,回溯,剪枝的综合应用(2) 大家好,今天为大家带来的是算法系列--递归,回溯,剪枝的综合应用(2) 一.括号…...

Docker搭建LNMP环境实战(09):安装mariadb

1、编写mariadb部署配置文件 在文件夹&#xff1a;/mnt/hgfs/dockers/test_site/compose下创建文件&#xff1a;test_site_mariadb.yml&#xff0c;内容如下&#xff1a; version: "3.5" services:test_site_mariadb:container_name: test_site_mariadbimage: mari…...

基于Python的微博舆论分析,微博评论情感分析可视化系统,附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

Flutter iOS上架指南

本文探讨了使用Flutter开发的iOS应用能否上架&#xff0c;以及上架的具体流程。苹果提供了App Store作为正式上架渠道&#xff0c;同时也有TestFlight供开发者进行内测。合规并通过审核后&#xff0c;Flutter应用可以顺利上架。但上架过程可能存在一些挑战&#xff0c;因此可能…...

实操:driver.js 实现产品导览、亮点、上下文帮助

官网 https://driverjs.com/ 依赖 <script src"https://cdn.jsdelivr.net/npm/driver.js1.0.1/dist/driver.js.iife.js"></script> <link rel"stylesheet" href"https://cdn.jsdelivr.net/npm/driver.js1.0.1/dist/driver.css"/…...

【JavaWeb】Day29.SpringBootWeb请求响应——请求(二)

请求响应 4.数组集合参数 数组集合参数的使用场景&#xff1a;在HTML的表单中&#xff0c;有一个表单项是支持多选的(复选框)&#xff0c;可以提交选择的多个值。 4.1 数组 数组参数&#xff1a;请求参数名与形参数组名称相同且请求参数为多个&#xff0c;定义数组类型形参即…...

asf是什么格式的文件?用手机怎么打开?

由于手机操作系统和硬件的限制&#xff0c;大部分手机并不直接支持asf文件的播放。因此&#xff0c;如果你想在手机上打开asf文件&#xff0c;你可能需要先将文件转换为手机支持的格式&#xff0c;如MP4。可以通过使用一些视频转换软件来实现&#xff0c;比如野葱视频转换器。 …...

picGo图床搭建gitee和smms(建议使用)

picGoGitee 这个需要下载gitee插件, 因为官方频繁的检索文件类型, 有时候也会失效 如果没有特殊要求平时存个学习的要看图中文字的重要的图片建议就是smms, 免费也够用! 图片存本地不方便, 各种APP中来回传还会失帧损失画质, 所以你值得往下看 picGosmms 建议使用这个, sm…...

LeetCode | 数组 | 二分查找 | 35.搜索插入位置【C++】

题目链接 题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums [1,3,5,6], target 5 输出…...

Linux 给网卡配置ip

ip addr | grep eth9 ifconfig eth9 10.0.0.2 netmask 255.255.255.0 up...

【C语言】翻译环境与运行环境

一、前言 在我们学习C语言的时候&#xff0c;第一个接触的程序就是&#xff1a;在屏幕上打印” hello word! “&#xff0c;可当时的我们却未去深入的理解与感悟&#xff0c;一个程序代码是如何运行的&#xff1b;而这一期的博客&#xff0c;则是带着我们&#xff0c;通过C代码…...

ubuntu20.04执行sudo apt-get update失败的解决方法

参考&#xff1a;执行sudo apt-get update失败的解决方案 1、换源型错误 &#xff08;1&#xff09;编辑/etc/apt/sources.list文件 在命令行中输入&#xff1a; sudo vim /etc/apt/sources.list 或者 sudo gedit /etc/apt/sources.list 推荐使用后者 &#xff08;2&#xf…...

接口调用成功后端却一直返回404

vuespringboot 我在vue.config.js中配置了向后端的反向代理 然后使用了axios向后端发送post请求 可以看到可以接收到前端传来的值 但是前端控制台却报了 “xhr.js:245POST http://localhost:7777/api/login 404 (Not Found)” 最后询问我那智慧的堂哥... ... 解决办法是把C…...

【Vmware】 debian 12 安装教程

1.前提说明 VMware 17.5.1 (自行安装)&#xff0c;参考Debian 12maven 3.8.7git 2.39.2jdk 1.8 / 11 / 17 1.1.Debian 下载 访问(https://www.debian.org/download) 下载 Debian 这是 Debian 12&#xff0c;代号为 bookworm&#xff0c;网络安装&#xff0c;用于 64 位 PC&a…...

YooAssets 使用相关

## 使用 YooAssets 动态加载原生文件时候 > 原生文件&#xff1a;txt&#xff1b;json&#xff1b;等需要直接保存文件内string字符的文件 需要将打包方式设置成为&#xff0c;PackRawFile 并且加载时候使用 API &#xff1a; YooAssets.LoadRawFileSync()YooAssets.LoadRa…...

精准扶贫管理系统|基于Springboot的精准扶贫管理系统设计与实现(源码+数据库+文档)

精准扶贫管理系统目录 目录 基于Springboot的精准扶贫管理系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员模块的实现 &#xff08;1&#xff09;用户信息管理 &#xff08;2&#xff09;贫困户信息管理 &#xff08;3&#xff09;新闻类型管理 &a…...

Flutter与iOS和Android原生页面交互

一、Flutter 与原生页面交互的重要性和应用场景 Flutter 是一个由 Google 开发的开源框架&#xff0c;用于创建跨平台的移动、Web 和桌面应用程序。Flutter 允许开发者使用一套代码库为 Android 和 iOS 等平台构建美观、高性能的应用程序。然而&#xff0c;尽管 Flutter 提供了…...

Chrome安装Vue插件vue-devtools

直接通过网站&#xff1a; Home | Vue Devtools (vuejs.org) chrome扩展商城中搜索&#xff1a;Vue.js devtools 参考下面edge扩展商城的图&#xff0c;两者流程相近...

内存和网卡压力测试

1.内存压力测试 1.1测试目的 内存压力测试的目的是评估开发板中的内存子系统性能和稳定性&#xff0c;以确保它能够满足特定的应用需求。开发板通常用于嵌入式系统、物联网设备、嵌入式智能家居等场景&#xff0c;这些场景对内存的要求通常比较高。 其内存压力测试的主要目的…...

法律行业案例法模型出现,OPenAI公布与法律AI公司Harvey合作案例

Harvey与OpenAl合作&#xff0c;为法律专业人士构建了一个定制训练的案例法模型。该模型是具有复杂推理广泛领域知识以及超越单一模型调用能力的任务的AI系统&#xff0c;如起草法律文件、回答复杂诉讼场景问题以及识别数百份合同之间的重大差异。 Harvey公司由具有反垄断和证…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

Axure 下拉框联动

实现选省、选完省之后选对应省份下的市区...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

C# winform教程(二)----checkbox

一、作用 提供一个用户选择或者不选的状态&#xff0c;这是一个可以多选的控件。 二、属性 其实功能大差不差&#xff0c;除了特殊的几个外&#xff0c;与button基本相同&#xff0c;所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...