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

java算法day43 | 动态规划part05 ● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

1049. 最后一块石头的重量 II

在这里插入图片描述
在这里插入图片描述
核心思想: 尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。
是不是感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。那么分成两堆石头,一堆石头的总重量是dp[target],另一堆就是sum - dp[target]。

class Solution {public int lastStoneWeightII(int[] stones) {int sum=0;for(int i=0;i<stones.length;i++){sum+=stones[i];}int target=sum/2;int dp[]=new int[target+1];//1、定义dp数组 3、第一列初始化为0for(int i=0;i<stones.length;i++){for(int j=target;j>=stones[i];j--){//4、遍历顺序dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);//2.递推公式}}return sum-dp[target]-dp[target];//最终的返回结果}
}

时间复杂度:O(m × n) , m是石头总重量(准确的说是总重量的一半),n为石头块数
空间复杂度:O(m)

494. 目标和

在这里插入图片描述
在这里插入图片描述

思路: 这道题的dp数组的含义变了。具体看代码随想录的讲解

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)/2为整数的条件或target的绝对值大于sum的绝对值,直接返回0if((target+sum)%2!=0 || Math.abs(target)>Math.abs(sum)) return 0;int size=(target+sum)/2;int[] dp=new int[size+1];//1、定义dp数组,表示j容量时的表达式数目dp[0]=1;//3、初始化for(int i=0;i<nums.length;i++){for(int j=size;j>=nums[i];j--){//4、因为是01背包,所以反向遍历dp[j]=dp[j]+dp[j-nums[i]];//2、递推公式}}return dp[size];}
}

时间复杂度:O(n × m),n为正数个数,m为背包容量
空间复杂度:O(m),m为背包容量

474.一和零

在这里插入图片描述
思路: 这道题是一个二维的背包问题,和普通的背包相比只需要多一层对容量的循环。
在这里插入图片描述

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp=new int[m+1][n+1];//1、定义dp数组,表示当0的容量为x,1的容量为n时,最大子集的长度for(int i=0;i<strs.length;i++){//4、遍历顺序,物品正序遍历int weightm=0;int weightn=0;for(int j=0;j<strs[i].length();j++){if(strs[i].charAt(j)=='0') weightm++; else weightn++;}for(int x=m;x>=weightm;x--){//4、物品的空间占用逆序遍历for(int y=n;y>=weightn;y--){dp[x][y]=Math.max(dp[x][y],dp[x-weightm][y-weightn]+1);//2、递推公式,注意value是1}}}return dp[m][n];}
}

时间复杂度: O(kmn),k 为strs的长度
空间复杂度: O(mn)

相关文章:

java算法day43 | 动态规划part05 ● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

1049. 最后一块石头的重量 II 核心思想&#xff1a; 尽量让石头分成重量相同的两堆&#xff0c;相撞之后剩下的石头最小&#xff0c;这样就化解成01背包问题了。 是不是感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。那么分成两堆石头&#xff0c;一堆石头的…...

STM32无刷电机全套开发资料(源码、原理图、PCB工程及说明文档)

目录 1、原理图、PCB、BOOM表 2、设计描述 2.1 前言 2.2 设计电路规范 3、代码 4、资料清单 资料下载地址&#xff1a;STM32无刷电机全套开发资料(源码、原理图、PCB工程及说明文档) 1、原理图、PCB、BOOM表 2、设计描述 2.1 前言 经过一个星期的画PCB&#xff0c;今…...

工地安全监测识别摄像机

工地安全监测识别摄像机是一种在建筑工地和施工现场广泛使用的智能监控设备&#xff0c;主要用于监测施工过程中可能出现的安全隐患和违规行为&#xff0c;以确保工地人员和设备的安全。通过高清摄像头、智能算法和远程监控系统的结合&#xff0c;该摄像机可以实时监测工地各个…...

【零基础学数据结构】顺序表实现书籍存储

