当前位置: 首页 > news >正文

代码随想录算法训练营第 35 天 | LeetCode 416. 分割等和子集

代码随想录算法训练营

Day35 代码随想录算法训练营第 35 天 | LeetCode 416. 分割等和子集


目录

  • 代码随想录算法训练营
  • 前言
    • LeetCode416. 分割等和子集
  • 一、LeetCode416. 分割等和子集
    • 1.题目链接
    • 2.思路
    • 3.题解


前言

LeetCode416. 分割等和子集

讲解文档


一、LeetCode416. 分割等和子集

1.题目链接

LeetCode416. 分割等和子集

2.思路

(1)为什么能用01背包:每个元素只能用一次
(2)子集是背包----背包最大容量:元素和/2
(元素和如果是偶数,不可能分成两个元素和相等的子集)
(3)物品重量:元素数值;物品价值:元素数值
(4)dp[j] 容量为j时,最大的价值之和
(5)判定两个子集元素和相等:
dp[sum/2]=sum/2
(装不满的情况:dp[7]=6 现在自己里面元素和还没有到sum/2,也就是7,但是剩下的任何元素放进去都会超出容量)

3.题解

class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size();// 元素只用一次,说明01背包// dp[i][j]  0-i的范围内 j是容量 dp表示最大价值// 背包最大的容量是sum/2,如果价值为sum/2则说明正好是的自己元素和相等// 元素数值看作物品容量和价值int dp[100001] = {0};int sum = accumulate(nums.begin(), nums.end(), 0);if (sum % 2)return false;int target = sum / 2;for (int i = 0; i < n; i++) {for (int j = target; j >= nums[i]; j--) {dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}return dp[target] == target;}
};

相关文章:

代码随想录算法训练营第 35 天 | LeetCode 416. 分割等和子集

代码随想录算法训练营 Day35 代码随想录算法训练营第 35 天 | LeetCode 416. 分割等和子集 目录 代码随想录算法训练营前言LeetCode416. 分割等和子集 一、LeetCode416. 分割等和子集1.题目链接2.思路3.题解 前言 LeetCode416. 分割等和子集 讲解文档 一、LeetCode416. 分割…...

伪国企是指的什么?

伪国企&#xff0c;也称为虚假国企&#xff0c;主要指的是那些通过不正当手段&#xff0c;如伪造文件、虚假宣传等&#xff0c;误导公众或第三方&#xff0c;使其误认为该企业具有国有企业背景或实际控制权的非国有企业。 一、伪国企类型 具体来说&#xff0c;伪国企可能包括…...

Transformer在量化投资中的应用

开篇 深度学习的发展为我们创建下一代时间序列预测模型提供了强大的工具。深度人工神经网络&#xff0c;作为一种完全以数据驱动的方式学习时间动态的方法&#xff0c;特别适合寻找输入和输出之间复杂的非线性关系的挑战。最初&#xff0c;循环神经网络及其扩展的LSTM网络被设…...

a++ 和 ++a

由于后缀递增/递减运算符需要返回原始值&#xff0c;这可能导致编译器生成额外的代码来保存原始值&#xff0c;因此在某些情况下&#xff0c;前缀递增/递减可能更高效。在不涉及表达式结果的上下文中&#xff08;例如&#xff0c;在单独的语句中&#xff09;&#xff0c;a和a的…...

Python配置文件格式——INI、JSON、YAML、XML、TOML

文章目录 对比INIJSONYAMLXMLTOML参考文献 对比 格式优点缺点是否支持注释INI简单易懂语言内置支持不支持复杂数据结构✓JSON支持复杂数据结构阅读起来不够直观YAML简洁有序支持复杂数据结构灵活但有歧义不同实现有兼容性问题✓XML支持复杂数据结构和命名空间语法冗长体积较大…...

The First项目报告:Web3人生模拟器,DegenReborn带你重开币圈

2023年6月14日&#xff0c;ReadON APP的首页上&#xff0c;一篇引人注目的文章《黑客马拉松奖&#xff1a;‘Degenreborn’——Meme与GameFi的梦幻交汇》跃然眼前&#xff0c;该文章巧妙融合了NFT、GameFi及Ethereum等热门话题&#xff0c;为读者带来了一场科技与娱乐的盛宴。 …...

燃气经营企业从业人员考试真题及答案

燃气经营企业从业人员考试真题及答案 11.《城镇燃气设计规范》中规定&#xff1a;当穿过卫生间、阁楼或壁柜时&#xff0c;燃气管道应采用&#xff08;&#xff09;连接(金属软管不得有接头)&#xff0c;并应设在钢套管内。 A.法兰 B.软管 C.焊接 D.丝扣 答案&#xff1a…...

白骑士的Matlab教学进阶篇 2.1 数据可视化

系列目录 上一篇&#xff1a;白骑士的Matlab教学基础篇 1.5 数据输入与输出 数据可视化是MATLAB的一个强大功能&#xff0c;它能够将数据以图形的形式展示出来&#xff0c;便于理解和分析。本文将介绍MATLAB中的基本绘图函数、绘制2D图形、绘制3D图形以及高级图形属性与定制的…...

