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工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
测试markdown--肇兴
day1: 1、去程:7:04 --11:32高铁 高铁右转上售票大厅2楼,穿过候车厅下一楼,上大巴车 ¥10/人 **2、到达:**12点多到达寨子,买门票,美团/抖音:¥78人 3、中饭&a…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