目录 书籍存储的实现规划 ​编辑 前置准备&#xff1a; 书籍结构体&#xff1a; 书籍展示的初始化和文件加载 书籍展示的销毁和文件保存 书籍展示的容量检查 书籍展示的尾插实现 书籍展示的书籍增加 书籍展示的书籍打印 书籍删除展示数据 书籍展示修改数据 在指定位置之前…...

【智能算法】黑寡妇优化算法(BWO)原理及实现

目录 1.背景2.算法原理2.1算法思想2.2算法过程 3.结果展示4.参考文献 1.背景 2020年&#xff0c;V Hayyolalam等人受到自然界黑寡妇交配行为启发&#xff0c;提出了黑寡妇优化算法&#xff08;Black Widow Optimization Agorithm, BWO&#xff09;。 2.算法原理 2.1算法思想…...

C#-非托管代码

非托管代码是指不受.NET运行时&#xff08;CLR&#xff09;的管理和控制&#xff0c;而是直接由操作系统或其他本机执行环境&#xff08;如C/C编译的代码&#xff09;所执行的代码。以下是一些常见的非托管代码的例子&#xff1a; C/C代码&#xff1a;通过使用C或C等编程语言编…...

计算机视觉之三维重建(7)---多视图几何(下)

文章目录 一、透视结构恢复问题1.1 概述1.2 透视结构恢复歧义1.3 代数方法1.4 捆绑调整 二、P3P问题三、随机采样一致性 一、透视结构恢复问题 1.1 概述 1. 透视结构恢复问题&#xff1a;摄像机为透视相机&#xff0c;内外参数均未知。 2. 问题&#xff1a;已知 n n n 个三维…...

AUTOSAR配置工具开发教程 - 开篇

简介 本系列的教程&#xff0c;主要讲述如何自己开发一套简单的AUTOSAR ECU配置工具。适用于有C# WPF基础的人员。 简易介绍见&#xff1a;如何打造AUTOSAR工具_autosar_mod_ecuconfigurationparameters-CSDN博客 实现版本 AUTOSAR 4.0.3AUTOSAR 4.2.2AUTOSAR 4.4.0 效果 …...

配置VM开机自启动

1. 在此电脑-右键选择“管理”-服务和应用程序-服务中找到VMware Workstation Server服务&#xff08;新版名称也可能是VMware自启动服务&#xff0c;自己找一下&#xff0c;服务属性里有描述信息的&#xff09;&#xff0c;将其启用并选择开机自动启动 新版参考官方文档&…...

工作的第四天

推荐一个软件分配软件 我们看一下如何使用 连接信息 AOC中国官方网站 发现打开 还是这个页面信息&#xff0c;发现最后出现了页面重新定向的问题 我服了 我的码 怎么解决 我想用这个软件 来看看这个软件下载就可以使用 一听到钱我使用的情绪不是很高了 算了不使用 使用…...

前端开发语言概览:从HTML、CSS到JavaScript

随着互联网的发展&#xff0c;前端开发领域涌现出了许多不同的编程语言和技术&#xff0c;用于构建各种类型的网页和应用程序。本文将介绍几种主流的前端开发语言&#xff0c;包括 HTML、CSS 和 JavaScript&#xff0c;并简要讨论它们在前端开发中的作用和特点。 1. HTML&…...

《Java面试自救指南》(专题二)计算机网络

文章目录 力推的计网神课get请求和post请求的区别在浏览器网址输入一个url后直到浏览器显示页面的过程常用状态码session 和 cookie的区别TCP的三次握手和四次挥手七层OSI模型&#xff08;TCP/IP协议模型&#xff09;各种io模型的知识http协议和tcp协议的区别https和http的区别…...

Android14音频进阶之<进阶调试>:Perfetto定位系统音频问题(六十六)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒体系统工程师系列【原创干货持续更新中……】🚀 优质视频课程:AAOS车载系统+AOSP…...

使用 Clickhouse 集成的表引擎同步数据方式详解

