当前位置: 首页 > 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是一种轻量级的数据…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...