Day 43
Day 43
1049.最后一块石头的重量II
本题中,石头的重量是 stones[i],石头的价值也是 stones[i] ,可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
最后dp[target]里是容量为target的背包所能背的最大重量。
那么分成两堆石头,一堆石头的总重量是dp[target],另一堆就是sum - dp[target]。
在计算target的时候,target = sum / 2 因为是向下取整,所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。
class Solution:def lastStoneWeightII(self, stones: List[int]) -> int:dp = [0] * 15001total = sum(stones)target = total // 2for stone in stones:for j in range(target, stone - 1, -1):dp[j] = max(dp[j], dp[j - stone] + stone)return total - dp[target] - dp[target]
class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int i : stones) {sum += i;}int target = sum >> 1;//初始化dp数组int[] dp = new int[target + 1];for (int i = 0; i < stones.length; i++) {//采用倒序for (int j = target; j >= stones[i]; j--) {//两种情况,要么放,要么不放dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - 2 * dp[target];}
}
494.目标和
本题要如何使表达式结果为target,
既然为target,那么就一定有 left组合 - right组合 = target。
left + right = sum,而sum是固定的。right = sum - left
公式来了, left - (sum - left) = target 推导出 left = (target + sum)/2 。
target是固定的,sum是固定的,left就可以求出来。
此时问题就是在集合nums中找出和为left的组合。
此时问题就转化为,装满容量为x的背包,有几种方法。
dp[j] 表示:填满j(包括j)这么大容积的包,有dp[j]种方法
只要搞到nums[i],凑成dp[j]就有dp[j - nums[i]] 种方法。
例如:dp[j],j 为5,
- 已经有一个1(nums[i]) 的话,有 dp[4]种方法 凑成 容量为5的背包。
- 已经有一个2(nums[i]) 的话,有 dp[3]种方法 凑成 容量为5的背包。
- 已经有一个3(nums[i]) 的话,有 dp[2]中方法 凑成 容量为5的背包
- 已经有一个4(nums[i]) 的话,有 dp[1]中方法 凑成 容量为5的背包
- 已经有一个5 (nums[i])的话,有 dp[0]中方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢,也就是把 所有的 dp[j - nums[i]] 累加起来。
dp[j] += dp[j - nums[i]]
class Solution:def findTargetSumWays(self, nums: List[int], target: int) -> int:total = sum(nums)if abs(target) > total:return 0if (target + total) % 2 == 1:return 0tar_sum = (target + total) // 2dp = [0] * (tar_sum + 1)dp[0] = 1for num in nums:for j in range(tar_sum, num - 1, -1):dp[j] += dp[j - num]return dp[tar_sum]
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.一和零
class Solution:def findMaxForm(self, strs: List[str], m: int, n: int) -> int:dp = [[0] * (n + 1) for _ in range(m + 1)]for s in strs:zeronum = s.count('0')onenum = s.count('1')for i in range(m, zeronum - 1, -1):for j in range(n, onenum - 1, -1):dp[i][j] = max(dp[i][j], dp[i - zeronum][j - onenum] + 1)return dp[m][n]
相关文章:
Day 43
Day 43 1049.最后一块石头的重量II 本题中,石头的重量是 stones[i],石头的价值也是 stones[i] ,可以 “最多可以装的价值为 dp[j]” “最多可以背的重量为dp[j]” dp[j] max(dp[j], dp[j - stones[i]] stones[i]); 最后dp[target]里是…...
服务器安全需要注意的几个方面?
服务器安全需要注意的几个方面? 服务器的核心技术相对复杂,专业人员稀少,尤其在病毒技术快速更新迭代的前提下,安全问题更为突出。这里提供一些实际工作中总结出的安全防护经验,以供参考。 一,增强网络整…...
Mysql数据库第十三课-----------sql语句的拔高3--------直冲云霄
作者前言 🎂 ✨✨✨✨✨✨🍧🍧🍧🍧🍧🍧🍧🎂 🎂 作者介绍: 🎂🎂 🎂 🎉🎉🎉…...
计算机网络-物理层(一)物理层的概念与传输媒体
计算机网络-物理层(一)物理层的概念与传输媒体 物理层相关概念 物理层的作用用来解决在各种传输媒体上传输比特0和1的问题,进而为数据链路层提供透明(看不见)传输比特流的服务物理层为数据链路层屏蔽了各种传输媒体的差异,使数据…...
差分升级在物联网水表上的实现与应用(学习)
摘要 当越来越多的物联网水表加入抄表系统后,实现了水表数据的信息化,并且当水表终端需要技术更新时,通过网络方式来升级产品可以高效修复设备面临的问题,减少用户损失,降低维护成本,但同时也对有限的网络…...
ubuntu磁盘管理
show partition information 挂载设备在这 显示文件系统信息 build file system mkfs -t ext4 /dev/nvme0n1p4命令作用:将/dev/nvme0n1p4 格式化为 ext4 建立交换分区 mkswap -c -v1 /dev/nvme0n1p4 102400-c:check -v1:新版交换分区 -v0&…...
前端处理后端返回的数据中有\n\n字样的换行符标识
后端返回的数据: 上面圈着的部分就是\n,前端需要将数据进行换行,对于这类型的数据,在前端页面是需要进行稍微处理才能正常显示。如果没有经过处理,那么内容是不会在有换行符的位置进行换行显示的 解决办法1࿱…...
matlab解常微分方程常用数值解法2:龙格库塔方法
总结和记录一下matlab求解常微分方程常用的数值解法,本文将介绍龙格库塔方法(Runge-Kutta Method)。 龙格库塔迭代的基本思想是: x k 1 x k a k 1 b k 2 x_{k1}x_{k}a k_{1}b k_{2} xk1xkak1bk2 k 1 h f ( x k , t …...
数据结构-栈(C语言简单实现)
简介 栈是一种数据结构栈可以用来存放数字一次只能向栈里加入一个数字,一次也只能从栈里获得一个数字栈里到的数字有前后顺序,先进入到的数字在前,后进入的数字在后每次从栈里获取的数字一定是最后面的数字,最后获取的数字一定是…...
山东布谷科技直播软件源码探索高效、稳定直播传输的技术介绍:流媒体传输技术
今天我们探索的是让直播软件源码平台在直播时能够高效、稳定的进行直播传输的技术,而这个技术就是直播软件源码平台的流媒体传输技术,在直播软件源码平台中,流媒体传输技术会将直播的图像、视频、音频等相关的流媒体信号通过网络传递到用户的…...
LeetCode 热题 100 JavaScript -- 74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵: 每行中的整数从左到右按非递减顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。 …...
任我行 CRM SQL注入漏洞复现(HW0day)
0x01 产品简介 任我行CRM(Customer Relationship Management)是一款专业的企业级CRM软件,旨在帮助企业有效管理客户关系、提升销售效率和提供个性化的客户服务。 0x02 漏洞概述 任我行 CRM SmsDataList 接口处存在SQL注入漏洞,未…...
[CKA]考试之集群故障排查 – kubelet故障
由于最新的CKA考试改版,不允许存储书签,本博客致力怎么一步步从官网把答案找到,如何修改把题做对,下面开始我们的 CKA之旅 题目为: Task 一个名为wk8s-node-0的节点状态为NotReady,让其他恢复至正常状态…...
VBA技术资料MF42:VBA_从Excel中上面的单元格复制公式
【分享成果,随喜正能量】唯有梦想才配让你不安,唯有行动才能解除你的不安.绳锯木断,水滴石穿。也许你现在做的事情很小,只要你能日积月累的坚持下去,才会发现意义非凡。所谓的成功,便是别人失败的时候你还在…...
ORB-SLAM2第一节---单目地图初始化
单目初始化 1.前提条件(640*480) 参与初始化的两帧各自的特征点数目都需要大于100.两帧特征点成功匹配的数目需要大于或等于100.两帧特征点三角化成功的三维点数目需要大于50. 2.针对条件三 流程如下 记录当前帧和参考帧(第一帧ÿ…...
Postman 汉化及下载
Postman 是一款常用的 API 测试工具,可以方便地进行接口测试、调试和文档编写。本文将详细介绍如何下载安装 Postman 并汉化,包括每个步骤的详细说明。 下载安装 Postman 1、打开浏览器,访问 Postman 官网,下载适用于自己系统的…...
【运维】Zabbix简介及其应用领域
文章目录 1. Zabbix的背景与起源1.1. 监控工具的重要性为什么企业和个人需要监控工具?常见的监控挑战与需求 1.2. Zabbix的诞生背景Zabbix的发展历程Zabbix与其他监控工具的对比 2. Zabbix的核心功能2.1. 数据收集支持的数据收集方法数据的存储与历史记录 2.2. 可视…...
vue 设置了表单验证的el-input,在触发验证后无法继续输入的问题解决
问题表现 在项目中碰到的问题,说是input框出现验证提示后,该框就无法输入新的数据了 下面是我的代码: // dom结构 <el-form ref"addForm" :rules"addFormRules" :model"addForm" label-width"100px&…...
基于smardaten无代码开发智能巡检系统,让无人机飞得更准
目录 引言需求背景搭建思路开发过程(1)无人机设备数据接入(2)无人机巡检任务管理(3)无人机三维防控监视(4)运防一体化大屏设计(5)异常告警管理(6&…...
51项目——智能垃圾桶
51项目——智能垃圾桶 文章目录 51项目——智能垃圾桶项目需求项目材料(实物图可以百度看一看)接线实战编写部分代码(需要打包好的代码可以私我)效果视频结束项目需求 人靠近,垃圾桶开盖,投放垃圾,人离开,垃圾桶自动关盖。 并屏幕显示距离,和垃圾桶开关的状态。 项目材…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
