【三十五】【算法分析与设计】综合练习(2),22。 括号生成,77。 组合,494。 目标和,模拟树递归,临时变量自动维护树定义,递归回溯,非树结构模拟树

本文主要是介绍【三十五】【算法分析与设计】综合练习(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. 组合

给定两个整数 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

定义dfs递归函数,将path树叶子节点填充到ret中。

思考模拟树需要定义的变量。

定义path表示树的根节点。

定义pos表示子树开始遍历的下标。

定义ret记录结果。

小技巧,将nk定义成全局变量,就不用每次都传入递归函数中。

递归函数的内部逻辑,将所有子树的叶子节点填充到 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循环变量所有的子树。

遍历下一个子树的时候,需要维护pathpos的定义。因为是模拟树所以必须时时刻刻维护pathpos的定义。因为这些变量都与树的定义有关。

递归出口,当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内部逻辑,将左子树叶子节点符合要求的计数,将右子树叶子节点符合要求的计数。

递归左右子树的时候需要时时刻刻维护pathpos

path += nums[pos]; pos++; dfs(nums); pos--; path -= nums[pos];

递归左子树。因为是模拟树所以必须时时刻刻维护pathpos的定义。因为这些变量都与树的定义有关。

path -= nums[pos]; pos++; dfs(nums); pos--; path += nums[pos];

递归右子树。因为是模拟树所以必须时时刻刻维护pathpos的定义。因为这些变量都与树的定义有关。

递归函数的出口,当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。 目标和,模拟树递归,临时变量自动维护树定义,递归回溯,非树结构模拟树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/883147

相关文章

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

使用Jackson进行JSON生成与解析的新手指南

《使用Jackson进行JSON生成与解析的新手指南》这篇文章主要为大家详细介绍了如何使用Jackson进行JSON生成与解析处理,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 核心依赖2. 基础用法2.1 对象转 jsON(序列化)2.2 JSON 转对象(反序列化)3.

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

SpringBoot中封装Cors自动配置方式

《SpringBoot中封装Cors自动配置方式》:本文主要介绍SpringBoot中封装Cors自动配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot封装Cors自动配置背景实现步骤1. 创建 GlobalCorsProperties

在java中如何将inputStream对象转换为File对象(不生成本地文件)

《在java中如何将inputStream对象转换为File对象(不生成本地文件)》:本文主要介绍在java中如何将inputStream对象转换为File对象(不生成本地文件),具有很好的参考价... 目录需求说明问题解决总结需求说明在后端中通过POI生成Excel文件流,将输出流(outputStre

idea中创建新类时自动添加注释的实现

《idea中创建新类时自动添加注释的实现》在每次使用idea创建一个新类时,过了一段时间发现看不懂这个类是用来干嘛的,为了解决这个问题,我们可以设置在创建一个新类时自动添加注释,帮助我们理解这个类的用... 目录前言:详细操作:步骤一:点击上方的 文件(File),点击&nbmyHIgsp;设置(Setti

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Linux修改pip临时目录方法的详解

《Linux修改pip临时目录方法的详解》在Linux系统中,pip在安装Python包时会使用临时目录(TMPDIR),但默认的临时目录可能会受到存储空间不足或权限问题的影响,所以本文将详细介绍如何... 目录引言一、为什么要修改 pip 的临时目录?1. 解决存储空间不足的问题2. 解决权限问题3. 提

一文详解SQL Server如何跟踪自动统计信息更新

《一文详解SQLServer如何跟踪自动统计信息更新》SQLServer数据库中,我们都清楚统计信息对于优化器来说非常重要,所以本文就来和大家简单聊一聊SQLServer如何跟踪自动统计信息更新吧... SQL Server数据库中,我们都清楚统计信息对于优化器来说非常重要。一般情况下,我们会开启"自动更新