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

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 本题中&#xff0c;石头的重量是 stones[i]&#xff0c;石头的价值也是 stones[i] &#xff0c;可以 “最多可以装的价值为 dp[j]” “最多可以背的重量为dp[j]” dp[j] max(dp[j], dp[j - stones[i]] stones[i]); 最后dp[target]里是…...

服务器安全需要注意的几个方面?

服务器安全需要注意的几个方面&#xff1f; 服务器的核心技术相对复杂&#xff0c;专业人员稀少&#xff0c;尤其在病毒技术快速更新迭代的前提下&#xff0c;安全问题更为突出。这里提供一些实际工作中总结出的安全防护经验&#xff0c;以供参考。 一&#xff0c;增强网络整…...

Mysql数据库第十三课-----------sql语句的拔高3--------直冲云霄

作者前言 &#x1f382; ✨✨✨✨✨✨&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f382; ​&#x1f382; 作者介绍&#xff1a; &#x1f382;&#x1f382; &#x1f382; &#x1f389;&#x1f389;&#x1f389…...

计算机网络-物理层(一)物理层的概念与传输媒体

计算机网络-物理层&#xff08;一&#xff09;物理层的概念与传输媒体 物理层相关概念 物理层的作用用来解决在各种传输媒体上传输比特0和1的问题&#xff0c;进而为数据链路层提供透明(看不见)传输比特流的服务物理层为数据链路层屏蔽了各种传输媒体的差异&#xff0c;使数据…...

差分升级在物联网水表上的实现与应用(学习)

摘要 当越来越多的物联网水表加入抄表系统后&#xff0c;实现了水表数据的信息化&#xff0c;并且当水表终端需要技术更新时&#xff0c;通过网络方式来升级产品可以高效修复设备面临的问题&#xff0c;减少用户损失&#xff0c;降低维护成本&#xff0c;但同时也对有限的网络…...

ubuntu磁盘管理

show partition information 挂载设备在这 显示文件系统信息 build file system mkfs -t ext4 /dev/nvme0n1p4命令作用&#xff1a;将/dev/nvme0n1p4 格式化为 ext4 建立交换分区 mkswap -c -v1 /dev/nvme0n1p4 102400-c&#xff1a;check -v1&#xff1a;新版交换分区 -v0&…...

前端处理后端返回的数据中有\n\n字样的换行符标识

后端返回的数据&#xff1a; 上面圈着的部分就是\n&#xff0c;前端需要将数据进行换行&#xff0c;对于这类型的数据&#xff0c;在前端页面是需要进行稍微处理才能正常显示。如果没有经过处理&#xff0c;那么内容是不会在有换行符的位置进行换行显示的 解决办法1&#xff1…...

matlab解常微分方程常用数值解法2:龙格库塔方法

总结和记录一下matlab求解常微分方程常用的数值解法&#xff0c;本文将介绍龙格库塔方法&#xff08;Runge-Kutta Method&#xff09;。 龙格库塔迭代的基本思想是&#xff1a; x k 1 x k a k 1 b k 2 x_{k1}x_{k}a k_{1}b k_{2} xk1​xk​ak1​bk2​ k 1 h f ( x k , t …...

数据结构-栈(C语言简单实现)

简介 栈是一种数据结构栈可以用来存放数字一次只能向栈里加入一个数字&#xff0c;一次也只能从栈里获得一个数字栈里到的数字有前后顺序&#xff0c;先进入到的数字在前&#xff0c;后进入的数字在后每次从栈里获取的数字一定是最后面的数字&#xff0c;最后获取的数字一定是…...

山东布谷科技直播软件源码探索高效、稳定直播传输的技术介绍:流媒体传输技术

今天我们探索的是让直播软件源码平台在直播时能够高效、稳定的进行直播传输的技术&#xff0c;而这个技术就是直播软件源码平台的流媒体传输技术&#xff0c;在直播软件源码平台中&#xff0c;流媒体传输技术会将直播的图像、视频、音频等相关的流媒体信号通过网络传递到用户的…...

