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

算法刷题记录 Day36

算法刷题记录 Day36

Date: 2024.04.02

lc 416. 分割等和子集

//2. 一维数组
class Solution {
public:bool canPartition(vector<int>& nums) {// 将问题转化为从数组中任意取数,使得容量为数组总和一半的背包内的价值尽可能大。// dp[j]表示容积为j的背包中,能装的最大价值。// dp[j] = for(int i=n-1; i>=0; i++) max(dp[j], dp[j-nums[i]]+nums[i]);int n = nums.size();int count = 0;for(auto& x: nums){count += x;}int half_count = count / 2;vector<int> dp(half_count+1, 0);for(int i=0; i<n; i++){for(int j=half_count; j>=nums[i]; j--){dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]);}}if(dp[half_count] == (count - half_count))return true;elsereturn false;}
};// 1. 二维数组
class Solution {
public:bool canPartition(vector<int>& nums) {// 将问题转化为从数组中任意取数,使得容量为数组总和一半的背包内的价值尽可能大。// dp[i][j] 表示从第[0, i]个数中,容积为j的背包的最大价值;// dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]]+v[i]);// 初始化第一行中,j大于等于nums[0]的为j,其余为0;int n = nums.size();int count = 0;for(auto& x: nums){count += x;}int half_count = count / 2;vector<vector<int>> dp(n, vector<int>(half_count+1, 0));for(int j=nums[0]; j<=half_count; j++){dp[0][j] = nums[0];}for(int i=1; i<n; i++){for(int j=0; j<=half_count; j++){if(j < nums[i])dp[i][j] = dp[i-1][j];else{dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i]]+nums[i]);}}}// for(int i=0; i<n; i++){//     for(int j=0; j<=half_count; j++){//         cout<<"i:"<<i<<", j:"<<j<<", value:"<<dp[i][j]<<endl;//     }// }if(dp[n-1][half_count] == (count - half_count))return true;elsereturn false;}
};

相关文章:

算法刷题记录 Day36

算法刷题记录 Day36 Date: 2024.04.02 lc 416. 分割等和子集 //2. 一维数组 class Solution { public:bool canPartition(vector<int>& nums) {// 将问题转化为从数组中任意取数&#xff0c;使得容量为数组总和一半的背包内的价值尽可能大。// dp[j]表示容积为j的…...

面试必问 - CSS 中元素居中小技巧

在网页设计中&#xff0c;居中是一个至关重要的布局技巧&#xff0c;能够确保你的页面在不同设备和屏幕尺寸上呈现出优雅的样式。 在这篇文章中&#xff0c;将介绍一些 CSS 居中的基本技巧&#xff0c;适用于各种场景。 1. 水平居中 文本水平居中 通过设置 text-align: cen…...

Chatgpt润色论文

使用ChatGPT进行论文润色时的指令 1.英语学术润色 模板&#xff1a;Below is a paragraph from an academic paper. Polish the writing to meet the academic style,improve the spelling, grammar, clarity, concision and overall readability. When necessary, rewrite th…...

51单片机实验02- P0口流水灯实验

目录 一、实验的背景和意义 二、实验目的 三、实验步骤 四、实验仪器 五、实验任务及要求 1&#xff0c;从led4开始右移 1&#xff09;思路 ①起始灯 &#xff08;led4&#xff09; ②右移 2&#xff09;效果 3&#xff09;代码☀ 2&#xff0c;从其他小灯并向右依…...

使用git 和 github协作开发

文章目录 github浏览器汉化插件github新建仓库git安装以及ssh配置团队创建及基本命令的使用创建团队基本命令 分支管理快速切换远程仓库地址 如何使用git && github进行协作开发&#xff0c;包括git常见基础命令 github浏览器汉化插件 在刚开始使用github的时候&#…...

DataX,MongoDB数据导入hdfs与mysql

【尚硅谷】Alibaba开源数据同步工具DataX技术教程【尚硅谷】Alibaba开源数据同步工具DataX技术教程_哔哩哔哩_bilibili 目录 1、MongoDB 1.1、MongoDB介绍 1.2、MongoDB基本概念解析 1.3、MongoDB中的数据存储结构 1.4、MongoDB启动服务 1.5、MongoDB小案例 2、DataX导入…...

【OpenCV-颜色空间】

OpenCV-颜色空间 ■ RGB■ BGR■ HSV■ HSL■ HUE■ YUV ■ RGB ■ BGR BGR 就是RGB R和B调换位置。 OpenCV 默认使用BGR ■ HSV ■ HSL ■ HUE ■ YUV...

电脑硬盘分区表的两种格式:MBR 和 GPT

电脑硬盘分区表的两种格式&#xff1a;MBR 和 GPT 段子手168 2024-4-5 电脑硬盘分区表有两种格式&#xff1a;MBR 和 GPT&#xff1a; 一、MBR 分区表 1.MBR 是主引导记录 (Master Boot Record) 的英文缩写 在传统&#xff08;Legacy&#xff09;硬盘分区模式中&#xff0c…...

kafka 常用非基础的核心设置项

在测试的过程中&#xff0c;心血来潮&#xff0c;想要测试下新topic中还没被消费的消息。专门查了下ai&#xff0c;奈何一本正经的胡说八道&#xff0c;浪费了点时间。现在记录下&#xff1a; 解决topic缺失时项目无法启动 &#xff0c; 报错&#xff1a; Topic(s) [……] is/a…...

杂谈 EV之我见

每周至少更新一片博文&#xff0c;没有目的的看代码是没有效率的&#xff0c;带着目的去看代码才会有所得&#xff0c; 目前车载行业火爆&#xff0c;得益于EV和AI技术的发展&#xff0c;汽车从一个传统工业产品&#xff0c;摇身一变成为了前沿科技产品。 小米su7的发布会我看…...

白色磨砂质感html5页源码

白色磨砂质感html5页源码&#xff0c;简约的基础上加上了团队成员&#xff0c;自动打字特效音乐播放器存活时间 源码下载 https://www.qqmu.com/2980.html...

sqlite建立数据库

在做一些简单的实验项目的时候&#xff0c;sqlite比较好用&#xff08;MacOS验视环境&#xff09;。相关包下载网页&#xff1a;https://www.sqlite.org/download.html 1 创建数据文件目录 cd /<project_path> mkdir database cd /database2 创建数据库 在当前目录&am…...

HTML5标签(网页编程)

一、常用标签 HTML5&#xff08;或HTML&#xff09;中有很多常用的标签&#xff0c;这些标签用于构建网页的结构和内容。以下是一些常用的HTML5标签&#xff1a; 1. 标题标签 <h1> 到 <h6>&#xff1a;定义六个级别的标题&#xff0c;<h1> 级别最高&#…...

RabbitMQ小记

参考书籍&#xff1a;朱忠华的《RabbitMQ实战指南》 一、基础概念 1.Exchange 1.1 创建方法的参数&#xff0c;exchangeDeclare() exchange&#xff1a;交换器的名称type&#xff1a;交换器的类型durable&#xff1a;是否持久化&#xff0c;true代表持久化。&#xff08;持…...

【备忘录】docker-maven-plugin 使用

在使用docker-maven-plugin 插件时&#xff0c;经常会碰到一些奇怪的问题&#xff1a; 比如&#xff1a; 1、docker远程访问时&#xff0c;认证安全问题&#xff1f; 2、dockerHost 访问地址准确性&#xff1f; 3、需要多个tag时如何处理&#xff1f; 4、push 到仓库时&#xf…...

一起学习python——基础篇(10)

前言&#xff0c;Python 是一种面向对象的编程语言。以前大学读书的时候经常开玩笑说的一句话“如果没有对象&#xff0c;就new一个”。起因就是编程老师上课时经常说一句“首先&#xff0c;我们new一个对象”。 今天讲一下python的类和对象。 类是什么&#xff1f;它是一种用…...

LoRa自组网络设计 6

1 深入了解LoRaWan 1.1 LoRaWan概述 LoRaWAN采用星型无线拓扑 End Nodes 节点 Gateway 网关 Network Server 网络服务器 Application Server 应用服务器 LoRa联盟是2015年3月Semtech牵头成立的一个开放的、非盈利的组织&#xff0c;发起成员还有法国Actility&#xff0c;中国…...

C++手撕红黑树

文章目录 红黑树概念性质&#xff08;条件限制&#xff09;节点的定义红黑树的结构红黑树的插入cur为红&#xff0c;p为红&#xff0c;g为黑&#xff0c;u存在且为红cur为红&#xff0c;p为红&#xff0c;g为黑&#xff0c;u不存在或u为黑&#xff0c;插入到p对应的一边cur为红…...

计算机中,逻辑端口

计算机中,端口是什么 在计算机领域中,端口(Port)是一个逻辑概念,用于标识计算机与外部设备或另一台计算机通信时的出入口。它是计算机与外部通信的途径,分为物理端口和逻辑端口两种。 物理端口:物理端口也被称为接口,是计算机主板上或其他设备上的硬件接口,如USB接口…...

SV学习笔记(一)

SV&#xff1a;SystemVerilog 开启SV之路 数据类型 內建数据类型 四状态与双状态 &#xff1a; 四状态指0、1、X、Z&#xff0c;包括logic、integer、 reg、 wire。双状态指0、1&#xff0c;包括bit、byte、 shortint、int、longint。 有符号与无符号 &#xff1a; 有符号&am…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

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

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

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...