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

java算法day43 | ● 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 | ● 1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

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

练气第六天

问:ANR怎么分析&#xff1f; ANR问题&#xff0c;这其实是一个非常综合性的问题&#xff0c;因为anr会涉及CPU负载&#xff0c;内存空间大小&#xff0c;线程锁&#xff0c;GC回收&#xff0c;这里面每个点&#xff0c;都是非常考验我们基本功的。 分析ANR问题&#xff0c;需…...

认识 Redis 与 分布式

Redis 官网页面 Redis官网链接 Redis 的简介 Redis 是一个在内存中存储数据的中间件 一方面用于作为数据库&#xff0c;另一方面用于作为数据缓存&#xff0c;适用于分布式系统中 Redis 基于网络&#xff0c;进行进程间通信&#xff0c;把自己内存中的变量给别的进程&#xf…...

Linux初学(十二)AWK进阶

一、AWK 1.1 简介 AWK是Linux中重要的文本处理工具Linux三剑客只一处理的对象可以是一个具体的文件&#xff0c;也可以是一个命令的执行结果AWK按行读取文件&#xff0c;将每一行视为一条记录 案例一&#xff1a;获取系统中每个用户的uid 方法一&#xff1a;cat /etc/passwd |…...

文字识别 Optical Character Recognition,OCR CTC STN

文字识别 Optical Character Recognition,OCR 自然场景文本检测识别技术综述 将图片上的文字内容,智能识别成为可编辑的文本。 场景文字识别(Scene Text Recognition,STR) OCR(Optical Character Recognition, 光学字符识别)传统上指对输入扫描文档图像进行分析处理,识…...

四、MySQL读写分离之MyCAT

一、读写分离概述 1、什么是读写分离&#xff1a; 读写分离&#xff1a;就是将读写操作分发到不同的服务器&#xff0c;读操作分发到对应的服务器 &#xff08;slave&#xff09;&#xff0c;写操作分发到对应的服务器&#xff08;master&#xff09; ① M-S (主从) 架构下&…...

通讯录项目实现

引言&#xff1a;通过顺序表的逻辑实现通讯录。这里就不讲关于顺序表的函数了。如果有不明白的可以看我写的顺序表的博客。 目录 顺序表与通讯录的比较 各源文件文件大榄 Contact.c中通讯录相关函数的定义 初始化和销毁通讯录 添加联系人&#xff1a; 删除联系人&#xf…...

xss相关知识点与绕过思路总结

前言 对xss的绕过进行了系统的学习与实践后&#xff0c;重新审视一下xss&#xff0c;对他的绕过进行一个总结。 &#xff08;当然我也是个小白&#xff0c;这些也是我当时瞎鸡儿乱搞绕过了几个xss自己做的小总结&#xff09; 可能有点丑陋&#xff0c;献丑了。 好博客推荐 …...

深入解析语言模型:原理、实战与评估

引言 随着人工智能的飞速发展&#xff0c;语言模型作为自然语言处理&#xff08;NLP&#xff09;的核心技术之一&#xff0c;日益受到业界的广泛关注。本文旨在深入探讨语言模型的原理、实战应用以及评估方法&#xff0c;帮助读者更好地理解和应用这一技术。 一、语言模型原理…...

Elasticsearch 的索引优化常规项

优化常规项 https://blog.csdn.net/bairo007/article/details/132019575 1、按实际情况适当调整主分片的数量 如果主分片数量太少&#xff0c;会导致每个分片中的数据量过大&#xff0c;而且无法利用集群中所有节点的计算资源。如果主分片数量太多&#xff0c;会导致索引过度…...

【JavaParser笔记01】JavaParser解析Java源代码中的类信息(javadoc注释、类​​​​​​​名称)

这篇文章,主要介绍如何使用JavaParser解析Java源代码中的类信息(javadoc注释、类名称)。 目录 一、JavaParser依赖库 1.1、引入依赖 1.2、获取类注释信息...

Stable Diffusion扩散模型【详解】小白也能看懂!!

文章目录 1、Diffusion的整体过程2、加噪过程2.1 加噪的具体细节2.2 加噪过程的公式推导 3、去噪过程3.1 图像概率分布 4、损失函数5、 伪代码过程 此文涉及公式推导&#xff0c;需要参考这篇文章&#xff1a; Stable Diffusion扩散模型推导公式的基础知识 1、Diffusion的整体…...

关于rabbitmq的prefetch机制

消息预取机制&#xff08;Prefetch Mechanism&#xff09;是RabbitMQ中用于控制消息传递给消费者的一种机制。它定义了在一个信道上&#xff0c;消费者允许的最大未确认的消息数量。一旦未确认的消息数量达到了设置的预取值&#xff0c;RabbitMQ就会停止向该消费者发送更多消息…...

机器学习介绍

机器学习是人工智能&#xff08;AI&#xff09;的一个分支&#xff0c;它使计算机系统能够从数据中学习并改进它们的性能。机器学习的核心在于开发算法&#xff0c;这些算法可以从大量数据中识别模式和特征&#xff0c;并用这些信息来做出预测或决策&#xff0c;而无需进行明确…...

OpenCV4.9开发之Window开发环境搭建

1.打开OpenCV所在github地址 2.点击opencv仓库,进入仓库详情,点击右下方的OpenCV 4.9.0进入下载页面 3.点击opencv-4.9.0-windows.exe下载 开始下载中... 下载完成 下载完成后,双击运行解压,默认解压路径,修改为c:/...

DDD 中的实体和值对象有什么区别?

在DDD中&#xff0c;实体 Entity 和值对象 Value Object 是两个基本的概念&#xff0c;它们之间有一些重要的区别。 唯一性&#xff1a;实体是唯一的&#xff0c;每个实体都有一个唯一的标识符&#xff0c;即使它的属性在一段时间内发生了变化&#xff0c;它仍然是这个实体。与…...