LeetCode 热题 100 JavaScript -- 74. 搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵&#xff1a; 每行中的整数从左到右按非递减顺序排列。 每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target &#xff0c;如果 target 在矩阵中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 …...

任我行 CRM SQL注入漏洞复现(HW0day)

0x01 产品简介 任我行CRM&#xff08;Customer Relationship Management&#xff09;是一款专业的企业级CRM软件&#xff0c;旨在帮助企业有效管理客户关系、提升销售效率和提供个性化的客户服务。 0x02 漏洞概述 任我行 CRM SmsDataList 接口处存在SQL注入漏洞&#xff0c;未…...

[CKA]考试之集群故障排查 – kubelet故障

由于最新的CKA考试改版&#xff0c;不允许存储书签&#xff0c;本博客致力怎么一步步从官网把答案找到&#xff0c;如何修改把题做对&#xff0c;下面开始我们的 CKA之旅 题目为&#xff1a; Task 一个名为wk8s-node-0的节点状态为NotReady&#xff0c;让其他恢复至正常状态…...

VBA技术资料MF42:VBA_从Excel中上面的单元格复制公式

【分享成果&#xff0c;随喜正能量】唯有梦想才配让你不安&#xff0c;唯有行动才能解除你的不安.绳锯木断&#xff0c;水滴石穿。也许你现在做的事情很小&#xff0c;只要你能日积月累的坚持下去&#xff0c;才会发现意义非凡。所谓的成功&#xff0c;便是别人失败的时候你还在…...

ORB-SLAM2第一节---单目地图初始化

单目初始化 1.前提条件&#xff08;640*480&#xff09; 参与初始化的两帧各自的特征点数目都需要大于100.两帧特征点成功匹配的数目需要大于或等于100.两帧特征点三角化成功的三维点数目需要大于50. 2.针对条件三 流程如下 记录当前帧和参考帧&#xff08;第一帧&#xff…...

Postman 汉化及下载

Postman 是一款常用的 API 测试工具&#xff0c;可以方便地进行接口测试、调试和文档编写。本文将详细介绍如何下载安装 Postman 并汉化&#xff0c;包括每个步骤的详细说明。 下载安装 Postman 1、打开浏览器&#xff0c;访问 Postman 官网&#xff0c;下载适用于自己系统的…...

【运维】Zabbix简介及其应用领域

文章目录 1. Zabbix的背景与起源1.1. 监控工具的重要性为什么企业和个人需要监控工具&#xff1f;常见的监控挑战与需求 1.2. Zabbix的诞生背景Zabbix的发展历程Zabbix与其他监控工具的对比 2. Zabbix的核心功能2.1. 数据收集支持的数据收集方法数据的存储与历史记录 2.2. 可视…...

vue 设置了表单验证的el-input,在触发验证后无法继续输入的问题解决

问题表现 在项目中碰到的问题&#xff0c;说是input框出现验证提示后&#xff0c;该框就无法输入新的数据了 下面是我的代码&#xff1a; // dom结构 <el-form ref"addForm" :rules"addFormRules" :model"addForm" label-width"100px&…...

基于smardaten无代码开发智能巡检系统,让无人机飞得更准

目录 引言需求背景搭建思路开发过程&#xff08;1&#xff09;无人机设备数据接入&#xff08;2&#xff09;无人机巡检任务管理&#xff08;3&#xff09;无人机三维防控监视&#xff08;4&#xff09;运防一体化大屏设计&#xff08;5&#xff09;异常告警管理&#xff08;6&…...

51项目——智能垃圾桶

51项目——智能垃圾桶 文章目录 51项目——智能垃圾桶项目需求项目材料(实物图可以百度看一看)接线实战编写部分代码(需要打包好的代码可以私我)效果视频结束项目需求 人靠近,垃圾桶开盖,投放垃圾,人离开,垃圾桶自动关盖。 并屏幕显示距离,和垃圾桶开关的状态。 项目材…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...