Leetcode494. 目标和(HOT100)

链接

代码一:
纯递归:

 

// 递归
class Solution {
public:int cnt=0;void dfs(vector<int> &a,int u,int target,int sum){if(u==a.size()){if(sum==target) cnt++;//当 u// 等于数组的大小时,表示已经处理了所有的元素,此时检查 sum 是否等于target return;}dfs(a,u+1,target,sum+a[u]);dfs(a,u+1,target,sum-a[u]);}int findTargetSumWays(vector<int>& a, int target) {dfs(a,0,target,0);//递归的数组,递归到了哪个下标,递归的和,当前和return cnt;}
};
// //
// 在这段代码中,时间复杂度是O(2^n),原因是因为我们对每个元素都有两个选择:要么加上这个元素,要么减去这个元素。这里的n是数组的长度。

代码二:
动态规划:

//dp
// class Solution {
// public:
//     int findTargetSumWays(vector<int>& a, int target) {
//         int n = a.size(), Offset = 1000;//设置一个偏移量,用于将负数索引转换为非负索引。由于 target 和数组元素的范围是 [-1000, 1000],我们可以将其映射到 [0, 2000] 的范围。
//         if (target < -1000 || target > 1000)
//             return 0;
//         vector<vector<int>> f(n + 1, vector<int>(2001));// f[i][j] 表示使用前 i 个元素,得到和为 j 的方式有多少种。
//         f[0][0 + Offset] = 1;//初始化条件,表示使用 0 个元素得到和为 0 的方式有 1 种(什么都不做)。
//         for (int i = 1; i <= n; i++) {//遍历数组所有元素
//             for (int j = -1000; j <= 1000; j++) {//每遍历到某个元素,都查看加上它或者减去它,得到的结果还在不在范围中,如果在,就存起来
//                 if (j - a[i - 1] >= -1000)//如果当前和减去当前元素仍在有效范围内,更新状态
//                     f[i][j + Offset] += f[i - 1][j - a[i - 1] + Offset];
//                 if (j + a[i - 1] <= 1000)//如果当前和加上当前元素仍在有效范围内,同样更新状态
//                     f[i][j + Offset] += f[i - 1][j + a[i - 1] + Offset];
//             }
//         }
//         return f[n][Offset + target];//返回使用 n 个元素得到目标和 target 的方式有多少种。
//     }
// };

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/479339.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

文件上传upload-labs-docker通关

&#xff08;图片加载不出&#xff0c;说明被和谐了&#xff09; 项目一&#xff1a; sqlsec/ggctf-upload - Docker Image | Docker Hub 学习过程中,可以对照源码进行白盒分析. 补充&#xff1a;环境搭建在Linux虚拟机上的同时&#xff0c;以另一台Windows虚拟机进行测试最…

【Android】静态广播接收不到问题分析思路

参考资料&#xff1a; Android 静态广播注册流程(广播2)-CSDN博客 Android广播发送流程(广播3)_android 发送广播-CSDN博客 https://zhuanlan.zhihu.com/p/347227068 在Android中&#xff0c;静态广播如果静态广播不能接收&#xff0c;我们可以从整个流程中去分析&#xff…

2024 APMCM亚太数学建模C题 - 宠物行业及相关产业的发展分析和策略(详细解题思路)

在当下&#xff0c; 日益发展的时代&#xff0c;宠物的数量应该均为稳步上升&#xff0c;在美国出现了下降的趋势&#xff0c; 中国 2019-2020 年也下降&#xff0c;这部分变化可能与疫情相关。需要对该部分进行必要的解释说明。 问题 1: 基于附件 1 中的数据及您的团队收集的额…

Git简单介绍

一、 Git介绍与安装 1.1 Git简介 Git是一个开源的分布式版本控制系统&#xff0c;可以有效、高速地处理从很小到非常大的项目版本管理。 1.2集中式(SVN&#xff09; VS 分布式(git) 集中式版本控制系统&#xff0c;版本库是集中存放在中央服务器的&#xff0c;工作时要先从中央…

CSS之3D转换

三维坐标系 三维坐标系其实就是指立体空间&#xff0c;立体空间是由3个轴共同组成的。 x轴:水平向右注意:x右边是正值&#xff0c;左边是负值 y轴:垂直向下注意:y下面是正值&#xff0c;上面是负值 z轴:垂直屏幕注意:往外面是正值&#xff0c;往里面是负值 3D移动 translat…

kafka生产者和消费者命令的使用

kafka-console-producer.sh 生产数据 # 发送信息 指定topic即可 kafka-console-producer.sh \ --bootstrap-server bigdata01:9092 \ --topic topicA # 主题# 进程 29124 ConsoleProducer kafka-console-consumer.sh 消费数据 # 消费数据 kafka-console-consumer.sh \ --boo…

基于Springboot的心灵治愈交流平台系统的设计与实现

基于Springboot的心灵治愈交流平台系统 介绍 基于Springboot的心灵治愈交流平台系统&#xff0c;后端框架使用Springboot和mybatis&#xff0c;前端框架使用Vuehrml&#xff0c;数据库使用mysql&#xff0c;使用B/S架构实现前台用户系统和后台管理员系统&#xff0c;和不同级别…

【人工智能】Python常用库-Scikit-learn常用方法教程

Scikit-learn 是一个功能强大的机器学习库&#xff0c;支持数据预处理、分类、回归、聚类、降维等功能&#xff0c;广泛用于模型开发与评估。以下是 Scikit-learn 的常用方法及详细说明。 1. 安装与导入 安装 Scikit-learn&#xff1a; pip install scikit-learn导入基本模块…

Tcon技术和Tconless技术介绍

文章目录 TCON技术&#xff08;传统时序控制器&#xff09;定义&#xff1a;主要功能&#xff1a;优点&#xff1a;缺点&#xff1a; TCONless技术&#xff08;无独立时序控制器&#xff09;定义&#xff1a;工作原理&#xff1a;优点&#xff1a;缺点&#xff1a; TCON与TCONl…

计算机基础(下)

内存管理 内存管理主要做了什么&#xff1f; 操作系统的内存管理非常重要&#xff0c;主要负责下面这些事情&#xff1a; 内存的分配与回收&#xff1a;对进程所需的内存进行分配和释放&#xff0c;malloc 函数&#xff1a;申请内存&#xff0c;free 函数&#xff1a;释放内存…

【青牛科技】TS223 单触摸键检测IC

概 述 &#xff1a; TS223是 触 摸 键 检 测 IC&#xff0c; 提 供 1个 触 摸 键 。 触 摸 检 测 IC是 为 了用 可 变 面 积 的 键 取 代 传 统 的 按 钮 键 而 设 计 的 。低 功 耗 和 宽 工 作 电压是 触 摸 键 的 DC和 AC特 点 。TS223采 用 SSOP16、 SOT23-6的 封 装 形 式…

CUDA补充笔记

文章目录 一、不同核函数前缀二、指定kernel要执行的线程数量三、线程需要两个内置坐标变量来唯一标识线程四、不是blocksize越大越好&#xff0c;上限一般是1024个blocksize 一、不同核函数前缀 二、指定kernel要执行的线程数量 总共需要线程数是&#xff1a; 1 * N N个线程…

“华为杯”研究生数学建模比赛历年赛题汇总(2004-2024)

文章目录 赛题链接历年赛题2004年赛题2005年赛题2006年赛题2007年赛题2008年赛题2009年赛题2010年赛题2011年赛题2012年赛题2013年赛题2014年赛题2015年赛题2016年赛题2017年赛题2018年赛题2019年赛题2020年赛题2020年赛题2021年赛题2022年赛题2023年赛题2024年赛题 赛题链接 部…

Python学习指南 + 谷歌浏览器如何安装插件

找往期文章包括但不限于本期文章中不懂的知识点&#xff1a; 个人主页&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 所属专栏&#xff1a; Python 目录 前言 Python 官方文档的使用 谷歌浏览器中如何安装插件 前言 在学习Python时&#xff0c;我们可能会出现这样的困惑&#x…

java写一个石头剪刀布小游戏

石头剪刀布是一款经典的手势游戏,通常由两人参与,玩法简单且充满趣味。玩家通过出示手势代表“石头”、“剪刀”或“布”,并根据规则比较手势决定胜负。它广泛用于休闲娱乐、决策或解压活动。 一、功能简介 用户与计算机对战。 用户输入选择:石头、剪刀或布。 计算机随机生…

docker如何安装redis

第一步 如果未指定redis&#xff0c;则安装的是最新版的 docker pull redis 创建一个目录 mkdir /usr/local/docker/redis 然后直接可以下载redis&#xff0c;这是方式确实不怎么好&#xff0c;应该找在官网上找对应的redis配置文件 wget http://download.redis.io/redis-stab…

【作业九】RNN-SRN-Seq2Seq

点击查看作业内容 目录 1 实现SRN &#xff08;1&#xff09;使用numpy实现 &#xff08;2&#xff09;在&#xff08;1&#xff09;的基础上&#xff0c;增加激活函数tanh &#xff08;3&#xff09;使用nn.RNNCell实现 &#xff08;4&#xff09;使用nn.RNN实现 2 使用R…

利用Docker容器技术部署发布web应用程序

Docker是什么&#xff1f; docker 是一个开源的应用容器引擎&#xff0c;可以帮助开发者打包应用以及依赖包到一个可移植的容器中&#xff0c;然后发布到任何流行的Linux机器上&#xff0c;也可以实现虚拟化&#xff0c;容器是完全使用沙箱机制&#xff0c;相互之间不会有任何…

【AI学习】Mamba学习(十八):S6的硬件感知设计

上一篇Mamba的文章提到&#xff0c;S6 models这个名称的由来是&#xff1a;S4 models with a selection mechanism and computed with a scan。 所以&#xff0c;S6模型首先是选择机制&#xff1a;先前模型的一个关键限制对选择性复制和归纳等重要合成任务不够适用&#xff0c…

Bug Fix 20241122:缺少lib文件错误

今天有朋友提醒才突然发现 gitee 上传的代码存在两个很严重&#xff0c;同时也很低级的错误。 因为gitee的默认设置不允许二进制文件的提交&#xff0c; 所以PH47框架下的库文件&#xff08;各逻辑层的库文件&#xff09;&#xff0c;以及Stm32Cube驱动的库文件都没上传到Gi…