当前位置: 首页 > 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…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

SQL慢可能是触发了ring buffer

简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...

深入理解Optional:处理空指针异常

1. 使用Optional处理可能为空的集合 在Java开发中&#xff0c;集合判空是一个常见但容易出错的场景。传统方式虽然可行&#xff0c;但存在一些潜在问题&#xff1a; // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...