代码随想录算法训练营第三十六天|leetcode416题

news/2024/4/19 11:50:52/

一、leetcode第416题

本题要求数组分成两个子集,子集的和是否相等,可以转化为0-1背包问题,即背包容量为数组元素和的1/2,物品大小即为元素大小。设置dp数组,dp[i]表示为背包容量为i能放置的元素大小,可知dp[i]为不放第i个元素和放第i个元素二者的最大值,由于单层数组的特殊性要从后向前遍历才能使得每一个元素只参与dp数组运算一次,最后如果dp数组中下标为target的元素值为target则为true,否则返回false。

具体代码如下:

class Solution {
public:bool canPartition(vector<int>& nums) {vector<int>dp(10001,0);int sum=0;for(int i=0;i<nums.size();i++){sum+=nums[i];}if(sum%2==1){return false;}int target=sum/2;for(int i=0;i<nums.size();i++){for(int j=target;j>=nums[i];j--){dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);}}if(dp[target]==target){return true;}return false;}
};


http://www.ppmy.cn/news/1404995.html

相关文章

学习python,这篇就够

此文章全面介绍了python语言的基础知识&#xff0c;不过还有第7章文件与数据格式化还未介绍&#xff0c;短期内会及时补充上&#xff0c;不用担心。 因作者水平有限&#xff0c;文章如果有不足的地方&#xff0c;欢迎提出。 文章有的地方可能会有错别字&#xff0c;但不影响学…

八股 -- C#

面向对象 &#xff08;三大特性&#xff09; 三大特性目的是为了提供更好的代码组织、可维护性、扩展性和重用性 C#基础——面向对象 - 知乎 (zhihu.com) 封装 理解&#xff1a; 你不需要了解这个方法里面写了什么代码&#xff0c;你只需要了解这个方法能够给你返回什么数据&…

解密SqlServer数据库引擎:探寻SqlServer的神秘力量(二)

本系列文章简介&#xff1a; 在当今数字化时代&#xff0c;数据库扮演着至关重要的角色。它们是组织和企业存储数据的核心&#xff0c;并为应用程序提供稳定、高效的数据访问。而在众多数据库中&#xff0c;SqlServer无疑是最为强大和受欢迎的之一。 SqlServer是由微软开发的关…

关于atoi函数的使用和模拟实现

这篇文章是关于atoi函数是怎样使用的和我们如何模拟实现它的。话不多说&#xff0c;我们先从C网站上关于atoi的函数信息入手。 函数分析 首先我们可以看到它的返回值是int&#xff0c;形参是一个字符串的首字母地址&#xff0c;它可以省略从字符串开始知道遇见的第一个非空白字…

关于 QSound播放wav音频文件,播放失败“using null output device, none available” 的解决方法

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/137264493 红胖子(红模仿)的博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV、OpenGL、ffmpeg、OSG、单片机、软…

【Node.js从基础到高级运用】二十一、使用child_process模块创建子进程

引言 在Node.js中&#xff0c;child_process模块是一个提供了创建和管理子进程的能力的核心模块。通过使用child_process模块&#xff0c;Node.js可以执行系统命令、运行其他脚本或应用程序&#xff0c;实现与Node.js进程的并行处理。 child_process模块提供了几种创建子进程的…

dotnet依赖注入与IOC

依赖注入与IOC IOC IOC 是 Inversion of Control&#xff08;控制反转&#xff09;的缩写。在软件开发中&#xff0c;IOC 是一种设计模式&#xff0c;它改变了传统的程序设计流程&#xff0c;使得对象之间的依赖关系由代码本身控制变为由外部容器控制。 而采用IOC 设计模式后&…

iOS开发进阶(十三):脚手架创建iOS项目

文章目录 一、前言二、xcode-select 命令三、拓展阅读 一、前言 项目初期&#xff0c;需要搭建项目基本框架&#xff0c;为此离不开辅助工具&#xff0c;即脚手架。当然&#xff0c;IDE也可以实现新建空白项目&#xff0c;但是其新建后的项目结构可能不符合预期设计&#xff0…

基于深度学习的危险物品检测系统(网页版+YOLOv8/v7/v6/v5代码+训练数据集)

摘要&#xff1a;本文详细介绍基于YOLOv8/v7/v6/v5的危险物品检测技术。主要采用YOLOv8技术并整合了YOLOv7、YOLOv6、YOLOv5的算法&#xff0c;进行了细致的性能指标对比分析。博客详细介绍了国内外在危险物品检测方面的研究现状、数据集处理方法、算法原理、模型构建与训练代码…

STM32重要参考资料

