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

贪心算法（16）（java）俄罗斯套娃信封问题

news 来源：原创 2025/8/26 2:30:10

题目：给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

示例 1：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1j

解法1：常规解法->动态规划

步骤：1.状态表示 2.状态转移方程 3.初始化 4.填表顺序 5.返回值

import java.util.Arrays;public class Solution {public int maxEnvelopes(int[][] e) {Arrays.sort(e,(v1,v2)->{return v1[0] - v2[0];});int n=e.length;int[]dp=new int[n];int ret=1;for (int i=1;i<n;i++){dp[i]=1;for (int j=0;j<i;j++){if (e[i][0]>e[j][0]&&e[i][1]>e[j][1]){dp[i]=Math.max(dp[i],dp[i]+1);}}ret=Math.max(ret,dp[i]);}return ret;}public static void main(String[] args) {Solution solution=new Solution();int [][] e={{5,4},{6,4},{6,7},{2,3}};System.out.println(solution.maxEnvelopes(e));}
}

解法2：重写排序+贪心+二分

重写排序：1.当左端点不同的时候，按左端点从小到大的顺序排列；

2.当左端点相同的时候，按右端点从大到小的顺序排列；

import java.util.ArrayList;
import java.util.Arrays;public class Solution2 {public int maxEnvelopes(int[][] e){Arrays.sort(e,(v1,v2)->{return v1[0]!=v2[0]?v1[0]-v2[0]:v2[1]-v1[1];});ArrayList<Integer>ret=new ArrayList<>();ret.add(e[0][1]);for (int i=1;i<e.length;i++){int b=e[i][1];if(b>ret.get(ret.size()-1)){ret.add(b);}else {int left=0,right=ret.size()-1;while(left>right){int mid=(left+right)/2;if(ret.get(mid)>=b)right=mid;else left=mid+1;}ret.set(left,b);}}return ret.size();}public static void main(String[] args) {Solution solution1=new Solution();int[][] e={{5,4},{6,4},{6,7},{2,3}};System.out.println(solution1.maxEnvelopes(e));}
}

贪心算法（16）（java）俄罗斯套娃信封问题