Clickhouse作为一个列式存储分析型数据库&#xff0c;提供了很多集成其他组件的表引擎数据同步方案。 官网介绍 一 Kafka 表引擎 使用Clickhouse集成的Kafka表引擎消费Kafka写入Clickhouse表中。 1.1 流程图 1.2 建表 根据上面的流程图需要建立三张表&#xff0c;分别Click…...

Linux 性能分析工具大全

vmstat--虚拟内存统计 vmstat&#xff08;VirtualMeomoryStatistics&#xff0c;虚拟内存统计&#xff09;是 Linux 中监控内存的常用工具,可对操作系统的虚拟内存、进程、CPU 等的整体情况进行监视。vmstat 的常规用法&#xff1a;vmstat interval times 即每隔 interval 秒采…...

FME学习之旅---day21

我们付出一些成本&#xff0c;时间的或者其他&#xff0c;最终总能收获一些什么。 教程&#xff1a;AutoCAD 变换 相关的文章 为您的 DWG 赋予一些样式&#xff1a;使用 DWGStyler、模板文件、块等 FME数据检查器在显示行的方式上受到限制。它只能显示线条颜色&#xff0c;而…...

volta(轻松切换管理Node.js版本)

Node.js版本管理 Volta提供了一个简单直观的命令行界面&#xff0c;可以轻松地安装、卸载、更新和切换Node.js版本。 Volta 既可以全局使用&#xff0c;也可以在项目级别使用&#xff0c;可以为每个项目单独设置node版本&#xff0c;nvm不行。 下载安装Volta 参考&#xff1a; …...

机器学习知识点

1鸢尾花分类 鸢尾花分类问题是一个经典的机器学习问题&#xff0c;旨在根据鸢尾花的花萼长度、花萼宽度、花瓣长度和花瓣宽度等特征&#xff0c;将鸢尾花分成三个品种&#xff1a;山鸢尾&#xff08;setosa&#xff09;、变色鸢尾&#xff08;versicolor&#xff09;和维吉尼亚…...

SQL注入利用学习-Union联合注入

联合注入的原理 在SQL语句中查询数据时&#xff0c;使用select 相关语句与where 条件子句筛选符合条件的记录。 select * from person where id 1; #在person表中&#xff0c;筛选出id1的记录如果该id1 中的1 是用户可以控制输入的部分时&#xff0c;就有可能存在SQL注入漏洞…...

zookeeper源码(12)命令行客户端

zkCli.sh脚本 这个命令行脚本在bin目录下&#xff1a; ZOOBIN"${BASH_SOURCE-$0}" ZOOBIN"$(dirname "${ZOOBIN}")" ZOOBINDIR"$(cd "${ZOOBIN}"; pwd)"# 加载zkEnv.sh脚本 if [ -e "$ZOOBIN/../libexec/zkEnv.sh&qu…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

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

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

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

Typeerror: cannot read properties of undefined (reading ‘XXX‘)

最近需要在离线机器上运行软件&#xff0c;所以得把软件用docker打包起来&#xff0c;大部分功能都没问题&#xff0c;出了一个奇怪的事情。同样的代码&#xff0c;在本机上用vscode可以运行起来&#xff0c;但是打包之后在docker里出现了问题。使用的是dialog组件&#xff0c;…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

论文阅读:Matting by Generation

今天介绍一篇关于 matting 抠图的文章&#xff0c;抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法&#xff0c;已经有很多的工作和这个任务相关。这两年 diffusion 模型很火&#xff0c;大家又开始用 diffusion 模型做各种 CV 任务了&am…...

数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)

目录 &#x1f50d; 若用递归计算每一项&#xff0c;会发生什么&#xff1f; Horners Rule&#xff08;霍纳法则&#xff09; 第一步&#xff1a;我们从最原始的泰勒公式出发 第二步&#xff1a;从形式上重新观察展开式 &#x1f31f; 第三步&#xff1a;引出霍纳法则&…...