stm32f103c8t6 一、引脚定义图 二、时钟树 三、系统结构图 四、启动配置 &#xff08;有时候不小心短接VCC和GND&#xff0c;芯片会锁住&#xff0c;可以BOOT0拉高试试&#xff08;用跳线帽接&#xff09;&#xff09; 五、最小系统原理图 可用于PCB设计

宝塔面板提示当前未安装docker或docker-compose有效解决方案!

宝塔面板提示当前未安装docker或docker-compose有效解决方案&#xff01; 首先点面板的安装docker后依旧提示【当前未安装docker或docker-compose,点击安装】&#xff0c;解决方法就是输入两条命令后刷新即可&#xff0c;命令ln -s /usr/local/bin/docker-compose /usr/bin/doc…

【mysql 第3-10条记录怎么查】

mysql 第3-10条记录怎么查 在MySQL中&#xff0c;如果你想要查询第3到第10条记录&#xff0c;你通常会使用LIMIT和OFFSET子句。但是&#xff0c;需要注意的是&#xff0c;LIMIT和OFFSET是基于结果集的行数来工作的&#xff0c;而不是基于记录的物理位置。这意味着它们通常与某种…

深度学习500问——Chapter05: 卷积神经网络(CNN)(2)

文章目录 5.6 有哪些池化方法 5.7 1x1卷积作用 5.8 卷积层和池化层有什么区别 5.9 卷积核是否一定越大越好 5.10 每层卷积是否只能用一种尺寸的卷积核 5.11 怎样才能减少卷积层参数量 5.12 在进行卷积操作时&#xff0c;必须同时考虑通道和区域吗 5.13 采用宽卷积的好处有什么 …

某音乐平台歌曲信息逆向之参数寻找

如何逆向加密参数&#xff1a;某音乐平台歌曲信息逆向之webpack扣取-CSDN博客 参数构建 {"comm": {"cv": 4747474,"ct": 24,"format": "json","inCharset": "utf-8","outCharset": "ut…

续-开发组件更新-提效工具分享

前言 小一个月没更新了&#xff0c;有各种各样的事啦&#xff0c;这一篇有点水吧。围绕两方面&#xff0c;开发组件更新以及IDEA插件的分享&#xff0c;题目和我一样水&#xff0c;有点像是日本轻小说取名了&#xff0c;整这么长。本篇的触动来源于&#xff0c;我今天偶然发现…

#设计模式#3.1用做松鼠桂鱼来理解抽象工厂(对象创建型模式)

概念&#xff1a;xx工厂&#xff0c;xx产品 区分 工厂是动作&#xff0c;产品是结果&#xff08;菜品&#xff09; 概念&#xff1a;抽象xx&#xff0c;具体xx 区分 抽象产品&#xff1a;“中式菜品” 具体产品&#xff1a;“麻婆豆腐”、“宫保鸡丁” 抽象工厂&#xff1a;“…

AWS相关服务说明

互联网网关 官网 # 官网 https://docs.aws.amazon.com/zh_cn/vpc/latest/userguide/VPC_Internet_Gateway.htmlInternet 网关是一种横向扩展、冗余且高度可用的 VPC 组件&#xff0c;支持在 VPC 和 Internet 之间进行通信。它支持 IPv4 和 IPv6 流量。它不会对您的网络流量造…

[Linux]基础IO(中)---理解重定向与系统调用dup2的使用、缓冲区的意义

重定向理解 在Linux下&#xff0c;当打开一个文件时&#xff0c;进程会遍历文件描述符表&#xff0c;找到当前没有被使用的 最小的一个下标&#xff0c;作为新的文件描述符。 代码验证&#xff1a; ①&#xff1a;先关闭下标为0的文件&#xff0c;在打开一个文件&#xff0c;…

合并两个单链表

归纳编程学习的感悟&#xff0c; 记录奋斗路上的点滴&#xff0c; 希望能帮到一样刻苦的你&#xff01; 如有不足欢迎指正&#xff01; 共同学习交流&#xff01; &#x1f30e;欢迎各位→点赞 &#x1f44d; 收藏⭐ 留言​&#x1f4dd; 但行前路&#xff0c;不负韶华&#…

探析Drools规则引擎的工作机制

目录 一、工作原理 二、工作流程 2.1 初始化环境 2.2 添加规则文件 2.3 编译规则文件 2.4 插入到工作内存 2.5 规则匹配与激活 2.6 规则执行 三、Drools 其他特性 3.1 符合事实 3.2 决策表 3.3 规则生命周期管理 3.4 规则流 四、Rete 算法 一、工作原理 Drools 规则引擎的工…