【三十五】【算法分析与设计】综合练习(2),22。 括号生成,77。 组合,494。 目标和,模拟树递归,临时变量自动维护树定义,递归回溯,非树结构模拟树
22. 括号生成
数字
n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。示例 1:
输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1 输出:["()"]
提示:
1 <= n <= 8
【三十五】【算法分析与设计】综合练习(2),22。 括号生成,77。 组合,494。 目标和,模拟树递归,临时变量自动维护树定义,递归回溯,非树结构模拟树
定义dfs
递归函数,将叶子节点填充到ret
中。
定义 ret 记录结果。
定义path
表示树节点。
定义left,right
表示当前树节点的左右括号数量。用来正确进入到下一个子树中。
任何情况下 left>=right
必须满足才是有效的形式。
如果需要添加左括号,left<=n,left+1<=n,left<n
。
如果需要添加右括号,left>=right,left>=right+1,left>right
。
以上是正确进入子树的规则。
递归函数dfs
内部逻辑,将path
树所有叶子节点填充到ret
,相当于将左子树叶子节点填充到ret
,右子树叶子节点填充到ret
。
if (left < n) {
path.push_back('(');
left++;
dfs();
path.pop_back();
left--;
}
这一整个代码表示左子树递归。因为是模拟树所以必须时时刻刻维护path,left,right
的定义。因为这些变量都与树的定义有关。
if (left > right) {
path.push_back(')');
right++;
dfs();
path.pop_back();
right--;
}
这一整个代码表示右子树递归。因为是模拟树所以必须时时刻刻维护path,left,right
的定义。因为这些变量都与树的定义有关。
递归函数的出口,当path.size() == 2 * n
,此时是叶子节点,将path
添加到ret
中。
class Solution {
public:int left, right;string path;vector<string> ret;int n;vector<string> generateParenthesis(int _n) {n = _n;dfs();return ret;}void dfs() {if (path.size() == 2 * n) {ret.push_back(path);return;}if (left < n) {path.push_back('(');left++;dfs();path.pop_back();left--;}if (left > right) {path.push_back(')');right++;dfs();path.pop_back();right--;}}
};
77. 组合
给定两个整数
n
和k
,返回范围[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
定义dfs
递归函数,将path
树叶子节点填充到ret
中。
思考模拟树需要定义的变量。
定义path
表示树的根节点。
定义pos
表示子树开始遍历的下标。
定义ret
记录结果。
小技巧,将n
和k
定义成全局变量,就不用每次都传入递归函数中。
递归函数的内部逻辑,将所有子树的叶子节点填充到 ret 中。
for (int i = pos; i <= n; i++) {
path.push_back(i);
int temp = pos;
pos = i + 1;
dfs();
path.pop_back();
pos = temp;
}
for 循环中的所有代码表示一个子树的递归,用for
循环变量所有的子树。
遍历下一个子树的时候,需要维护path
和pos
的定义。因为是模拟树所以必须时时刻刻维护path
,pos
的定义。因为这些变量都与树的定义有关。
递归出口,当path.size() == k
时,表示是叶子节点,此时将path
填充到ret
中。
class Solution {
public:vector<vector<int>> ret;vector<int> path;int pos = 1;int n, k;vector<vector<int>> combine(int _n, int _k) {n = _n;k = _k;dfs();return ret;}void dfs() {if (path.size() == k) {ret.push_back(path);return;}for (int i = pos; i <= n; i++) {path.push_back(i);int temp = pos;pos = i + 1;dfs();path.pop_back();pos = temp;}}
};
494. 目标和
给你一个非负整数数组
nums
和一个整数target
。向数组中的每个整数前添加
'+'
或'-'
,然后串联起所有整数,可以构造一个 表达式 :
例如,
nums = [2, 1]
,可以在2
之前添加'+'
,在1
之前添加'-'
,然后串联起来得到表达式"+2-1"
。返回可以通过上述方法构造的、运算结果等于
target
的不同 表达式 的数目。示例 1:
输入: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
示例 2:
输入:nums = [1], target = 1 输出:1
提示:
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
定义dfs
将树叶子节点符合要求的计数。
定义path
表示树根节点。
定义pos
表示nums
下一个应该遍历下标,也就是子树的可能性。
上面的定义模拟树。
定义ret
记录结果。
定义target
表示目标和,定义为全局变量。
递归函数dfs
内部逻辑,将左子树叶子节点符合要求的计数,将右子树叶子节点符合要求的计数。
递归左右子树的时候需要时时刻刻维护path
和pos
。
path += nums[pos];
pos++;
dfs(nums);
pos--;
path -= nums[pos];
递归左子树。因为是模拟树所以必须时时刻刻维护path
,pos
的定义。因为这些变量都与树的定义有关。
path -= nums[pos];
pos++;
dfs(nums);
pos--;
path += nums[pos];
递归右子树。因为是模拟树所以必须时时刻刻维护path
,pos
的定义。因为这些变量都与树的定义有关。
递归函数的出口,当pos == nums.size()
表示是叶子节点,同时path==target
表示是符合要求的情况,此时ret++
。
class Solution {
public:int ret;int path;int pos;int target;int findTargetSumWays(vector<int>& nums, int _target) {target=_target;dfs(nums);return ret;}void dfs(vector<int>& nums) {if (pos == nums.size()) {if (path == target)ret++;return;}path += nums[pos];pos++;dfs(nums);pos--;path -= nums[pos];path -= nums[pos];pos++;dfs(nums);pos--;path += nums[pos];}
};
利用临时变量的性质自动维护树的定义。
此时就不需要手动维护树的定义。
手动维护树的定义需要进行操作,此时临时变量空间仅仅是int
类型的,所以相对于手动维护,时间会快一点。
如果临时变量是vector
类型效率可能会减低,因为每次都需要开辟vector
的空间。此时用全局变量手动维护可能会更好一点。
int 类型可以不使用全局变量,利用临时变量自动维护,此时效率可能会变快。因为加减操作也是需要时间的。
class Solution {
public:int ret;int target;int findTargetSumWays(vector<int>& nums, int _target) {target = _target;dfs(nums, 0, 0);return ret;}void dfs(vector<int>& nums, int pos, int path) {if (pos == nums.size()) {if (path == target)ret++;return;}dfs(nums, pos + 1, path + nums[pos]);dfs(nums, pos + 1, path - nums[pos]);}
};
结尾
最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。
同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。
谢谢您的支持,期待与您在下一篇文章中再次相遇!
相关文章:

【三十五】【算法分析与设计】综合练习(2),22。 括号生成,77。 组合,494。 目标和,模拟树递归,临时变量自动维护树定义,递归回溯,非树结构模拟树
22. 括号生成 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n 3 输出:["((())࿰…...
QT智能指针
一.概述 Qt智能指针是一种能够在不需要手动管理内存的情况下,自动释放资源的指针。它们是C11的std::shared_ptr的一种扩展,可以用于管理Qt对象,尤其是那些不是QObject的对象。 使用智能指针可以避免内存泄露和悬垂指针等问题,同时…...
C++笔记之pkg-config详解,以及g++、gcc编译时使用pkg-config
C++笔记之pkg-config详解,以及g++、gcc编译时使用pkg-config —— 2024-04-05 code review 文章目录 C++笔记之pkg-config详解,以及g++、gcc编译时使用pkg-config1.pkg-config详解`pkg-config` 的基本用法在 `g++`/`gcc` 编译时使用 `pkg-config`注意事项2.示例C++,普通编译…...

[Apple Vision Pro]开源项目 Beautiful Things App Template
1. 技术框架概述: - Beautiful Things App Template是一个为visionOS设计的免费开源软件(FOSS),用于展示3D模型画廊。 2. 定位: - 该模板作为Beautiful Things网站的延伸,旨在为Apple Vision Pro用户…...
Qt Remote Objects (QtRO) 笔记
简介 Qt Remote Objects (QtRO) 是 Qt 的一个进程间通信模块。 术语 Source 是指提供服务或提供功能供其他程序使用的对象,是 RPC 中的被调用端。 Replica 是指 Source 对象的代理对象,用于 RPC 中的调用端,对 Replica 的调用请求将被转发…...

Unity类银河恶魔城学习记录12-6.5 p128.5 Create item by Craft源代码
此章节在原视频缺失,此过程为根据源代码推断而来,并非原视频步骤 Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释,可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩…...

UE4_如果快速做出毛玻璃效果_假景深
UE4_如果快速做出毛玻璃效果_假景深 2022-08-20 15:02 一个SpiralBlur-SceneTexture材质节点完成效果,启用半透明材质通过修改BlurAmount数值大小调整效果spiralBlur-SceneTexture custom节点,HLSL语言float3 CurColor 0;float2 BaseUV MaterialFloa…...

c# wpf LiveCharts 绑定 简单试验
1.概要 c# wpf LiveCharts 绑定 简单试验 2.代码 <Window x:Class"WpfApp3.Window2"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d"http://schem…...

【Kafka】Kafka安装、配置、使用
【Kafka】安装Kafka 1. 安装Kafka2. Kafka使用2.0 集群分发脚本xsync(重要)2.0.1 scp命令2.0.2 rsync远程同步工具2.0.3 写一个集群分发脚本xsync (Shell 脚本) 2.1 Zookeeper安装2.2 对Kafka进行分发2.2.1 执行同步脚本2.2.2 三台云主机配置Kafka环境变量 1. 安装Kafka Kafka…...

2024HW-->Wireshark攻击流量分析
在HW中,最离不开的,肯定是看监控了,那么就要去了解一些wireshark的基础用法以及攻击的流量!!!! 1.Wireshark的基本用法 比如人家面试官给你一段流量包,你要会用 1.分组详情 对于我…...

Lafida多目数据集实测
Lafida 数据集 paper:J. Imaging | Free Full-Text | LaFiDa—A Laserscanner Multi-Fisheye Camera Dataset 官网数据:https://www.ipf.kit.edu/english/projekt_cv_szenen.php 官网:KIT-IPF-Software and Datasets - LaFiDa 标定数据下载&…...
excel wps中编码格式转换
EXCEL报表:另存为CSV格式,转换成UTF-8编码 - 简书 (jianshu.com) 经验证管用...

【游戏分析】非游戏领空追字符串来源
通过NPC名称找NPC数组 扫描 NPC名字 ASIC型 发现全部都有后缀 那么采用 字节集的方式去扫描 也是扫不到 说明:不是ASIC型字符串 扫描 NPC名字 Unicode型 没有结果 那么转换成字节集去扫描 终于发现结果了 把结果挨个修改字符串 发现 其中两个是可以用的 22和23 …...
golang 数组和切片
区别 1.数组长度固定,切片长度可变 2.数组是深拷贝,切片是浅拷贝,切片是引用类型 扩容规则 不同版本不一样 https://www.jb51.net/article/280481.htm#_lab2_2_1 go1.18 1.如果期望容量大于当前容量的两倍就会使用期望容量; 2.如…...

物联网实战--入门篇之(九)安卓QT--开发框架
目录 一、QT简介 二、开发环境 三、编码风格 四、设计框架 五、总结 一、QT简介 QT是一款以C为基础的开发工具,已经包含了很多常用的库,除了基本的GUI以外,还有网络、数据库、多媒体、进程通信、串口、蓝牙等常用库,开发起来…...

【leetcode面试经典150题】16.接雨水(C++)
【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致&…...
互联网面经
腾讯视频 代码:反转链表,单例模式 RAII,哪里用到 Web服务器怎样处理请求 get\post流程 项目使用的还是http1.0吗;http2.0:二进制、首部压缩、主动推送;Https Epoll/select/poll ET/LT 进程地址空间。3…...
xss介绍及作用
XSS(Cross-Site Scripting)是一种常见的网络安全漏洞,它允许攻击者向网站注入恶意的客户端脚本代码,从而在用户的浏览器中执行这些代码。 XSS攻击的原理是攻击者将恶意脚本插入到网页中的用户输入数据中,当其他用户访…...

PostgreSQL入门到实战-第二弹
PostgreSQL入门到实战 PostgreSQL安装之Windows官网地址PostgreSQL概述Windows上安装PostgreSQL更新计划 PostgreSQL安装之Windows 官网地址 声明: 由于操作系统, 版本更新等原因, 文章所列内容不一定100%复现, 还要以官方信息为准 https://www.postgresql.org/PostgreSQL概…...

3-【PS让图片动起来】系列1-【导入素材】
【问题介绍】仅做图片,现在很难吸引用户视线,越来越多地图片需要动起来增添意境,比如春日樱花花瓣掉落、冬季雪花纷纷,今天来学学怎么用PS的时间轴,让图片动起来~ 如下图,一副冬日雪景图,想给画…...

手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
MySQL 主从同步异常处理
阅读原文:https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主,遇到的这个错误: Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一,通常表示ÿ…...

nnUNet V2修改网络——暴力替换网络为UNet++
更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...