每日算法-250424
每日算法打卡 (24/04/25) - LeetCode 2971 & 1647
记录一下今天解决的两道 LeetCode 题目
2971. 找到最大周长的多边形
题目
思路
贪心
一个基本的多边形构成条件是:最长边必须小于其他所有边的长度之和。
为了找到周长最大的多边形,我们应该尽可能地包含更多的边。因此,一个自然的贪心策略是先将所有可能的边长进行排序。
解题过程
- 排序:将边长数组
nums
从小到大排序。这是贪心策略的基础,方便我们从小到大尝试构建多边形。 - 遍历与累加:我们维护一个当前边长之和
sum
。从最短的边开始累加。 - 判断合法性:当我们考虑加入第
i
条边 (长度为nums[i]
) 时,需要检查之前所有边的和sum
(即nums[0] + ... + nums[i-1]
) 是否大于nums[i]
。- 根据多边形构成条件,如果
sum > nums[i]
,那么以nums[i]
作为最长边,加上之前i
条边(总共i+1
条边)可以构成一个合法的多边形。其周长为sum + nums[i]
。因为我们希望周长尽可能大(包含尽可能多的边),所以我们记录下这个合法的周长。 - 如果
sum <= nums[i]
,则无法以nums[i]
作为最长边构成多边形。
- 根据多边形构成条件,如果
- 更新最大周长:我们用一个变量
maxPerimeter
来记录遍历过程中遇到的最大合法周长。只有当sum > nums[i]
时,我们才更新maxPerimeter = sum + nums[i]
。 - 继续累加:无论当前
nums[i]
能否构成合法多边形,我们都将其加入sum
(sum += nums[i]
),以便为后续判断更长的边做准备。 - 初始条件与返回:多边形至少需要3条边。我们从数组的第三个元素(索引
i = 2
)开始检查。如果遍历结束后,maxPerimeter
仍然是初始值(例如 0 或 -1,表示从未找到合法的多边形),则返回 -1。否则,返回maxPerimeter
。
- 代码细节:
sum
在代码中实际上是nums[0] + ... + nums[i]
的前缀和。trueSum
对应我们上面说的maxPerimeter
。index
在代码中记录的是构成最大周长多边形的最长边的索引。检查index < 2
等价于检查是否找到了至少一个包含3条边的合法多边形(因为index
初始为1,只有当i=2
时满足条件,index
才会更新为2)。
复杂度
- 时间复杂度: O ( N log N ) O(N \log N) O(NlogN),主要是排序数组
nums
的时间。遍历数组需要 O ( N ) O(N) O(N)。 - 空间复杂度: O ( log N ) O(\log N) O(logN) 或 O ( N ) O(N) O(N),取决于排序算法使用的栈空间。如果忽略排序的辅助空间(或视为原地排序),则为 O ( 1 ) O(1) O(1)。
Code
class Solution {public long largestPerimeter(int[] nums) {Arrays.sort(nums);long sum = nums[0] + nums[1];long trueSum = 0;int index = 1;for (int i = 2; i < nums.length; i++) {if (sum <= nums[i]) {sum += nums[i];} else {index = i;sum += nums[i];trueSum = sum;}}return index < 2 ? -1 : trueSum;}
}
1647. 字符频次唯一的最小删除次数
题目
思路
贪心
目标是最小化删除次数,使得所有存在字符的频次都是唯一的。
我们可以先统计每个字符的出现频次。为了方便处理冲突(频次相同),一个好的策略是处理排序后的频次。
解题过程
- 统计频次:使用一个数组(大小为26)统计字符串
s
中每个字符 (‘a’ 到 ‘z’) 的出现次数。 - 排序频次:将得到的频次(只考虑大于0的频次,或者处理整个频次数组)进行升序排序。
- 处理冲突(贪心):从后往前(即从最大的频次开始)遍历排序后的频次数组
hash
。- 我们检查当前频次
hash[i]
是否大于等于它前一个的频次hash[i-1]
。 - 如果
hash[i] <= hash[i-1]
,说明出现了频次冲突或者顺序不对(因为已经排序了,所以只会是相等的情况)。我们需要减少hash[i-1]
的值,使其严格小于hash[i]
。 - 贪心选择:为了最小化删除次数,我们将冲突的频次
hash[i-1]
减少到max(0, hash[i] - 1)
。这样既保证了唯一性,又使得减少的量(即删除的字符数)最少。 - 累加删除次数:将原始频次与修改后频次之差累加到总删除次数
count
中。 - 注意:修改后的频次
hash[i-1]
必须大于等于 0。如果目标值hash[i] - 1
小于 0,则必须将当前频次降为 0,删除次数就是其原始值。
- 我们检查当前频次
- 返回结果:遍历完成后,
count
即为所需的最小删除次数。
复杂度
- 时间复杂度: O ( N + K log K + K ) = O ( N ) O(N + K \log K + K) = O(N) O(N+KlogK+K)=O(N)。
- O ( N ) O(N) O(N) 用于遍历字符串统计频次 (N 为字符串长度)。
- O ( K log K ) O(K \log K) O(KlogK) 用于排序频次数组 (K 为字符集大小,这里是 26,是常数)。
- O ( K ) O(K) O(K) 用于遍历频次数组处理冲突。
- 因为 K 是常数 (26),所以 K log K K \log K KlogK 和 K K K 都是 O ( 1 ) O(1) O(1)。因此,总时间复杂度由 O ( N ) O(N) O(N) 主导。
- 空间复杂度: O ( K ) = O ( 1 ) O(K) = O(1) O(K)=O(1)。
- 需要一个大小为 K (26) 的数组来存储频次。
Code
class Solution {public int minDeletions(String ss) {char[] s = ss.toCharArray();int[] hash = new int[26];for (char c : s) {hash[c - 'a']++;}Arrays.sort(hash);int count = 0;for (int i = 24; i >= 0; i--) {if (hash[i] == 0) {break;}if (hash[i] >= hash[i + 1]) {count += (hash[i + 1] - 1) <= 0 ? hash[i] : hash[i] - (hash[i + 1] - 1);hash[i] = Math.max((hash[i + 1] - 1), 0);}}return count;}
}
相关文章:
每日算法-250424
每日算法打卡 (24/04/25) - LeetCode 2971 & 1647 记录一下今天解决的两道 LeetCode 题目 2971. 找到最大周长的多边形 题目 思路 贪心 一个基本的多边形构成条件是:最长边必须小于其他所有边的长度之和。 为了找到周长最大的多边形,我们应该尽可能…...
在本地部署n8n:完整指南
n8n是一个强大的工作流自动化工具,可以帮助你连接不同的应用程序和服务,无需编写复杂的代码。本指南将带你完成在本地计算机上部署n8n的完整过程。 什么是n8n? n8n(发音为"n-eight-n")是一个开源的工作流自…...
棋盘格角点检测顺序问题
文章目录 前言一、OpenCV函数测试二、原因分析三、libcbdetect修改总结 前言 棋盘格角点检测在相机拼接、机械臂手眼标定中等应用很广泛,通常也要求尽量各种角度摆放从而保证标定精度。然后就自然想到了这个问题:如果棋盘格任意角度摆放怎么能对应上角点…...
C++之类和对象:定义,实例化,this指针,封装
C语言是面向过程的,C是面向对象的,利用对象交互,接口完成事情。 类的定义: 我们在C语言中可以用struct创建自定义结构体,在C中可以在结构体中定义函数了,这种就被称为类。 #include<iostream> usi…...
Ubuntu系统下交叉编译iperf3
一、参考资料 Linux下iperf3移植到arm下测试100M网口-CSDN博客 Iperf3移植到ARM Linux及使用教程-CSDN博客 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编…...
游戏引擎学习第243天:异步纹理下载
仓库 https://gitee.com/mrxiao_com/2d_game_6 https://gitee.com/mrxiao_com/2d_game_5 回顾并为今天设定阶段 目前的开发工作主要回到了图形渲染相关的部分。我们之前写了自己的软件渲染器,这个渲染器性能意外地好,甚至可以以相对不错的帧率运行过场…...
27、Session有什么重⼤BUG?微软提出了什么⽅法加以解决?
Session的重大BUG 1、进程回收导致Session丢失 原理: IIS的进程回收机制会在系统繁忙、达到特定内存阈值等情况下,自动回收工作进程(w3wp.exe)。由于Session数据默认存储在进程内存中,进程回收时这些数据会被清除。 …...
机器学习在网络安全中的应用:守护数字世界的防线
一、引言 随着信息技术的飞速发展,网络安全问题日益凸显,成为全球关注的焦点。传统的网络安全防护手段,如防火墙、入侵检测系统(IDS)和防病毒软件,虽然在一定程度上能够抵御攻击,但在面对复杂多…...
从数据到智慧:解密机器学习的自主学习密码
在数字洪流奔涌的时代,每一次点击、每一行代码、每一条传感器数据都在生成海量信息。传统编程如同精心设计的齿轮组,需要工程师逐行编写规则;而机器学习则打破这一范式,赋予机器从数据中自主提炼规律、总结模式的超能力。这种能力…...
Trae或者VsCode无法识别相对路径(不自动切换工作目录)
在VsCode中或者Trae中,只要是在vscode的基础上修改得到的编辑器,都默认没有勾选自动选择当前文件路径为工作路径,因此需要手动修改工作路径或者设置,否则无法识别相对路径,PyCharm中就不会出现这种问题。 解决方法&…...
解决VSCode每次SSH连接服务器时,都需要下载vscode-server
如下图所示,本地下载或者在服务器终端上运行wget指令获得vscode服务器包 注意,解压完成后,需要修改文件名为你本地vscode的commit ID...
架构-系统工程与信息系统基础
一、系统工程核心知识 1. 系统工程定义 本质:一种组织管理技术,从整体出发分析系统要素(组成、结构、信息流、控制机制),追求“整体最优”,借助计算机实现规划、设计、管理、控制的优化。目标:…...
矩阵运算和线性代数操作开源库
用于矩阵运算和线性代数操作常用的开源库推荐,涵盖不同编程语言和硬件平台: C/C 库 Eigen 特点:高性能的模板库,支持矩阵/向量运算、线性求解、特征值计算等,无需依赖外部BLAS/LAPACK。 官网:https://eig…...
无标注文本的行业划分(行业分类)算法 —— 无监督或自监督学习
对于无标注文本的行业划分(行业分类),属于典型的无监督或自监督学习任务。以下是几种常见的算法方法及实现思路,适用于缺乏标注数据的场景: 一、基于关键词匹配的规则方法 核心思想:通过预定义的行业关键…...
电子病历高质量语料库构建方法与架构项目(计划篇)
电子病历(EMR)作为医疗信息化的重要产物,包含了丰富的医疗信息和临床知识,是辅助临床决策、药物挖掘和医学研究的重要资源。然而,电子病历数据具有非结构化、噪声大、专业性强等特点,如何构建高质量电子病历语料库成为医疗自然语言处理领域的核心挑战。本全计划将从项目背景…...
什么混合检索?在基于大模型的应用开发中,混合检索主要解决什么问题?
混合检索的定义 混合检索(Hybrid Retrieval)是一种结合多种检索技术优势的信息检索方法,旨在通过整合不同检索策略提升检索系统的准确性、召回率和适应性。其核心思想是将基于关键词的检索(如BM25、TF-IDF)与基于语义的检索(如向量检索、深度学习模型)相结合,以应对单…...
优化uniappx页面性能,处理页面滑动卡顿问题
问题:在页面遇到滑动特别卡的情况就是在页面使用了动态样式或者动态类,做切换的时候页面重新渲染导致页面滑动卡顿 解决:把动态样式和动态类做的样式切换改为通过获取元素修改样式属性值 循环修改样式示例 bannerList.forEach((_, index)…...
Yocto meta-toradex-security layer 创建独立数据分区
By Toradex 胡珊逢 简介 Toradex 为其产品使用的软件系统如 Linux 提供了诸多的安全功能,例如 Secure Boot、分区加密、OP-TEE 等,帮助用户应对安全合规。这些功能可以通过在 Yocto Project 中添加由 Toradex 开发的 meta-toradex-securitylayer 被轻松…...
uniapp 安卓离线本地打包,Android Studio生成apk包
第一步:HbuilderX生成本地资源包 下载最新的SDK 下载完后压缩下来是这样的 将HbuilderX生成的复制到这里,替换 Android Studio引入下载的最新文件里的HBuilder-Integrate-AS目录 好,接下来开始修改配置 把你的证书签名ÿ…...
C语言教程(十四):C 语言指针详解
一、指针的基本概念 指针是一个变量,其值为另一个变量的内存地址。简单来说,指针指向了内存中的某个位置,通过指针可以间接访问该位置存储的数据。指针的使用可以让程序更加高效地处理数据,特别是在处理数组、动态内存分配等方面。…...
2025年04月24日Github流行趋势
项目名称:markitdown 项目地址url:https://github.com/microsoft/markitdown项目语言:Python历史star数:53,351今日star数:822项目维护者:afourney, gagb, sugatoray, PetrAPConsulting, l-lumin项目简介&a…...
切割PDF使用python,库PyPDF2
使用 Python 将大型 PDF 文件分割成多个小文件 理解任务 将一个 170M 的 PDF 文件分割成多个 10M 左右的小文件。这在处理大型 PDF 文件时非常有用,例如: 减少单个文件的大小,方便传输或存储分别处理不同的文件部分提高 PDF 处理的效率 选…...
网络IP冲突的成因与解决方案
网络IP冲突的成因与解决方案 一、IP冲突的常见现象与危害二、IP冲突的常见原因三、6种实用解决方案四、预防IP冲突的4个最佳实践五、总结 前言 肝文不易,点个免费的赞和关注,有错误的地方请指出,看个人主页有惊喜。 作者:神的孩子…...
python版本得数独游戏
python版本得数独游戏 游戏说明: 游戏使用9x9数独棋盘,.表示可填写的空格 输入格式为行,列,数值(如3,5,7表示第3行第5列填7) 系统会自动检查以下内容: 输入格式是否正确 数字是否在1-9范围内 是否修改固定数字 是…...
64位系统上编译32位openh264 x264
在64位系统上要使用i386(32位库)的时候,有些是找不到apt可以安装的版本,所以需要手动编译安装,下面是openh264和x264的编译过程。 默认编译openh264 git clone https://github.com/cisco/openh264make ARCHi386 OSlinux PREFIX/lib/i386-li…...
加深对vector理解OJ题
17. 电话号码的字母组合 - 力扣(LeetCode) OJ(一)电话号码的字母组合 思路:这里以引用leetcode里面的一个大佬里面的图 1.这道题中,我们用递归的方法来写。 为了简洁展示,我们举例子”456“&am…...
协作开发攻略:Git全面使用指南 — 第三部分 特殊应用场景
协作开发攻略:Git全面使用指南 — 第三部分 特殊应用场景 Git 是一种分布式版本控制系统,用于跟踪文件和目录的变更。它能帮助开发者有效管理代码版本,支持多人协作开发,方便代码合并与冲突解决,广泛应用于软件开发领域…...
机器学习(9)——随机森林
文章目录 1. 随机森林的基本原理想2. 算法流程2.1. 数据采样(Bootstrap):2.2. 构建决策树:2.3. 聚合预测: 3. 随机森林的构建过程3.1. 数据集的随机抽样3.2. 决策树的训练3.3. 树的生长3.4. 多棵树的集成3.5. 输出预测…...
(第三篇)Springcloud之Ribbon负载均衡
一、简介 1、介绍 Spring Cloud Ribbon是Netflix发布的开源项目,是基于Netflix Ribbon实现的一套客户端负载均衡的工具。主要功能是提供客户端的软件负载均衡算法,将Netflix的中间层服务连接在一起。Ribbon客户端组件提供一系列完善的配置项如连接超时&…...
Linux并发与竞争:从生活例子到内核实战
Linux并发与竞争:从生活例子到内核实战 一、并发与竞争:多车道公路的交通问题 想象一条四车道的高速公路(多核CPU),所有车辆(线程/进程)都想通过同一个收费站(共享资源)…...
【金仓数据库征文】——金仓数据库:国产数据库的卓越之选
目录 一、金仓数据库的核心技术优势 (一)强大的事务处理能力 (二)高度安全 (三)全面兼容与深度适配 (四)强大的扩展性 (五)智能便捷的工具 二、电信行…...
人脸识别考勤系统实现教程:基于Face-Recognition、OpenCV与SQLite
引言 随着人工智能技术的飞速发展,人脸识别技术已广泛应用于安防、金融、教育等多个领域。本文将带领大家利用Python的face-recognition库、OpenCV和SQLite数据库,从零开始构建一个具备异常报警功能的人脸识别考勤系统。该系统能够实时检测视频流中的人…...
Golang 闭包学习
引言 在平常的 Go 语言开发中,常常需要将一段函数逻辑封装起来,异步执行、作为回调传递,甚至保持某些运行时状态。此时,闭包成为一种非常自然的编程手段。它允许我们在函数内部“记住”外部作用域中的变量,从而实现变…...
Trae+DeepSeek学习Python开发MVC框架程序笔记(四):使用sqlite验收用户名和密码
继续通过Trae向DeepSeek发问并修改程序,实现程序运行时生成数据库,用户在系统登录页面输入用户名和密码后,控制器通过模型查询用户数据库表来验证用户名和密码,验证通过后显示登录成功页面,验证失败则显示登录失败页面…...
【mdlib】0 全面介绍 mdlib - Rust 实现的 Markdown 工具集
mdlib 是由开发者 bahdotsh 创建的一个多功能 Markdown 工具集合,包含两个主要组件:一个轻量级 Markdown 解析库和一个功能完善的个人 Wiki 系统。该项目完全采用 Rust 实现,兼具高性能与跨平台特性。 核心组件 Markdown 解析库 特性&#…...
使用Django REST Framework快速开发API接口
以下是使用 Django 和 Django REST Framework (DRF) 开发 API 接口的核心步骤,涵盖模型、迁移、序列化、视图、路由等关键环节: 前言 什么是DRF? Django REST Framework(DRF) 是基于Django的一个强大且灵活的工具包&…...
Vue3项目中 npm 依赖安装 --save 与 --save-dev 的区别解析
这两个命令的区别如下: bash npm install --save types/crypto-js # 安装到 dependencies(生产依赖) npm install --save-dev types/crypto-js # 安装到 devDependencies(开发依赖) 核心区别 依赖分类不同…...
开源模型应用落地-语音合成-MegaTTS3-零样本克隆与多语言生成的突破
一、前言 在人工智能技术飞速发展的今天,文本转语音(TTS)技术正以前所未有的速度改变着人机交互的方式。近日,字节跳动与浙江大学联合推出了一款名为MegaTTS3 的开源TTS模型,再次刷新了行业对高质量语音合成的认知。作为一款轻量化设计的模型,MegaTTS3以仅0.45亿参数 的规…...
connection.cursor() 与 models.objects.filter
在 Django 中操作数据库时,connection.cursor() 和 models.objects.filter 是两种不同的方式,各有特点和适用场景: models.objects.filter (ORM 方式) 特点: 基于 Django 的 ORM(对象关系映射)框架&am…...
深入浅出JavaScript常见设计模式:从原理到实战(1)
深入浅出JavaScript常见设计模式:从原理到实战(1) 设计模式是一种在特定情境下解决软件设计中常见问题的通用方案或模板。在特定的开发场景中使用特定的设计模式,可以提升代码质量,增强代码可读性和可维护性,提高团队开发效率&…...
RCE学习
一、远程代码执行漏洞 1. 远程代码执行的定义 定义:远程代码执行漏洞(Remote Code Execute,简称RCE)是指程序预留了执行命令或代码的接口并被黑客利用的漏洞。广义上也包括远程命令执行(Remote Command Execute&…...
Redis安装及入门应用
应用资料:https://download.csdn.net/download/ly1h1/90685065 1.获取文件,并在该文件下执行cmd 2.输入redis-server-lucifer.exe redis.windows.conf,即可运行redis 3.安装redis客户端软件 4.安装后运行客户端软件,输入链接地址…...
【棒球运动】户外运动安全技巧·棒球1号位
以棒球运动为例,在棒球这项结合力量、速度与策略的户外运动中,安全防护是保障运动表现的核心。以下是针对棒球特点的户外安全指南,涵盖装备、环境与行为规范三大维度: 一、场景化防护装备选择 击球场景 击球手需佩戴双重防护头盔…...
卸载rpm包
昨天了解了查询rpm包的流程和命令,那么今天了解一下删除rpm包的语法,那么话不多说,来看. 1.基本语法 rpm -e RPM包的名称 注:e erase擦除 2.案例 删除firefox软件包 :rpm -e firefox 3.细节讨论 1.如果其它软件包依赖于要卸载的软件包,卸载时…...
【AI提示词】艺人顾问
提示说明 专业艺人顾问,专注于为客户提供全面的艺术、娱乐和商业咨询服务,帮助他们在竞争激烈的行业中树立品牌影响力,提升市场竞争力 提示词 # Role: 艺人顾问## Profile - language: 中文 - description: 专业艺人顾问,专注于…...
第七部分:向量数据库和索引策略
什么是矢量数据库? 简单来说,向量数据库是一种专门化的数据库,旨在优化存储和检索以高维向量形式表示的文本。 为什么这些数据库对RAG至关重要?因为向量表示能够在大规模文档库中进行高效的基于相似性的搜索,根据用户…...
26考研|数学分析:数项级数
数项级数这一章的开始,开启了新的关于“级数”这一新的概念体系的学习进程,此部分共包含四章的内容,分别为数项级数、函数项级数、幂级数以及傅里叶级数。这一章中,首先要掌握级数的相关概念与定义,重难点在于掌握判断…...
2025 年免费 Word 转 PDF 转换器有哪些?
我们列出了最好的 Word 到 PDF 转换器,以便轻松轻松地将 .doc 文件导出到 .pdf 而不会丢失原始格式。 尽管 Microsoft 365 包含一个 Word 版本,该版本可以将您正在处理的 .docx 文档无缝导出为 PDF 格式,但仍在使用旧版 Word 的人可能缺少此…...
【Spring Boot】深入解析:#{} 和 ${}
1.#{} 和 ${}的使用 1.1数据准备 1.1.1.MySQL数据准备 (1)创建数据库: CREATE DATABASE mybatis_study DEFAULT CHARACTER SET utf8mb4;(2)使用数据库 -- 使⽤数据数据 USE mybatis_study;(3ÿ…...
SpringMVC知识体系
SpringMVC 知识体系 1. SpringMVC 基础 MVC 设计模式 Model: 模型层,处理业务逻辑View: 视图层,负责界面展示Controller: 控制层,处理请求并协调模型和视图 核心组件 DispatcherServlet: 前端控制器HandlerMapping: 处理器映射Controller: …...