题目：给你一个二维整数数组 envelopes ，其中 envelopes[i] [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算…...

编程日记 2025/8/26 2:30:10

【DeepSeek原理学习2】MLA 多头隐变量注意力

解决的问题 Multi-Head Latent Attention，MLA——解决的问题：KV cache带来的计算效率低和内存需求大以及上下文长度扩展问题。 MLA原理 MLA原理：其核心思想是将键（Key）和值（Value）矩阵压缩到…...

编程日记 2025/8/26 2:20:22

2024年RAG大赛

2024 CCF国际AIOps挑战赛赛题与赛制解读-CSDN博客自动化测评也比较有意思，分数为关键字语义相似度，分值比为6:4. 2024 CCF AIOPS国际挑战赛优秀奖方案分享 https://zhuanlan.zhihu.com/p/7444390758 【大模型RAG获奖方案分享】如何提高RAG系统在…...

编程日记 2025/8/25 12:04:05

2025-4-6-C++ 学习有序数组、set()的一些内置函数与求和函数

C的学习必须更加精进一些，对于好多的函数和库的了解必须深入一些。文章目录 3510. 移除最小数对使数组有序 II（有序数组）题目参考代码（1）auto it idx.lower_bound(i);功能解释可能的使用场景常见错误 （2&…...

编程日记 2025/8/26 2:20:25

Flutter：Flutter SDK版本控制，fvm安装使用

1、首先已经安装了Dart，cmd中执行 dart pub global activate fvm2、windows配置系统环境变量 fvm --version3、查看本地已安装的 Flutter 版本 fvm releases4、验证当前使用的 Flutter 版本： fvm flutter --version5、切换到特定版本的 Flutter fvm use …...

编程日记 2025/8/26 2:22:57

GPT-4o 的“图文合体”是怎么做到的

每周跟踪AI热点新闻动向和震撼发展想要探索生成式人工智能的前沿进展吗？订阅我们的简报，深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同，从行业内部的深度分析和实用指南中受益。不要错过这个机会，成为AI领…...

编程日记 2025/8/26 2:26:10

PyTorch教程：如何读写张量与模型参数

本文演示了PyTorch中张量（Tensor）和模型参数的保存与加载方法，并提供完整的代码示例及输出结果，帮助读者快速掌握数据持久化的核心操作。 1. 保存和加载单个张量通过torch.save和torch.load可以直接保存和读取张量。 import to…...

编程日记 2025/8/26 2:20:26

MySQL8.0.31安装教程，附pdf资料和压缩包文件

参考资料：黑马程序员一、下载点开下面的链接：https://dev.mysql.com/downloads/mysql/ 点击Download 就可以下载对应的安装包了, 安装包如下: 我用夸克网盘分享了「mysql」，链接：https://pan.quark.cn/s/ab7b7acd572b 二、解…...

编程日记 2025/8/26 2:22:56

Linux 系统中对存储设备（/dev/mmcblk、/dev/sd、/dev/nvme）进行分区、格式化或挂载的操作

在 Linux 系统中对存储设备（/dev/mmcblk、/dev/sd、/dev/nvme）进行分区、格式化或挂载的操作步骤如下： 一、确认设备信息首先明确要操作的设备名称（如 /dev/sdb、/dev/nvme0n1），避免误操作导致数据丢失&a…...

编程日记 2025/8/21 11:06:01

【Kafka基础】topics命令行操作大全：高级命令解析（1）

1 创建压缩主题（Log Compaction） /export/home/kafka_zk/kafka_2.13-2.7.1/bin/kafka-topics.sh --create \--bootstrap-server 192.168.10.33:9092 \--topic comtopic \--partitions 3 \--replication-factor 2 \--config cleanup.policycompact \--con…...

编程日记 2025/8/19 4:25:13

springboot集成spring loadbalancer实现客户端负载均衡

在 Spring Boot 中实现负载均衡，通常需要结合 Spring Cloud 组件，比如 Spring Cloud LoadBalancer。Spring Cloud LoadBalancer 是一个客户端负载均衡器，可以与 Spring Boot 集成，实现微服务之间的负载均衡。以下是一个简单的示…...

编程日记 2025/8/22 15:41:54

什么是 k8s Affinity（亲和性）

在 Kubernetes（K8s）中，Affinity（亲和性） 是一种 Pod 调度策略，它用于控制 Pod 在什么条件下可以被调度到特定的节点上。它比 Taints 和 Tolerations 更灵活，可以基于节点属性或 Pod 之间的关系…...

编程日记 2025/8/24 5:32:58

深度探索：策略学习与神经网络在强化学习中的应用

深度探索：策略学习与神经网络在强化学习中的应用策略学习(Policy-Based Reinforcement Learning)一、策略函数1.1 策略函数输出的例子二、使用神经网络来近似策略函数：Policy Network ,策略网络2.1 策略网络运行的例子2.2需要的几个概念2.3神经网络近似…...

编程日记 2025/8/25 20:56:59

用VAE作为标题显示标题过短，所以标题变成了这样

VAE (Variational Autoencoder / 变分自编码器) 基本概念: VAE 是一种生成模型 (Generative Model)，属于自编码器 (Autoencoder) 家族。它的目标是学习数据的潜在表示 (Latent Representation)，并利用这个表示来生成新的、与原始数据相似的数据。与标…...

编程日记 2025/8/25 15:42:22

【day27】测试策略升级方案：需求阶段介入与业务规则覆盖矩阵设计

测试策略升级方案：需求阶段介入与业务规则覆盖矩阵设计一、需求评审阶段：主动识别业务逻辑问题在需求评审时，测试团队应通过结构化提问提前暴露潜在风险，避免后期返工。以下为提问框架与示例： 1. 业务逻辑澄清提问模…...

编程日记 2025/8/23 15:53:25

AI烘焙大赛中的算法：理解PPO、GRPO与DPO的罪简单的方式

🧠 向所有学习者致敬！ “学习不是装满一桶水，而是点燃一把火。” —— 叶芝我的博客主页： https://lizheng.blog.csdn.net 🌐 欢迎点击加入AI人工智能社区！ 🚀 让我们一起努力，共创…...

编程日记 2025/8/21 4:44:10

二分 —— 基本算法刷题路程

一、1.求阶乘 - 蓝桥云课算法代码： #include <bits/stdc.h> using namespace std; #define ll long long ll check(ll n) {ll cnt0;while(n){cnt(n/5);}return cnt; }int main() {ll k;cin>>k;ll L0,R1e19;while(L<R){ll mid(LR)>>1;if(che…...

编程日记 2025/8/22 11:04:40

内存序问题排查

1 内存序 2 简介 std::memory_order 是 C11 引入的一个枚举类型，用于和 <atomic> 原子操作一起使用，控制多线程环境下内存的可见性和执行顺序。它的主要作用是：告诉编译器和 CPU，在执行某个原子操作时，哪些内…...

编程日记 2025/8/20 4:50:05

历年跨链合约恶意交易详解（四）——Chainswap20210711

漏洞合约函数 function receive(uint256 fromChainId, address to, uint256 nonce, uint256 volume, Signature[] memory signatures) virtual external payable {_chargeFee();require(received[fromChainId][to][nonce] 0, withdrawn already);uint N signatures.length;r…...

编程日记 2025/8/22 4:17:02

Johnson

理论全源最短路算法 Floyd 算法，时间复杂度为 O(n)跑 n 次 Bellman - Ford 算法，时间复杂度是 O(nm)跑 n 次 Heap - Dijkstra 算法，时间复杂度是 O(nmlogm) 第 3 种算法被 Johnson 做了改造，可以求解带负权边的全源最短路。 J…...

编程日记 2025/8/22 4:18:00

spring boot + Prometheus + Grafana 实现项目监控

一、引入依赖 <dependencies><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-actuator</artifactId></dependency><!-- Micrometer Reg…...

编程日记 2025/8/20 2:26:46

Mythical Beings：第八季即将回归，探索新的神话传承

Mythical Beings是由Tarasca Art & Games开发的、基于Ignis区块链的卡牌收集游戏。自发布以来，这款游戏以其独特的玩法和深厚的神话背景吸引了大量玩家的关注。每张卡牌不仅代表着独特的游戏属性，还融合了丰富的文化和神话故事，使玩家不仅…...

编程日记 2025/8/24 1:20:10

Linux中查看占用端口号的进程信息的方法

在 Linux 中查看占用 ** 端口（eg:1717）**的进程号（PID），可以通过以下命令实现： 方法 1：使用 netstat 命令 sudo netstat -tulnp | grep :1717参数解释： -t：查看 TCP 端口…...

编程日记 2025/8/25 13:30:50

批量将 txt/html/json/xml/csv 等文本拆分成多个文件

我们的文本文件太大的时候，我们通常需要对文本文件进行拆分，比如按多少行一个文件将一个大的文本文件拆分成多个小的文本文件。这样我们在打开或者传输的时候都比较方便。今天就给大家介绍一种同时对多个文本文件进行批量拆分的方法，可以快速…...

编程日记 2025/8/24 17:21:51

爱普生高精度车规晶振助力激光雷达自动驾驶

在自动驾驶技术快速落地的今天，激光雷达作为车辆的“智慧之眼”，其测距精度与可靠性直接决定了自动驾驶系统的安全上限。而在这双“眼睛”的核心，爱普生（EPSON）的高精度车规晶振以卓越性能成为激光雷达实现毫米级感知的…...

编程日记 2025/8/25 0:28:08

Spring Boot 自定义 Redis Starter 开发指南（附动态 TTL 实现）

一、功能概述本 Starter 基于 Spring Boot 2.7 实现以下核心能力： Redis 增强：标准化 RedisTemplate 配置（JSON 序列化 LocalDateTime 支持）缓存扩展：支持 Cacheable(value “key#60s”) 语法动态设置 TTL配置集中…...

编程日记 2025/8/21 4:53:55

区分CRI、OCI、containerd、Docker、CRI-O、runc等名词概念

这些概念可以分为： 一、容器运行时Container Runtimes a、规范OCI (Open Container Initiative) 定义：OCI 是一个开放标准，用于定义容器格式和运行时的规范。它旨在确保容器镜像的格式和容器运行时的操作方式在不同的实现之间保持兼容性。 •…...

编程日记 2025/8/20 2:26:46

#关于process.env.NODE_ENV 与 import.meta.env 相关了解

process.env.NODE_ENV 在前端 Vue 项目中非常重要，但它其实是个“假象”，在前端它并不是原生就有的变量。下面我从多个角度来给你通俗讲明白它的由来和使用方式 👇 🌐 一、process.env.NODE_ENV 是干嘛用的？ 这是一个…...

编程日记 2025/8/25 9:56:26

R语言赋能气象水文科研：从多维数据处理到学术级可视化

全球气候变化加剧了极端天气与水文事件的复杂性，气象卫星、雷达、地面观测站及水文传感器每天产生TB级‌时空异质数据‌。传统研究常面临四大瓶颈： ‌数据清洗低效‌：缺失值、异常值处理耗时；‌时空分析模型构建复杂‌&#xff1…...

编程日记 2025/8/23 8:19:13

MySQL 约束（入门版）

目录一、约束的基本概念二、约束演示三、外键约束 （一）介绍 （二）外键约束语法 （三）删除/更新行为一、约束的基本概念 1、概念：约束是作用于表中字段上的规则，用于限制存储…...

编程日记 2025/8/22 2:28:17

【go】类型断言

接口-类型断言 Type Assertion Type Assertion（中文名叫：类型断言），通过它可以做到以下几件事情检查 i 是否为 nil（是nil直接抛出panic）检查 i 存储的值是否为某个类型具体的使用方式有两种&#xff…...

编程日记 2025/8/21 7:54:32

(复看)CExercise_06_1指针和数组_2 给定一个double数组，求平均值，并且返回

题目： 求平均值，给定一个double数组，求平均值，并且返回。要求使用while循环遍历数组，然后配合"*p"的语法实现。函数的声明如下： double get_ave(double *arr, int len); 关键点分析&#xff1…...

编程日记 2025/8/24 1:17:42

Ubuntu 服务器上运行相关命令，关闭终端就停止服务，怎么才能启动后在后台运行？

环境： Ubuntu 20.04 LTS 问题描述： Ubuntu 服务器上运行相关命令，关闭终端就停止服务，怎么才能启动后在后台运行？ bash docker/entrypoint.sh解决方案： bash docker/entrypoint.sh 脚本在后台运行&…...

编程日记 2025/8/24 19:42:16

ffmpeg提取字幕

使用ffmpeg -i test.mkv 获取视频文件的字幕流信息如下 Stream #0:4(chi): Subtitle: subrip (srt) (default) Metadata: title : chs Stream #0:5(chi): Subtitle: subrip (srt) Metadata: title : cht Stream #0:6(jpn)…...

编程日记 2025/8/24 18:44:13

深入理解Socket编程：构建简单的计算器服务器

一、Socket通信基础 1. Socket通信基本流程服务器端流程： 创建Socket (socket()) 绑定地址和端口 (bind()) 监听连接 (listen()) 接受连接 (accept()) 数据通信 (read()/write()) 关闭连接 (close()) 客户端流程： 创建Socket (socket()) 连接…...

编程日记 2025/8/22 10:53:03

CPU狂飙900%，该怎么处理

首先，说明一下问题：CPU飙升200% 以上是生产容易发生的场景场景:1：MySQL进程飙升900% 大家在使用MySQL过程，想必都有遇到过CPU突然过高，或者达到200%以上的情况。数据库执行查询或数据修改操作时，系统需…...

编程日记 2025/8/23 12:34:17

C++继承完全指南：从语法到设计模式----图解原理+工业级代码示例+陷阱规避

🔮✨⚡️🌌 欢迎来到张有志的量子编程次元 🌌⚡️✨🔮 ▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂ 🛸 核心探索舱 🛸 ⇩⇩⇩ 正在加载未来代码 ⇩⇩⇩ ▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔…...

编程日记 2025/8/22 1:07:28

使用Pholcus编写Go爬虫示例

想用Pholcus库来写一个Go的爬虫程序。首先，我得确认Pholcus的当前状态，因为之前听说过它可能已经不再维护了。不过用户可能还是需要基于这个库的示例，所以得先提供一个基本的框架。首先，我应该回忆一下Pholcus的基本用法。Pholc…...

编程日记 2025/8/23 11:43:53

R Excel 文件：高效数据处理与可视化工具的完美结合

R Excel 文件：高效数据处理与可视化工具的完美结合引言在数据分析和处理领域，R语言因其强大的数据处理能力和丰富的可视化功能而备受青睐。而Excel作为最常用的电子表格软件，其广泛的应用也使得R与Excel的结合成为数据处理与可视化的理想…...

编程日记 2025/8/22 10:52:40

Python设计模式：适配模式

1. 适配模式（Adapter Pattern）详解适配模式（Adapter Pattern）是一种结构型设计模式，它允许将一个类的接口转换成客户端所期望的另一种接口。适配模式使得原本由于接口不兼容而无法一起工作的类可以协同工作。换句话说…...

编程日记 2025/8/22 13:42:22

Python设计模式：策略模式

1. 什么是策略模式策略模式（Strategy Pattern）是一种行为型设计模式，它定义了一系列算法，将每个算法封装起来，并使它们可以互换。策略模式使得算法的变化独立于使用算法的客户。换句话说，策略模式允许在运…...

编程日记 2025/8/23 15:08:03

Unity Internal-ScreenSpaceShadows 分析

一、代码结构 // Unity built-in shader source. Copyright (c) 2016 Unity Technologies. MIT license (see license.txt)Shader "Hidden/Internal-ScreenSpaceShadows" {Properties {_ShadowMapTexture ("", any) "" {} // 阴影贴图纹理&…...

编程日记 2025/8/22 4:58:31

nginx配置oss代理

工作中会有一些时候需要将图片,视频,音频等文件放到oss这种对象存储中进行存储,实现高性能的访问,这种情况叫做动静分离.这里只做了图片的配置,视频以及音频的配置是一样的. 以下是nginx.conf的配置信息,其中还有ssl的加密配置,以及后端服务器的代理模块配置,(这里不用的话可以…...

编程日记 2025/8/20 12:18:06

UML对象图

UML对象图一、对象图核心概念对象图（Object Diagram）描述的是系统在某一时刻对象（实例）的状态快照。它关注的是实际对象之间的实例关系，而不是类与类之间的静态结构。主要特点有： 对象（Ob…...

编程日记 2025/8/20 2:26:48

手机不同App音量自动调节软件

软件介绍在日常使用手机的过程中，大家是不是经常会遇到在不同App之间切换时，需要频繁调整音量的情况呢？这样真的很不方便。而一款名为App Volume Control的软件就能很好地解决这个问题。 App Volume Control借助辅助功能服务，能…...

编程日记 2025/8/19 14:28:33

模板方法模式详解

模板方法模式详解及真实场景解决方案推荐学习完策略模式和模板方法模式看这个案例： 策略与模板方法模式组合详解模式定义模板方法模式是一种行为设计模式，在父类中定义算法的骨架，允许子类在不改变算法结构的情况下重写特定步骤。核心思…...

编程日记 2025/8/19 21:23:42

基于SSM邮件收发管理系统（带源码、论文）

摘要随着互联网技术的迅速发展和普及，网络通信已经成了人们离不开的通信手段。作为最早出现的网络通信方式还有世界上应用最为广泛的网络服务之一，电子邮件综合了电话通信和传统邮件的特点，具有传播速度快、价格低廉的优良特性。随着技术发…...

编程日记 2025/8/25 20:15:52

1990-2019年各地级市GDP数据

1990-2019年各地级市GDP数据 1、时间：1990-2019年 2、来源：城市年鉴 3、指标：行政区划代码、年份、省份、城市、经度、纬度、地区生产总值(万元) 4、范围：250地级市 5、指标解释：地区生产总值（Gross R…...

编程日记 2025/8/23 7:26:45

Scala相关知识学习总结5

1、多维数组定义： val arr Array.ofDim[Double](3,4) 表示二维数组中有三个一维数组，每个一维数组有四个元素。 2、列表 List 不可变 List：默认不可变，可创建有序且可重复的列表，可使用:从右向左增加数据&#xf…...

编程日记 2025/8/25 3:28:43

【LangChain Agent 】详解，构建自主决策的 LLM 应用

🐇明明跟你说过：个人主页 🏅个人专栏：《深度探秘：AI界的007》 🏅 🔖行路有良友，便是天堂🔖 目录一、引言 1、什么是 Lang Chain 2、什么是 Agent 二、LangChain …...

编程日记 2025/8/24 12:50:05

相关文章：