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

【力扣刷题 | 第二十四天】

目录

前言:

416. 分割等和子集 - 力扣(LeetCode)

总结


前言:

        今晚我们爆刷动态规划类型的题目。

416. 分割等和子集 - 力扣(LeetCode)

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

 这道题其实可以用我们之前讲过的回溯算法暴力搜索来做,其基本思想为:我们先对这个数组求和,之后再除以二,此时如果我们如果我们得到了一个整数,就说明这个数组是可以分为两个元素和一样的子集的,如果得不到就说明这个数组根本就没有办法被均分,自然也就无法得到两个元素和一样的子集。

 那么也就是说把这个集合的总和的一半target求出来,然后在集合中搜索,如果可以在原集合中找到一个子集的和==target,那么另一半子集的和自然也就是target。

因此我们简化了这个问题,现在我们要做的是:

在这个集合中找出一个子集,使得子集的和等于target

但问题是使用回溯算法暴力搜索的话,就这道题而言,会超时。因此我们就要再想想还有没有别的方法

答案是有的。其实我们可以把他想为一个背包问题:一共有这么多的数,能否把容量为target的包满

那么不就是一个动态规划的问题嘛那么我们就开始动态规划的五步:
1.确定dp数组的含义以及下标含义:

dp[j]  容量为j的背包 能够容纳的最多价值为 dp[j],而这道题我们可以认为每一个元素的数值即是容量也是价值

如果我们把11这个背包装满之后,他的价值也是11,那么就说明存在一个子集,他的元素和为target

