网站点击快速排名,随县网站建设,陈木胜妻子,公众号做视频网站吗个人主页#xff1a;元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题 http://t.csdnimg.cn/yUl2I
【C】 http://t.csdnimg.cn/6AbpV
数据结构与算法 http://t.csdnimg.cn/hKh2l 前言#xff1a;这个专栏主要讲述递归递归、搜…个人主页元清加油_【C】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题 http://t.csdnimg.cn/yUl2I
【C】 http://t.csdnimg.cn/6AbpV
数据结构与算法 http://t.csdnimg.cn/hKh2l 前言这个专栏主要讲述递归递归、搜索与回溯算法所以下面题目主要也是这些算法做的
我讲述题目会把讲解部分分为3个部分 1、题目解析
2、算法原理思路讲解
3、代码实现 目标和
题目链接目标和
题目
给你一个非负整数数组 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 200 nums[i] 10000 sum(nums[i]) 1000-1000 target 1000 解法
题目解析
题目的意思非常简单给我们一个非负整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 或 - 然后串联起所有整数可以构造一个 表达式 。表达式的值要等于 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 算法原理思路讲解 对于每个数可以选择加上或减去它依次枚举每⼀个数字在每个数都被选择时检查得到的和是否等于⽬标值。如果等于则记录结果。 一、画出决策树 以 nums[ ] [1,2,3] 和 target 2 为例子 决策树就是我们后面设计函数的思路 二、设计代码 1全局变量 int sum;
int ret; sumtarget的值 ret记录符合target 值的次数 2设计递归函数 void dfs(vectorint nums, int pos, int path); 参数nums数组pos当前要处理的元素下标path当前状态和返回值无函数作⽤查找所有值为 target 的次数 递归流程 递归结束条件pos 与数组⻓度相等判断当前状态的 path 是否与⽬标值target相等若是计数ret加⼀ 选择当前元素进⾏加操作递归下⼀个位置并更新参数 path 选择当前元素进⾏减操作递归下⼀个位置并更新参数 path 以上思路讲解完毕大家可以自己做一下了 代码实现 时间复杂度O()其中 n 是数组 nums 的长度。回溯需要遍历所有不同的表达式共有 种不同的表达式每种表达式计算结果需要 O(1) 的时间因此总时间复杂度是 O()。 空间复杂度O(n)其中 n 是数组 nums 的长度。空间复杂度主要取决于递归调用的栈空间栈的深度不超过 n。 class Solution
{
public:int sum;int ret;void dfs(vectorint nums, int pos, int path){if (pos nums.size()){if (path sum){ret;}return;}dfs(nums, pos 1, path nums[pos]);dfs(nums, pos 1, path - nums[pos]);}int findTargetSumWays(vectorint nums, int target){sum target;dfs(nums, 0, 0);return ret;}
};
