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 核心思想: 尽量让石头分成重量相同的两堆,相撞之后剩下的石头最小,这样就化解成01背包问题了。 是不是感觉和昨天讲解的416. 分割等和子集 (opens new window)非常像了。那么分成两堆石头,一堆石头的…...
练气第六天
问:ANR怎么分析? ANR问题,这其实是一个非常综合性的问题,因为anr会涉及CPU负载,内存空间大小,线程锁,GC回收,这里面每个点,都是非常考验我们基本功的。 分析ANR问题,需…...
认识 Redis 与 分布式
Redis 官网页面 Redis官网链接 Redis 的简介 Redis 是一个在内存中存储数据的中间件 一方面用于作为数据库,另一方面用于作为数据缓存,适用于分布式系统中 Redis 基于网络,进行进程间通信,把自己内存中的变量给别的进程…...
Linux初学(十二)AWK进阶
一、AWK 1.1 简介 AWK是Linux中重要的文本处理工具Linux三剑客只一处理的对象可以是一个具体的文件,也可以是一个命令的执行结果AWK按行读取文件,将每一行视为一条记录 案例一:获取系统中每个用户的uid 方法一:cat /etc/passwd |…...
文字识别 Optical Character Recognition,OCR CTC STN
文字识别 Optical Character Recognition,OCR 自然场景文本检测识别技术综述 将图片上的文字内容,智能识别成为可编辑的文本。 场景文字识别(Scene Text Recognition,STR) OCR(Optical Character Recognition, 光学字符识别)传统上指对输入扫描文档图像进行分析处理,识…...
四、MySQL读写分离之MyCAT
一、读写分离概述 1、什么是读写分离: 读写分离:就是将读写操作分发到不同的服务器,读操作分发到对应的服务器 (slave),写操作分发到对应的服务器(master) ① M-S (主从) 架构下&…...
通讯录项目实现
引言:通过顺序表的逻辑实现通讯录。这里就不讲关于顺序表的函数了。如果有不明白的可以看我写的顺序表的博客。 目录 顺序表与通讯录的比较 各源文件文件大榄 Contact.c中通讯录相关函数的定义 初始化和销毁通讯录 添加联系人: 删除联系人…...
xss相关知识点与绕过思路总结
前言 对xss的绕过进行了系统的学习与实践后,重新审视一下xss,对他的绕过进行一个总结。 (当然我也是个小白,这些也是我当时瞎鸡儿乱搞绕过了几个xss自己做的小总结) 可能有点丑陋,献丑了。 好博客推荐 …...
深入解析语言模型:原理、实战与评估
引言 随着人工智能的飞速发展,语言模型作为自然语言处理(NLP)的核心技术之一,日益受到业界的广泛关注。本文旨在深入探讨语言模型的原理、实战应用以及评估方法,帮助读者更好地理解和应用这一技术。 一、语言模型原理…...
Elasticsearch 的索引优化常规项
优化常规项 https://blog.csdn.net/bairo007/article/details/132019575 1、按实际情况适当调整主分片的数量 如果主分片数量太少,会导致每个分片中的数据量过大,而且无法利用集群中所有节点的计算资源。如果主分片数量太多,会导致索引过度…...
【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、 伪代码过程 此文涉及公式推导,需要参考这篇文章: Stable Diffusion扩散模型推导公式的基础知识 1、Diffusion的整体…...
关于rabbitmq的prefetch机制
消息预取机制(Prefetch Mechanism)是RabbitMQ中用于控制消息传递给消费者的一种机制。它定义了在一个信道上,消费者允许的最大未确认的消息数量。一旦未确认的消息数量达到了设置的预取值,RabbitMQ就会停止向该消费者发送更多消息…...
机器学习介绍
机器学习是人工智能(AI)的一个分支,它使计算机系统能够从数据中学习并改进它们的性能。机器学习的核心在于开发算法,这些算法可以从大量数据中识别模式和特征,并用这些信息来做出预测或决策,而无需进行明确…...
OpenCV4.9开发之Window开发环境搭建
1.打开OpenCV所在github地址 2.点击opencv仓库,进入仓库详情,点击右下方的OpenCV 4.9.0进入下载页面 3.点击opencv-4.9.0-windows.exe下载 开始下载中... 下载完成 下载完成后,双击运行解压,默认解压路径,修改为c:/...
DDD 中的实体和值对象有什么区别?
在DDD中,实体 Entity 和值对象 Value Object 是两个基本的概念,它们之间有一些重要的区别。 唯一性:实体是唯一的,每个实体都有一个唯一的标识符,即使它的属性在一段时间内发生了变化,它仍然是这个实体。与…...
算法-最值问题
#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介绍与使用
在项目正式上线之前,我们通常需要通过压测来评估当前系统能够支撑的请求量、排查可能存在的隐藏bug;压力测试(压测)是确保系统在高负载情况下仍能稳定运行的重要步骤。通过模拟高并发场景,可以评估系统的性能瓶颈、可靠…...
数学思想论(有目录)
数学思想是数学发展过程中的重要指导原则,它涉及对数学概念、方法和理论的理解和认识,以及如何利用这些工具来解决实际问题。数学思想的形成和演进是随着数学的发展而逐渐深化的,它体现了人类对数学本质和应用的不断探索和思考。 一些主要的数学思想包括: 函数与方程思想…...
C++的并发世界(五)——线程状态切换
0.线程状态 初始化:该线程正在被创建; 就绪:该线程在列表中就绪,等待CPU调度; 运行:该线程正在运行; 阻塞:该线程被阻塞挂机,Blocked状态包括:pendÿ…...
2026 机器人行业发展前景与 AI 获客方案深度解析
引言:机器人行业的爆发式增长与获客挑战2026 年 3 月,全球机器人行业正处于爆发前夜。数据显示,2026 年全球机器人市场规模预计将达到 4000 亿元,较 2025 年增长 25%(数据来自网络)。随着具身智能技术的加速…...
Fillinger:设计自动化时代的效率提升工具
Fillinger:设计自动化时代的效率提升工具 【免费下载链接】illustrator-scripts Adobe Illustrator scripts 项目地址: https://gitcode.com/gh_mirrors/il/illustrator-scripts 核心价值:从机械操作到创意释放的设计革命 核心价值:让…...
利用Charles实现请求与响应的动态修改:从基础到实战
1. Charles工具简介与基础配置 Charles是一款功能强大的网络抓包工具,它就像是你手机和电脑之间的"透明玻璃",能让你清清楚楚地看到所有进出的网络请求。我第一次接触Charles是在调试一个电商APP的支付接口时,当时遇到一个诡异的bu…...
RWKV7-1.5B-g1a镜像优势解析:离线加载兼容+软链修复+日志分级排查设计
RWKV7-1.5B-g1a镜像优势解析:离线加载兼容软链修复日志分级排查设计 1. 平台简介与核心能力 rwkv7-1.5B-g1a是基于新一代RWKV-7架构的多语言文本生成模型,专为轻量级应用场景优化设计。该镜像经过工程化改造,在保持原模型优秀生成能力的同时…...
LFM2.5-1.2B-Thinking-GGUF保姆级教程:Web界面汉化+响应式布局适配移动端指南
LFM2.5-1.2B-Thinking-GGUF保姆级教程:Web界面汉化响应式布局适配移动端指南 1. 模型与平台介绍 LFM2.5-1.2B-Thinking-GGUF是Liquid AI推出的一款轻量级文本生成模型,特别适合在资源有限的环境中快速部署使用。这个镜像内置了GGUF模型文件和llama.cpp…...
从LeetCode到ACM:迷宫最短路径的C++ BFS模板,这么写就对了
从LeetCode到ACM:迷宫最短路径的C BFS模板实战精解 在算法竞赛和面试刷题中,迷宫类问题是最经典的场景之一。无论是LeetCode上的简单矩阵遍历,还是ACM竞赛中复杂的路径搜索,广度优先搜索(BFS)都是解决这类问…...
Android开发者必看:火山引擎API验签实战,5步搞定接口适配
Android开发者实战指南:火山引擎API验签与接口适配全解析 在移动应用开发领域,直接调用第三方API服务已成为提升开发效率的常见做法。火山引擎作为国内领先的云服务平台,其丰富的API接口为Android应用开发提供了强大支持。然而,由…...
Java: 手动实现DeepSeek R1工具调用,基于ReAct与Spring AI的实践指南
1. DeepSeek R1工具调用的现状与挑战 DeepSeek R1作为当前热门的开源大模型,在实际应用中经常会遇到需要调用外部工具的场景。但很多开发者在使用过程中发现,当前版本的DeepSeek R1并不支持原生的工具调用功能。这意味着当我们想让模型执行诸如查询天气、…...
Qwen2.5-VL-7B-Instruct实战教程:如何将截图中的UI设计精准还原为可运行HTML+CSS
Qwen2.5-VL-7B-Instruct实战教程:如何将截图中的UI设计精准还原为可运行HTMLCSS 1. 工具简介与环境准备 Qwen2.5-VL-7B-Instruct是一个专门针对RTX 4090显卡优化的多模态大模型工具,它能看懂图片内容并生成相应的代码。想象一下,你只需要给…...
AXI非对齐访问实战指南:从WSTRB信号到DMA数据搬运的避坑细节
AXI非对齐访问实战指南:从WSTRB信号到DMA数据搬运的避坑细节 在FPGA与ASIC设计中,AXI总线作为AMBA协议族的核心成员,其非对齐访问特性常被开发者视为"双刃剑"。当处理摄像头YUV数据、音频采样流或网络封包等非规整数据时࿰…...