2024年8月 | 涉及侵权、抄袭洗稿违规行为公示

为护社区良好氛围&#xff0c;守护清朗网络空间&#xff0c;CSDN持续对侵害他人权益、抄袭洗稿违规内容进行治理。 今年7月&#xff0c;CSDN共计删除涉及抄袭洗稿内容xx篇&#xff0c;下架侵权资源xx个&#xff0c;封禁违规账号42个。 部分违规账号公示 账号昵称处置结果封禁创…...

操作系统快速入门(四)

&#x1f600;前言 本篇博文是关于操作系统的&#xff0c;希望你能够喜欢 &#x1f3e0;个人主页&#xff1a;晨犀主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是晨犀&#xff0c;希望我的文章可以帮助到大家&#xff0c;您的满意是我的动力&#x1f609;&…...

前缀异或优化

前言&#xff1a;这个题目其实就是考察前缀和&#xff0c;正常情况下开二维数组来记录&#xff0c;但是也可以优化成一位的位运算 我们顺便可以学习一下如何进行查询二进制串中1的个数 class Solution { public:vector<bool> canMakePaliQueries(string s, vector<vec…...

AI学习指南深度学习篇-卷积神经网络中的正则化和优化

AI学习指南深度学习篇-卷积神经网络中的正则化和优化 在深度学习领域&#xff0c;卷积神经网络&#xff08;Convolutional Neural Networks&#xff0c;CNN&#xff09;是一类非常重要的模型&#xff0c;被广泛应用于图像识别、目标检测等任务中。然而&#xff0c;在训练CNN时…...

AutoGen Studio 本地源码构建

目录 一、环境配置 1.1 创建本地环境 1.2 下载 autogen 源码 1.3 安装依赖 2. 构建 3. 运行 本文主要介绍 AutoGen Studio 本地源码构建过程。 一、环境配置 1.1 创建本地环境 通过 conda 创建一个环境,Python 3.10+,Node.js 14.15.0+。 conda create -n autogen p…...

医疗陪诊系统源码详解:在线问诊APP开发的技术要点

如今&#xff0c;开发一款高效、可靠的在线问诊APP则成为了许多企业的目标。本篇文章&#xff0c;小编将详细解析医疗陪诊系统的源码&#xff0c;并探讨在线问诊APP开发的关键技术要点。 一、医疗陪诊系统的基本功能 在开始开发之前&#xff0c;首先需要明确医疗陪诊系统的基本…...

VSCode编译多个不同文件夹下的C++文件

实际上VSCode编译C文件就是通过向g传递参数实现的&#xff0c;因此即使是不同包下面的cpp文件或者.h文件都是可以通过修改g的编译参数实现&#xff0c;而在VSCode中&#xff0c;task.json文件其实就是在配置g的编译参数&#xff0c;因此我们可以通过修改task.json里面的参数&am…...

【安卓】连接真机和使用通知

文章目录 连接到真机使用通知通知的简单使用通知的详细信息 连接到真机 先用USB线将手机与电脑连接。 打开手机的设置&#xff0c;找到关于手机&#xff0c;点开之后&#xff0c;找到开发者选项界面。或者找到软件版本号&#xff0c;连续点击&#xff0c;系统会提示你点击几次能…...

CSS3下拉菜单实现

导航菜单&#xff1a; <nav class"multi_drop_menu"><!-- 一级开始 --><ul><li><a href"#">Power</a></li><li><a href"#">Money</a></li><li><a href"#"…...

Mysql8.3.0排序导致分页数据错乱

#业务场景 生产环境 仓库管理&#xff0c;能看到各个仓库的C库位 物料管理&#xff0c;编辑物料&#xff0c;弹框时选择库位时&#xff0c;7页数据&#xff0c;没有C库位&#xff0c;查询条件指定C&#xff0c;能查到数据 本地环境 数据还原到本地 弹框数据在2页与第3页看…...

漏洞复现-Cacti命令执行漏洞 (CVE-2022-46169)

1.漏洞描述 Cacti是一套基于PHP&#xff0c;MySQL&#xff0c;SNMP及RRDTool开发的网络流量监测图形分析工具&#xff0c;可为用户提供强大且可扩展的操作监控和故障管理框架。 该漏洞存在于remote_agent.php文件中&#xff0c;未经身份验证的恶意攻击者可以通过设置HTTP_变量…...

【Ajax使用说明】Ajax、Axios以及跨域

目录 一、原生Ajax 1.1 Ajax简介 1.2 XML简介 1.3 AJAX 的特点 1.3.1 AJAX的优点 1.3.2 AJAX 的缺点 1.4 AJAX 的使用 1.4.1AJAX的基本操作 1.4.2AJAX的传参 1.4.3 AJAX的post请求及设置请求体 1.4.4 AJAX响应json数据 1.4.5 AJAX请求超时与网络异常处理 1.4.5 AJ…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...