2.状态转移方程:dp[j]= max(dp[j] , dp[j-nums[i]]+nums[i[);

因此我们可以得到代码:

class Solution {
public:bool canPartition(vector<int>& nums) {int sum=0;vector<int> dp(10001, 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;}else{return false;}}
};

总结

        动态规划的题目更加灵活多变,有的时候很难想出来这还能用动态规划的思路来做,因此我们要多做多练,才可以学好动态规划。

如果我的内容对你有帮助,请点赞,评论,收藏。创作不易,大家的支持就是我坚持下去的动力!

 

相关文章:

【力扣刷题 | 第二十四天】

目录 前言&#xff1a; 416. 分割等和子集 - 力扣&#xff08;LeetCode&#xff09; 总结 前言&#xff1a; 今晚我们爆刷动态规划类型的题目。 416. 分割等和子集 - 力扣&#xff08;LeetCode&#xff09; 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这…...

PyTorch使用(一)(常用库)

1.各大模型库 hub&#xff1a;简单来说就是专门为PyTorch集成的算法模型库 网站&#xff1a;GitHub - pytorch/hub: Submission to https://pytorch.org/hub/ Model Zoo&#xff1a;这个平台上提供预训练模型&#xff0c;在每个模型上&#xff0c;会标注出这个模型在GitHub的标…...

React ~ React Router 6

React Router 6 VS React Router 5.x 内置组件的变化; 移除<Switch /> , 新增<Routes />语法的变化; component { About } 变为 element { <About /> }新增多个hook官方明确推荐函数式组件了! 一级路由(变化) 安装路由 npm i react-router-dom (默认是最…...

【LeetCode每日一题】——304.二维区域和检索-矩阵不可变

文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】 矩阵 二【题目难度】 中等 三【题目编号】 304.二维区域和检索-矩阵不可变 四【题目描述】 …...

硬件串口通信协议学习(UART、IIC、SPI、CAN)

0.前言 学习资料&#xff1a;江协科技的个人空间-江协科技个人主页-哔哩哔哩视频 通信的目的&#xff1a;将一个设备的数据传送到另一个设备&#xff0c;扩展硬件系统通信协议&#xff1a;制定通信的规则&#xff0c;通信双方按照协议规则进行数据收发 全双工&#xff1a;通信…...

第一章-JavaScript基础进阶part2:事件

文章目录 概念一、注册事件&#xff08;绑定事件&#xff09;1.1 addEventListener事件监听 二、删除事件&#xff08;解绑&#xff09;三、DOM事件流四、事件对象event4.1 e.target与this与e.currentTarget的区别4.2 事件对象的常见属性 五、阻止事件默认行为及冒泡六、事件委…...

如何优雅的使用后端接口

优雅的后端接口 一个后端接口大致分为四个部分&#xff1a;接口地址(url)、接口请求方式(get、post等)、请求数据(request)、响 应数据(response)。 一、URL & Method Rest 设计风格 》 Restful API 简单理解&#xff1a; URI 是用来唯一标志一个互联网资源&#xff1b;Me…...

QEMU源码全解析25 —— QOM介绍(14)

接前一篇文章&#xff1a;QEMU源码全解析24 —— QOM介绍&#xff08;13&#xff09; 本文内容参考&#xff1a; 《趣谈Linux操作系统》 —— 刘超&#xff0c;极客时间 《QEMU/KVM》源码解析与应用 —— 李强&#xff0c;机械工业出版社 特此致谢&#xff01; 本文开始对于…...

TopK问题

topK问题&#xff1a; N个数找最大或者最小的前k个。 例子&#xff1a; 优质筛选&#xff08;店面的排名&#xff09; 10000个数&#xff0c;找出最大的前10个数 解决思路&#xff1a;建立大堆&#xff0c;然后pop9次 但是有些场景&#xff0c;上面的思路…...

接口自动化测试-Postman+Newman+Git+Jenkins实战集成(详细)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、Postman 创建…...

CMake 学习笔记 (Generator Expressions)

CMake 学习笔记 &#xff08;Generator Expressions&#xff09; Generator Expressions 可以认为是一种特殊的变量&#xff0c;它会在编译阶段求值。通常用在 target_link_libraries(), target_include_directories(), target_compile_definitions() 上。 用 Generator Expr…...

提高测试用例质量的6大注意事项

在软件测试中&#xff0c;经常会遇到测试用例设计不完整&#xff0c;用例没有完全覆盖需求等问题&#xff0c;这样往往容易造成测试工作效率低下&#xff0c;不能及时发现项目问题&#xff0c;无形中增加了项目风险。 因此提高测试用例质量&#xff0c;就显得尤为重要。一般来说…...

2023牛客暑期多校训练营6 A-Tree (kruskal重构树))

文章目录 题目大意题解参考代码 题目大意 ( 0 ≤ a i ≤ 1 ) , ( 1 ≤ c o s t i ≤ 1 0 9 ) (0\leq a_i\leq 1),(1 \leq cost_i\leq 10^9) (0≤ai​≤1),(1≤costi​≤109) 题解 提供一种新的算法&#xff0c;kruskal重构树。 该算法重新构树&#xff0c;按边权排序每一条边…...

软件测试—支付功能测试

有人问过我这样一个问题&#xff1a;作为一个支付平台&#xff0c;接入了快钱、易宝或直连银行等多家的渠道&#xff0c;内在的产品流程是自己的。业内有什么比较好的测试办法&#xff0c;来测试各渠道及其支持的银行通道呢&#xff1f; 回答&#xff1a;对支付平台而言&#…...

自动化测试的统筹规划

背景 回顾以前自动化测试编写的经历&#xff0c;主要是以开发者自驱动的方式进行&#xff0c;测试的编写随心而动&#xff0c;没有规划&#xff0c;也没有章法&#xff0c;这样就面临如下的一些问题&#xff1a; 测试用例设计不到位&#xff0c;覆盖不全&#xff0c;或者不够…...

外键字段的增删改查、多表查询(子查询和连表查询、正反向、聚合查询、 分组查询、 F与Q查询)、django中如何开启事务

一、 外键字段的增删改查 1.多对多的外键增删改查图书和作者是多对多&#xff0c;借助于第三张表实现的&#xff0c;如果想绑定图书和作者的关系&#xff0c;本质上就是在操作第三方表2.如何操作第三张表问题&#xff1a;让你给图书添加一个作者&#xff0c;他俩的关系可是多对…...

【学习笔记】生成式AI(ChatGPT原理,大型语言模型)

ChatGPT原理剖析 语言模型 文字接龙 ChatGPT在测试阶段是不联网的。 ChatGPT背后的关键技术&#xff1a;预训练&#xff08;Pre-train&#xff09; 又叫自监督式学习&#xff08;Self-supervised Learning&#xff09;&#xff0c;得到的模型叫做基石模型&#xff08;Founda…...

【Opencv入门到项目实战】(三):图像腐蚀与膨胀操作

文章目录 1.腐蚀操作2.膨胀操作3.开运算和闭运算4.礼帽与黑帽5.梯度运算 1.腐蚀操作 腐蚀操作是图像处理中常用的一种形态学操作&#xff0c;我们通常用于去除图像中的噪声、分割连通区域、减小目标物体的尺寸等。腐蚀操作的原理是&#xff0c;在给定的结构元素下&#xff0c;…...

Autosar诊断系列介绍20 - UDS应用层P2Server/P2Client等时间参数解析

本文框架 1. 前言2.几个时间参数含义2.1 P2Client与P2Server2.2 P2*Client与P2*Server2.3 P3Client_Phys与P3Client_Func2.4 S3Client与S3Server 1. 前言 本系列Autosar 诊断入门介绍&#xff0c;会详细介绍诊断相关基础知识&#xff0c;如您对诊断实战有更高需求&#xff0c;…...

【iOS】json数据解析以及简单的网络数据请求

文章目录 前言一、json数据解析二、简单的网络数据请求三、实现访问API得到网络数据总结 前言 近期写完了暑假最后一个任务——天气预报&#xff0c;在里面用到了简单的网络数据请求以及json数据的解析&#xff0c;特此记录博客总结 一、json数据解析 JSON是一种轻量级的数据…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...