算法-最值问题

#include<iostream> using namespace std; int main() {int a[7];//上午上课时间int b[7];//下午上课时间int c[7];//一天总上课时间for (int i 0; i < 7; i) {cin >> a[i] >> b[i];c[i] a[i] b[i];}int max c[0];//max记录最长时间int index -1;//索…...

Go 性能压测工具之wrk介绍与使用

在项目正式上线之前&#xff0c;我们通常需要通过压测来评估当前系统能够支撑的请求量、排查可能存在的隐藏bug&#xff1b;压力测试&#xff08;压测&#xff09;是确保系统在高负载情况下仍能稳定运行的重要步骤。通过模拟高并发场景&#xff0c;可以评估系统的性能瓶颈、可靠…...

数学思想论(有目录)

数学思想是数学发展过程中的重要指导原则,它涉及对数学概念、方法和理论的理解和认识,以及如何利用这些工具来解决实际问题。数学思想的形成和演进是随着数学的发展而逐渐深化的,它体现了人类对数学本质和应用的不断探索和思考。 一些主要的数学思想包括: 函数与方程思想…...

C++的并发世界(五)——线程状态切换

0.线程状态 初始化&#xff1a;该线程正在被创建&#xff1b; 就绪&#xff1a;该线程在列表中就绪&#xff0c;等待CPU调度&#xff1b; 运行&#xff1a;该线程正在运行&#xff1b; 阻塞&#xff1a;该线程被阻塞挂机&#xff0c;Blocked状态包括&#xff1a;pend&#xff…...

使用 SciPy 求解零和博弈纳什均衡的正确建模与实现

...

实测MPU6050低功耗电流:从Sleep到Cycle模式,不同唤醒频率下功耗到底差多少?

MPU6050低功耗模式实测&#xff1a;从微安级电流到唤醒策略的硬件优化指南 当你的智能手环在手腕上安静沉睡时&#xff0c;MPU6050这颗运动传感器正在以微安级的电流维持着生命体征——这不是魔法&#xff0c;而是现代嵌入式设计中精妙的低功耗艺术。作为硬件工程师&#xff0c…...

【Leona】BoxId 是什么-设备指纹参数

BoxId 是什么&#xff1f;从 Leona.sense() 到 /v1/verdict 的可落地闭环&#xff1a;签名、落库、错误处理与回归验证&#xff08;基于公开示例&#xff09; TL;DR BoxId 不是“风险结论”&#xff0c;而是一次“证据报告兑换券”&#xff1a;端上拿 BoxId&#xff0c;后端换证…...

别再只盯着原理图了!用Python+OpenCV动手模拟激光三角测距(斜射/直射对比)

用PythonOpenCV模拟激光三角测距&#xff1a;斜射与直射的实战对比 激光三角测距技术听起来高大上&#xff0c;但真正理解它的精髓往往需要跳出公式推导的泥潭。作为一名长期在工业检测领域摸爬滚打的技术人员&#xff0c;我发现用代码模拟物理过程是最有效的学习方式。本文将…...

量子计算误差缓解技术解析与应用实践

1. 量子计算误差缓解技术概述 量子计算中的误差主要来源于量子比特与环境相互作用导致的退相干、量子门操作的不完美性以及测量误差。这些误差会随着量子电路深度的增加而累积&#xff0c;严重影响计算结果的可靠性。误差缓解技术旨在通过硬件和软件层面的方法&#xff0c;在不…...

从find到ind2sub:Matlab数据筛选后操作的完整工作流(以R2023b为例)

从find到ind2sub&#xff1a;Matlab数据筛选后操作的完整工作流&#xff08;以R2023b为例&#xff09; 在数据分析与科学计算领域&#xff0c;Matlab作为一款强大的工具&#xff0c;其矩阵操作能力尤为突出。面对大型矩阵或高维数组时&#xff0c;如何高效地定位并处理特定条件…...

D2DX终极指南:让《暗黑破坏神2》在现代PC上重获新生的Glide封装器

D2DX终极指南&#xff1a;让《暗黑破坏神2》在现代PC上重获新生的Glide封装器 【免费下载链接】d2dx D2DX is a complete solution to make Diablo II run well on modern PCs, with high fps and better resolutions. 项目地址: https://gitcode.com/gh_mirrors/d2/d2dx …...

【Sora 2×AE工作流革命】:20年特效总监亲授无缝整合5大黄金法则,错过再等三年?

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Sora 2AE工作流革命的底层逻辑与行业拐点 Sora 2AE&#xff08;Advanced Encoding&#xff09;并非简单升级&#xff0c;而是将扩散模型时序建模能力与自适应编码器深度耦合的范式重构。其核心突破在于…...

别再手动算归一化了!用Origin9.1的‘列公式’功能一键搞定数据预处理

用Origin9.1列公式功能高效实现数据归一化&#xff1a;从原理到实战 科研数据处理中&#xff0c;归一化是消除量纲影响、提升分析结果可比性的关键步骤。传统手动计算不仅耗时费力&#xff0c;还容易因公式输入错误导致结果偏差。Origin9.1的"列公式"功能&#xff08…...

JSON数据同步利器:深度解析ogre-software/json-synchronizer的核心原理与应用

1. 项目概述&#xff1a;一个被低估的JSON数据同步利器如果你经常和JSON数据打交道&#xff0c;尤其是在前后端分离、微服务架构或者多数据源集成的场景下&#xff0c;你肯定遇到过这样的烦恼&#xff1a;手头有两份甚至多份JSON数据&#xff0c;它们结构相似&#xff0c;但内容…...