LeetCode刷题--- 目标和

2023-12-23 17:38:47

个人主页:元清加油_【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 <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • -1000 <= target <= 1000

解法

题目解析

  1. 题目的意思非常简单,给我们一个非负整数数组?nums?和一个整数?target?。
  2. 向数组中的每个整数前添加?'+'?或?'-'?,然后串联起所有整数,可以构造一个?表达式?。
  3. 表达式的值要等于 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;
  • sum(target的值)?
  • ret(记录符合target 值的次数)

(2)设计递归函数

void dfs(vector<int>& nums, int pos, int path);
  • 参数:nums(数组),pos(当前要处理的元素下标),path(当前状态和)
  • 返回值:无;
  • 函数作?:查找所有值为 target 的次数;
递归流程:
  1. 递归结束条件:pos?与数组?度相等,判断当前状态的 path?是否与?标值(target)相等,若是计数(ret)加?;
  2. 选择当前元素进?加操作,递归下?个位置,并更新参数 path;
  3. 选择当前元素进?减操作,递归下?个位置,并更新参数 path;

以上思路讲解完毕,大家可以自己做一下了


代码实现

时间复杂度:O(2^{n}),其中 n?是数组 nums 的长度。回溯需要遍历所有不同的表达式,共有 2^{n}?种不同的表达式,每种表达式计算结果需要 O(1) 的时间,因此总时间复杂度是 O(2^{n})。

空间复杂度:O(n),其中 n?是数组 nums 的长度。空间复杂度主要取决于递归调用的栈空间,栈的深度不超过 n。

class Solution 
{
public:
    int sum;
    int ret;

    void dfs(vector<int>& 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(vector<int>& nums, int target)
    {
        sum = target;

        dfs(nums, 0, 0);

        return ret;
    }
};

文章来源:https://blog.csdn.net/weixin_74268082/article/details/135165447
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。