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ÿ…...
C语言——指针
地址是由物理的电线上产生的,能够标识唯一一个内存单元。在C语言中,地址也叫做指针。 在32位机器中,有32根地址线。地址是由32个0/1组成的二进制序列,也就是用4个字节来存储地址。 在64位机器中,有64根地址线。地址是…...
手搓二分查找
第一种: 该种方法是若a[mid]目标数,则让r一直等于mid,让l往右移动,一直移动到rl,这时候跳出循环,在循环外判断 但是不能写成让lmid,让r往左移动,比如a[2]key,这时&#x…...
pycharm调试(步过(Step Over)、单步执行(Step Into)、步入(Step Into)、步出(Step Out))
pycharm调试 pycharm调试 pycharm调试为什么要学会调试?1. 步过 (Step Over)2. 单步执行 (Step Into)3. 步入(Step Into)4. 步出(Step Out) 为什么要学会调试? 调试可以帮助初学者更深入地理解编程基础&am…...
Linux是什么,该如何学习
🐇明明跟你说过:个人主页 🏅个人专栏:《Linux :从菜鸟到飞鸟的逆袭》 🏅 🔖行路有良友,便是天堂🔖 目录 一、引言 1、Linux的起源与发展 2、Linux在现代计算机领域…...
C++ | Leetcode C++题解之第7题整数反转
题目: 题解: class Solution { public:int reverse(int x) {int rev 0;while (x ! 0) {if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {return 0;}int digit x % 10;x / 10;rev rev * 10 digit;}return rev;} };...
Linux------一篇博客了解Linux最常用的指令
🎈个人主页:靓仔很忙i 💻B 站主页:👉B站👈 🎉欢迎 👍点赞✍评论⭐收藏 🤗收录专栏:Linux 🤝希望本文对您有所裨益,如有不足之处&#…...
vscode安装通义灵码
作为vscode的插件,直接使用 通义灵码-灵动指间,快码加编,你的智能编码助手 通义灵码,是一款基于通义大模型的智能编码辅助工具,提供行级/函数级实时续写、自然语言生成代码、单元测试生成、代码注释生成、代码解释、研…...
RIP协议(路由信息协议)
一、RIP协议概述 RIP协议(Routing Information Protocol,路由信息协议)是一种基于距离矢量的内部网关协议,即根据跳数来度量路由开销,进行路由选择。 相比于其它路由协议(如OSPF、ISIS等)&#…...
SpringBoot根据配置类动态加载不同环境下的自定义配置
dev环境配置 Profile({"dev","test"}) PropertySource("classpath:dev.properties") public class DevConfigLoader { }Profile("prod") PropertySource("classpath:prod.properties") public class ProdConfigLoader { }P…...
什么?穷哥们没钱RLHF?跟我一起DPO吧,丐版一样用
本次DPO训练采用TRL的方式来进行训练 Huggingface TRL是一个基于peft的库,它可以让RL步骤变得更灵活、简单,你可以使用这个算法finetune一个模型去生成积极的评论、减少毒性等等。 本次进行DPO的模型是一个500M的GPT-2,目的是训练快&#x…...
承德网站建设规划/请你设计一个网络营销方案
文章目录前言一、用途1.捕获页面错误2.调试测试用例3.展示测试结果4.记录页面状态二、方法1. save_screenshot2. get_screenshot_as_file3. get_screenshot_as_png4. get_screenshot_as_base64总结前言 大家好,我是空空star,本篇给大家分享一下Selenium基…...
四川省住房和城乡建设厅官方网站/杭州新站整站seo
H - 扑克牌 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 128000/64000 KB (Java/Others)Submit StatusProblem Description 一副不含王的扑克牌由52张牌组成,由红桃、黑桃、梅花、方块4组牌组成,每组13张不同的面值。现在给定52张牌中的…...
集团网站建设调研报告/长沙网络推广平台
参考:Tiny Spring 分析一,原文:1000行代码读懂Spring(一)- 实现一个基本的IoC容器 代码地址:https://github.com/xiaoxicode/jdk_source_1.7/tree/master/tinyspring 特此声明,本文不能算严格意义上的原创…...
关于网站制作报价/长沙关键词优化方法
解决 Win10 局域网下两台电脑无法ping通: 无法访问目标主机解决 Win10 局域网下两台电脑无法ping通: 无法访问目标主机问题描述第一步:启用规则第二步:修改高级共享设置第三步:ping测试解决 Win10 局域网下两台电脑无法ping通: 无法访问目标主…...
php建站系统哪个好/福州短视频seo
用axios配合接口实现一个简单的例子 第一步: 第二步: 第三步: 第四步: 第五步: 这里是我的项目需求 一:这里需要传的参数为图下(且都设置默认值) data() {return {params: {pageNum: 1, // 当前页pageSiz…...
网站兼容9/有没有可以代理推广的平台
如今互联网技术在不断地发展和进步。同时Web3D产品建模技术也越来越承受,被广泛应用于诸多行业当中。商迪3D构建的Web3D产品建模可视化三维模型在产品建模和宣传展示中,Web3D技术发挥了极大的作用,并为产品建模和展示注入了新的活力。电商产品…...