代码随想录day42
1049. 最后一块石头的重量 II
https://leetcode.cn/problems/last-stone-weight-ii/
这个自己还是没想出来01背包对应。
本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。
stones = [2,7,4,1,8,1]也就是sum=23,2+7+1+1=11,4+8=12,差值为1。
class Solution {public int lastStoneWeightII(int[] stones) {int sum=0;for(int i=0;i<stones.length;i++){sum+=stones[i];}int[] dp=new int[sum/2+1];for(int i=0;i<stones.length;i++){for(int j=sum/2;j>=stones[i];j--){dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);}}return sum-2*dp[sum/2];}
}
494. 目标和
https://leetcode.cn/problems/target-sum/
这个更难想到怎么和01背包问题结合了,target是一个差值,但±怎么判定呢。
x-(sum-x)=target;——>x=(target+sum)/2;
这个真的好难理解啊
dp[j] += dp[j - nums[i]];
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int i = 0; i < nums.length; i++) sum += nums[i];//如果target过大 sum将无法满足if ( target < 0 && sum < -target) return 0;if ((target + sum) % 2 != 0) return 0;int size = (target + sum) / 2;if(size < 0) size = -size;int[] dp = new int[size + 1];dp[0] = 1;for (int i = 0; i < nums.length; i++) {for (int j = size; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[size];}
}
474. 一和零
https://leetcode.cn/problems/ones-and-zeroes/
这个也很难想到。
将m和n作为背包容量定义二维数组。
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp=new int[m+1][n+1];int x,y;for(str:strs){x=y=0;for(char ch : str.toCharArray()){if(ch=='0'){x++;}else{y++;}}for (int i = m; i >= x; i--) {for (int j = n; j >= y; j--) {dp[i][j] = Math.max(dp[i][j], dp[i - x][j - y] + 1);}}}return dp[m][n];}
}
相关文章:
代码随想录day42
1049. 最后一块石头的重量 II https://leetcode.cn/problems/last-stone-weight-ii/ 这个自己还是没想出来01背包对应。 本题其实就是尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。 stones [2,7,4,1,8,1]也就是sum…...
【笔记】两台1200PLC进行S7 通信(1)
使用两台1200系列PLC进行S7通信(入门) 文章目录 目录 文章目录 前言 一、通信 1.概念 2.PLC通信 1.串口 2.网口 …...
统一网关Gateway
为什么需要网关 网关功能: 身份认证和权限校验服务路由,负载均衡 根据请求判断找到对应的服务路由,然后服务可能有多个实例,这个时候网关就会做一个负载均衡去挑选一个实例调用.请求限流 限制请求的数量,这是微服务的…...
6、kubernetes(k8s)安装
本文内容以语雀为准 文档 等等,Docker 被 Kubernetes 弃用了?容器运行时端口和协议kubeadm initkubeadm config安装网络策略驱动使用 kubeadm 创建集群 控制平面节点隔离 持久卷为容器设置环境变量在CentOS上安装Docker引擎Pod 网络无法访问排查处理 说明 本文…...
python-批量下载某短视频平台音视频标题、评论、点赞数
python-批量下载某短视频平台音视频标题、评论数、点赞数前言一、获取单个视频信息1、获取视频 url2、发送请求3、数据解析二、批量获取数据1、批量导入地址2、批量导出excel文件3、批量存入mysql数据库三、完整代码前言 1、Cookie中文名称为小型文本文件,指某些网…...
【数据结构与算法】单链表的增删查改(附源码)
这么可爱的猫猫不值得点个赞吗😽😻 目录 一.链表的概念和结构 二.单链表的逻辑结构和物理结构 1.逻辑结构 2.物理结构 三.结构体的定义 四.增加 1.尾插 SListpushback 2.头插 SListpushfront 五.删除 1.尾删 SListpopback 2.头删 SListpo…...
华为OD机试 - 回文字符串
题目描述 如果一个字符串正读和反渎都一样(大小写敏感),则称它为一个「回文串」,例如: leVel是一个「回文串」,因为它的正读和反读都是leVel;同理a也是「回文串」art不是一个「回文串」,因为它的反读tra与正读不同Level不是一个「回文串」,因为它的反读leveL与正读不…...
C语言太简单?这14道C语言谜题,你能答对几个
14个C语言的迷题以及答案,代码应该是足够清楚的,而且有相当的一些例子可能是我们日常工作可能会见得到的。通过这些迷题,希望你能更了解C语言。 如果你不看答案,不知道是否有把握回答各个谜题?让我们来试试。 下面的…...
Benchmark测试——fio——源码分析
1. main 1.1 parse_options() 解析选项,更新数据结构 1.1.1 fio_init_options() 1.1.2 fio_test_cconv(&def_thread.o) <cconv.c> 1.1.2.1 convert_thread_options_to_cpu() 传递options给数据结构 1.1.3 parse_cmd_line() switch语句多路选择&am…...
测量 R 代码运行时间的 5 种方法
简介 平常在撰写论文时,会需要比较算法之间的计算时间。本篇文章给出几种测量 R 代码运行时间的方法。本文是小编学习过程中的笔记,主要参考博客1,2。 1. 使用 Sys.time() 小编通常使用 Sys.time() 函数来计算时间。首先记录当前运行时刻&…...
Qt 第9课、计算器中缀转后缀算法
计算器核心算法: 1、将中缀表达式进行数字和运算符的分离 2、将中缀表达式转换成后缀表达式 3、通过后缀表达式计算最后的结果 二、计算器中缀转后缀算法 计算器中缀转后缀算法的意义在于把中缀表达式转换成后缀表达式,能够更好地计算 算法的基本思路…...
docker的使用方法
docker技术 同一个操作系统内跑多套不同版本依赖的业务 docker可以使同一个物理机中进程空间,网络空间,文件系统空间相互隔绝 虚拟机弊端:每个需要安装操作系统,太重量级,资源需要提前分配好 部署程序 开发环境 win…...
Kafka(五)生产者向发送消息的执行流程
(1)生产者要往 Kafka 发送消息时,需要创建 ProducerRecoder,代码如下: ProducerRecord<String,String> record new ProducerRecoder<>("CostomerCountry","Precision Products","France&q…...
华为OD机试模拟题 用 C++ 实现 - 简易压缩算法(2023.Q1)
最近更新的博客 【华为OD机试模拟题】用 C++ 实现 - 最多获得的短信条数(2023.Q1)) 文章目录 最近更新的博客使用说明简易压缩算法题目输入输出示例一输入输出说明示例二输入输出说明示例三输入输出说明...
MATLAB R2022b 安装教程
MATLAB R2022b 安装教程MathWorks 于2022年9月发布了 MATLAB 和 Simulink 产品系列的最新版本 Matlab R2022b版本 ,加入两个新产品: Medical Imaging Toolbox — 可视化、配准、分割和标注二维及三维医学图像Simscape Battery — 设计和仿真电池和储能系…...
PCI子系统
很多网络接口卡都是外围组件互联(Peripheral Compaonent Interconnect)设备,必须与Linux PCI子系统协同工作,并非所有的网络接口都是PCI设备,很多嵌入式设备的网络接口连接的就不是PCI总线,这些设备的初始化…...
Spring源码之IoC容器的Bean创建和依赖注入,DefaultListableBeanFactory容器为例
接上篇Spring源码之IoC容器初始化过程,以FileSystemXmlApplicationContext容器为例 因为FileSystemXmlApplicationContext使用的容器为DefaultListableBeanFactory,所以该篇基于DefaultListableBeanFactory的实现分析依赖注入过程。 目录获取Bean的总体流…...
解决小程序页面scroll-view块自身滑动问题
修改scroll-view的style样式 本来通过函数限制高度 style"margin-top:200rpx;"height: calc(100vh - 200rpx - env(safe-area-inset-bottom));会出现整个scroll-view块位置不固定滑动里面的内容后,自己本身在整个页面内上移,将样式改为&#…...
PowerCommand康明斯发电机控制屏维修HMI211
康明斯柴油发电机的监控系统分为普通机组控制屏和智能化机组控制界面。普通操作界面实用于普通的康明斯柴油发电机的控制,康明斯柴油发电机的起动与停止、供电与断电、状态调整等均由手动操作;自动化康明斯柴油发电机控制系统适合于智能化康明斯柴油发电…...
ELK + Kafka 测试
配置file beat输出到 Kafkalogstash服务器从kafka获取数据并输出到es集群在es集群上查看索引kibana界面添加索引查看数据1.配置file beat输出到 Kafka 1.1 Filebeat机器配置数据采集和输出目标 做好域名解析 # vim /usr/local/filebeat/filebeat.yml # 修改输出目标为kafka…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
Python学习(8) ----- Python的类与对象
Python 中的类(Class)与对象(Object)是面向对象编程(OOP)的核心。我们可以通过“类是模板,对象是实例”来理解它们的关系。 🧱 一句话理解: 类就像“图纸”,对…...
动态规划-1035.不相交的线-力扣(LeetCode)
一、题目解析 光看题目要求和例图,感觉这题好麻烦,直线不能相交啊,每个数字只属于一条连线啊等等,但我们结合题目所给的信息和例图的内容,这不就是最长公共子序列吗?,我们把最长公共子序列连线起…...
Python第七周作业
Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt,并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径,并创建logs目录(若不存在) 3.递归遍历目录data,输出所有.csv文件的路径…...
零基础在实践中学习网络安全-皮卡丘靶场(第十一期-目录遍历模块)
经过前面几期的内容我们学习了很多网络安全的知识,而这期内容就涉及到了前面的第六期-RCE模块,第七期-File inclusion模块,第八期-Unsafe Filedownload模块。 什么是"遍历"呢:对学过一些开发语言的朋友来说应该知道&…...
