【三十五】【算法分析与设计】综合练习(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

相关文章

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

pytorch自动求梯度autograd的实现

《pytorch自动求梯度autograd的实现》autograd是一个自动微分引擎,它可以自动计算张量的梯度,本文主要介绍了pytorch自动求梯度autograd的实现,具有一定的参考价值,感兴趣... autograd是pytorch构建神经网络的核心。在 PyTorch 中,结合以下代码例子,当你

Python如何自动生成环境依赖包requirements

《Python如何自动生成环境依赖包requirements》:本文主要介绍Python如何自动生成环境依赖包requirements问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录生成当前 python 环境 安装的所有依赖包1、命令2、常见问题只生成当前 项目 的所有依赖包1、

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL

Spring Boot项目中结合MyBatis实现MySQL的自动主从切换功能

《SpringBoot项目中结合MyBatis实现MySQL的自动主从切换功能》:本文主要介绍SpringBoot项目中结合MyBatis实现MySQL的自动主从切换功能,本文分步骤给大家介绍的... 目录原理解析1. mysql主从复制(Master-Slave Replication)2. 读写分离3.

C语言函数递归实际应用举例详解

《C语言函数递归实际应用举例详解》程序调用自身的编程技巧称为递归,递归做为一种算法在程序设计语言中广泛应用,:本文主要介绍C语言函数递归实际应用举例的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录前言一、递归的概念与思想二、递归的限制条件 三、递归的实际应用举例(一)求 n 的阶乘(二)顺序打印

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n