【三十五】【算法分析与设计】综合练习(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的时间轴,让图片动起来~ 如下图,一副冬日雪景图,想给画…...
基于Java+SpringBoot+Mybaties+layui+Vue+elememt 实习管理系统 的设计与实现
一.项目介绍 前台功能:用户进入系统可以实现首页,系统公告,个人中心,后台管理等功能进行操作 后台由管理员,实习单位,教师和学生,主要功能包括首页,个人中心,班级管理&am…...
非关系型数据库——Redis基本操作
目录 一、Redis数据库常用命令 1.Set——存放数据 2.Get——获取数据 3.Keys——获取符合条件的键值 4.Exists——判断键值是否存在 5.Del——删除指定键值 6.Type——获取键值对应的类型 7.Rename——对已有键值重命名(覆盖) 8.Renamenx——对…...
golang语言和JAVA对比
引言: 在当今的软件开发领域,有许多编程语言供开发人员选择。其中,Golang和Java是两种备受开发者青睐的语言。本文将探讨Golang和Java之间的比较和对比,分析它们在语言特性、性能、平台支持、社区和生态系统、开发效率和可维护性等方面的异同。 一、语言特性和性能 Golang…...
隐私计算实训营学习九:隐语多方安全计算在安全核对的行业实践
文章目录 一、业务背景:安全核对产生的土壤二、产品方案:从试点到规模化的路三、技术共建:与隐语的共同成长 一、业务背景:安全核对产生的土壤 业务背景:很多粗放使用数据的方式被新出台的法律法规所规范,…...
C#实现只保存2天的日志文件
文章目录 业务需求代码运行效果 欢迎讨论! 业务需求 在生产环境中,控制台窗口不便展示出来。 为了在生产环境中,完整记录控制台应用的输出,选择将其输出到文件中。 但是,存储所有输出的话会占用很多空间,…...
C++ 类和对象(中篇)
类的6个默认成员函数 如果一个类中什么成员都没有,简称为空类。空类中什么都没有吗?并不是的,任何一个类在我们不写的情 况下,都会自动生成下面6个默认成员函数。 构造函数: 定义:构造函数是一个特殊的成员…...
可视化场景(9):智慧看板,可能是最直观的数据展示
10年经验的大数据可视化和数字孪生老司机,该领域的专家,是您可信赖的技术合伙人,分享该领域的项目和作品,欢迎互动交流。 hello,我是贝格前端工场,本期分享可视化大屏在安全生产与设备运维场景的应用&#…...
加密算法(二)
1、SHA-256加密算法: package com.arithmetic.encryption; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; //使用java.security.MessageDigest类来进行SHA-256摘要的计算。 //通过getInstance("SHA-256")方法获取…...
大创项目推荐 深度学习 YOLO 实现车牌识别算法
文章目录 0 前言1 课题介绍2 算法简介2.1网络架构 3 数据准备4 模型训练5 实现效果5.1 图片识别效果5.2视频识别效果 6 部分关键代码7 最后 0 前言 🔥 优质竞赛项目系列,今天要分享的是 🚩 基于yolov5的深度学习车牌识别系统实现 该项目较…...
IP知识详解
IP基本认识 IP 在 TCP/IP 参考模型中处于第三层,也就是网络层。 网络层的主要作用是:实现主机与主机之间的通信,也叫点对点(end to end)通信。 网络层与数据链路层有什么关系呢? IP 的作用是主机之间通信…...
组织建设求是网/windows优化软件排行
有话先说:我是一只菜鸟,一只都是,从前是现在也是。 CSS中的会计元素与行内元素 块级元素特性:占据一整行,总是重起一行并且后面的元素也必须另起一行显示。内联元素特性:和其他内联元素显示在同一行。 可以…...
影视网站如何做seo/seo站长工具推广平台
策略路由PBR分为: 本地策略路由:对本设备发送的报文实现策略路由,比如本机下发的ICMP、BGP等协议报文。 当用户需要实现不同源地址的报文或者不同长度的报文通过不同的方式进行发送时,可以配置本地策略路由。 常用Policy-Ba…...
国外的贸易网站/独立站建站平台
C static、const和static const 以及它们的初始化 const定义的常量在超出其作用域之后其空间会被释放,而static定义的静态常量在函数执行后不会释放其存储空间。 static表示的是静态的。类的静态成员函数、静态成员变量是和类相关的,而不是和类的具体对象…...
做网站电话销售/百度信息流
ldd 作用:用来查看程式运行所需的共享库,常用来解决程式因缺少某个库文件而不能运行的一些问题。 示例:查看test程序运行所依赖的库: /opt/app/todeav1/test$ldd test libstdc.so.6 > /usr/lib64/libstdc.so.6 (0x00000039a7e00000) libm.so.6 >…...
北京app外包/seo建站是什么
在python中用到pow函数,一般都是求数值的三次方, pow(x,y)----->其意思是数字x的y次方 例如:pow(5,3)------>表示5的三次方,其结果为:555...
wordpress 判断管理员/啥是网络推广
在提到批量归一化的面试问题时候,一般会以以下几种形式提问: 为什么要引入BN?BN解决了什么问题?BN的公式是怎样的?BN公式中,有哪些参数是可学的?BN中,均值和方差的尺寸shape是什么样…...