算法(蓝桥杯)贪心算法5——删数问题的解题思路
问题描述
给定一个高精度的正整数 n(n≤1000 位),需要删除其中任意 s 个数字,使得剩下的数字按原左右顺序组成一个新的正整数,并且这个新的正整数最小。例如,对于数字 153748,删除 2 个数字后,最小的数是 1348。
解题思路
1. 贪心算法
要解决这个问题,我们可以使用贪心算法。贪心算法在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的。
2. 维护单调递增栈
我们可以通过维护一个单调递增的栈来实现这个目标。具体步骤如下:
2.1 初始化栈
创建一个空栈
stack,用于存储最终结果中的数字。2.2 遍历每个数字
遍历输入的高精度正整数
n的每一位数字num。2.3 维护单调递增栈
弹出条件:当栈不为空(
stack),且还需要删除数字(s > 0),且栈顶元素大于当前数字(stack[-1] > num)时,弹出栈顶元素,并减少s的值。这样做的目的是尽可能地让结果数的高位更小,从而使得整个数更小。入栈操作:将当前数字
num入栈。这一步是为了保留当前数字,以便后续继续判断。2.4 处理剩余的删除操作
遍历结束后,如果
s还大于0,说明原数是单调递增的。在这种情况下,直接去掉末尾的s个数字即可。因为从末尾去掉数字对结果数的影响最小。2.5 拼接结果并处理前导0
拼接结果:将栈中的数字拼接成一个字符串。
处理前导0:使用
lstrip('0')去掉前导0。如果去掉前导0后字符串为空(即原数删除后只剩下0),则返回'0'。3. 示例解释
以
n = "153748"和s = 2为例,详细说明每一步的操作:
初始化栈:
stack = []。遍历每一位数字:
num = '1':栈为空,直接入栈。stack = ['1']。
num = '5':栈顶元素'1'小于'5',直接入栈。stack = ['1', '5']。
num = '3':栈顶元素'5'大于'3',弹出'5',s减1。stack = ['1']。然后'3'入栈。stack = ['1', '3']。
num = '7':栈顶元素'3'小于'7',直接入栈。stack = ['1', '3', '7']。
num = '4':栈顶元素'7'大于'4',弹出'7',s减1。stack = ['1', '3']。然后'4'入栈。stack = ['1', '3', '4']。
num = '8':栈顶元素'4'小于'8',直接入栈。stack = ['1', '3', '4', '8']。遍历结束后,
s为0,不需要再处理。拼接结果并处理前导0:
''.join(stack).lstrip('0'),结果为'1348'。最终结果为
'1348',这是删除2个数字后得到的最小数。4. 代码实现
def min_number_after_delete(n, s):"""删除s个数字后得到的最小数:param n: 原始高精度正整数,字符串形式:param s: 需要删除的数字个数:return: 删除s个数字后得到的最小数,字符串形式"""stack = []# 遍历每个数字for num in n:# 当栈不为空且s大于0且栈顶元素大于当前数字时,弹出栈顶元素while stack and s > 0 and stack[-1] > num:stack.pop()s -= 1# 当前数字入栈stack.append(num)# 如果s还大于0,说明原数是单调递增的,直接去掉末尾的s个数字即可if s > 0:stack = stack[:-s]# 将栈中的数字拼接成字符串,并去掉前导0return ''.join(stack).lstrip('0') or '0'# 示例 n = "153748" s = 2 print(min_number_after_delete(n, s)) # 输出:1348n = "1087" s = 1 print(min_number_after_delete(n, s)) # 输出:875. 总结
通过维护一个单调递增的栈,我们可以有效地找到删除
s个数字后得到的最小数。这种方法的时间复杂度为 O(n),其中 n 是输入数字的长度,因为每个数字最多只会被入栈和出栈一次。希望这个解释能帮助你更好地理解这个问题的解法。如果有任何疑问,欢迎继续提问。
相关文章:
算法(蓝桥杯)贪心算法5——删数问题的解题思路
问题描述 给定一个高精度的正整数 n(n≤1000 位),需要删除其中任意 s 个数字,使得剩下的数字按原左右顺序组成一个新的正整数,并且这个新的正整数最小。例如,对于数字 153748,删除 2 个数字后&a…...
数字孪生发展及应用
一、数字孪生的前世今生 (一)萌芽的种子:概念的首次提出 数字孪生的概念最早可追溯到 20 世纪 60 年代,美国国家航空航天局(NASA)在阿波罗计划中,为了训练宇航员和指挥控制人员,使用…...
MYSQL对表的增删改查
表的基本操作 创建表create table [if not exists] <tableName> (<columnName> <columnType> [constraints] [comment] , ...<columnName> <columnType> [constraints] [comment] ) ;删除表drop table [if exists] <tableName> ;…...
左神算法基础提升--4
文章目录 树形dp问题Morris遍历 树形dp问题 求解这个问题需要用到我们在基础班上学到的从节点的左子树和右子树上拿信息的方法。 求最大距离主要分为两种情况:1.当前节点参与最大距离的求解;2.当前节点不参与最大距离的求解; 1.当前节点参与最…...
【docker踩坑记录】
docker踩坑记录 踩坑记录(持续更新中.......)docker images 权限问题 踩坑记录(持续更新中…) docker images 权限问题 permission denied while trying to connect to the Docker daemon socket at unix:///var/run/docker.sock: Head "http://%2Fvar%2Frun%2Fdocker.s…...
CloudberryDB(四)并行执行
要查看CloudberryDB & Greenplum数据库的并行度配置,可以使用以下几种方法: ### 方法一:使用SHOW命令 在Greenplum数据库中,可以使用SHOW命令来查看当前的并行度配置。例如: sql SHOW gp_parallel_degree ; SH…...
LARGE LANGUAGE MODELS ARE HUMAN-LEVEL PROMPT ENGINEERS
题目 大型语言模型是人类级别的提示工程师 论文地址:https://arxiv.org/abs/2211.01910 项目地址:https://github.com/keirp/automatic_prompt_engineer 摘要 通过对自然语言指令进行调节,大语言模型 (LLM) 显示了作为通用计算机的令人印象深…...
rabbitmq安装延迟队列
在RabbitMQ中,延迟队列是一种特殊的队列类型。当消息被发送到此类队列后,不会立即投递给消费者,而是会等待预设的一段时间,待延迟期满后才进行投递。这种队列在多种场景下都极具价值,比如可用于处理需要在特定时间触发…...
Kubernetes (K8s) 入门指南
Kubernetes (K8s) 入门指南 什么是Kubernetes? Kubernetes,通常简称为 K8s(因为从 “K” 到 “s” 之间有八个字符),是一个开源的容器编排平台,用于自动化部署、扩展和管理容器化应用程序。它最初由谷歌设…...
Python 调用 Ollama 库:本地大语言模型使用详解
ollama 是一个用于调用本地大语言模型(Large Language Models,LLMs)的 Python 库,旨在提供简单、高效的 API 接口,以便开发者能够方便地与本地的大语言模型进行交互。以下是关于如何在 Python 中使用 ollama 库的详细介…...
python matplotlib绘图,显示和保存没有标题栏和菜单栏的图像
目录 1. 使用plt.savefig保存无边框图形 2. 显示在屏幕上,并且去掉窗口的标题栏和工具栏 3. 通过配置 matplotlib 的 backend 和使用 Tkinter(或其他图形库) 方法 1:使用 TkAgg 后端,并禁用窗口的工具栏和标题栏 …...
无人机(Unmanned Aerial Vehicle, UAV)路径规划介绍
无人机(Unmanned Aerial Vehicle, UAV)是无人驾驶飞行器的简称。凭借其体积小巧、操作简便、生存能力强等诸多优势,无人机在军事、电力巡检、航空航天与科学研究等诸多领域得到了广泛应用。在执行任务时,无人机可搭载多种传感器设…...
python爬虫入门(实践)
python爬虫入门(实践) 一、对目标网站进行分析 二、博客爬取 获取博客所有h2标题的路由 确定目标,查看源码 代码实现 """ 获取博客所有h2标题的路由 """url "http://www.crazyant.net"import re…...
于灵动的变量变幻间:函数与计算逻辑的浪漫交织(下)
大家好啊,我是小象٩(๑ω๑)۶ 我的博客:Xiao Xiangζั͡ޓއއ 很高兴见到大家,希望能够和大家一起交流学习,共同进步。 这一节我们主要来学习单个函数的声明与定义,static和extern… 这里写目录标题 一、单个函数…...
python实现pdf转word和excel
一、引言 在办公中,我们经常遇收到pdf文件格式,因为pdf格式文件不易修改,当我们需要编辑这些pdf文件时,经常需要开通会员或收费功能才能使用编辑功能。今天,我要和大家分享的,是如何使用python编程实现…...
Pandas使用笔记
个人学习笔记 日期转换 索引日期格式:2023-09-12 15:00:00 转换为:2023-09-12 import pandas as pd# 假设你的 DataFrame 名为 df,索引是 2023-09-12 15:00:00 # 这里创建一个示例 DataFrame 用于演示 data {value: [1, 2, 3]} index pd…...
高等数学学习笔记 ☞ 定积分与积分公式
1. 定积分的基本概念 1.1 定积分的定义 1. 定义:设函数在闭区间上有界。在闭区间上任意插入若干个分点,即, 此时每个小区间的长度记作(不一定是等分的)。然后在每个小区间上任意取,对应的函数值为。 为保证每段的值(即矩形面积)无…...
wow-agent---task2使用llama-index创建Agent
一:创造俩个函数,multiply和add作为fuction calling被LLM当做工具来使用,实现计算一个简单的计算题: from llama_index.llms.ollama import Ollama from llama_index.core.agent import ReActAgent from llama_index.core.tools …...
RabbitMQ实现延迟消息发送——实战篇
在项目中,我们经常需要使用消息队列来实现延迟任务,本篇文章就向各位介绍使用RabbitMQ如何实现延迟消息发送,由于是实战篇,所以不会讲太多理论的知识,还不太理解的可以先看看MQ的延迟消息的一个实现原理再来看这篇文章…...
Oracle 拉链式merge sort join 原理
Oracle 拉链式Merge Sort Join 的原理,我用一个生活中的比喻来解释。 --- 比喻场景:匹配快递包裹和收件人 1. 快递包裹清单 想象我们有一个快递公司送货的包裹清单,清单按照收件人的邮编(ZIP Code)排序: …...
PyTorch 3.0静态图分布式训练插件下载与安装(官方未公开的--enable-static-graph标志使用手册)
第一章:PyTorch 3.0静态图分布式训练插件下载与安装PyTorch 3.0 并非官方发布的正式版本(截至 2024 年,PyTorch 最新稳定版为 2.3.x),因此“PyTorch 3.0 静态图分布式训练插件”属于概念性技术预研组件,目前…...
Docker 安装 Portainer(Docker 容器管理工具)
安装步骤 1. 创建 Portainer 数据卷(可选,用于持久化数据) docker volume create portainer_data2. 运行 Portainer 容器 方式一:Docker 命令运行 docker run -d \-p 8000:8000 \-p 9443:9443 \--name portainer \--restartalways…...
OpenClaw语音控制之语音命令识别系统架构详解
5.1 系统架构总览5.1.1 整体架构OpenClaw 语音命令识别系统是一个基于事件驱动的实时语音处理平台,核心设计目标是实现低延迟、高可靠的语音交互能力。系统采用模块化架构,各组件通过明确定义的接口进行通信,支持多种电话服务提供商ÿ…...
从STM32开发手册中快速定位信息:文脉定序系统的嵌入式应用联想
从STM32开发手册中快速定位信息:文脉定序系统的嵌入式应用联想 作为一名在嵌入式领域摸爬滚打多年的工程师,我深知那种在动辄上千页的芯片手册里“大海捞针”的痛苦。比如,当你需要配置一个特定的定时器中断,或者想确认某个GPIO引…...
龙虾为啥越养越贵,越用越蠢?极客老王揭秘Agent落地真相
进入2026年3月,科技圈的舆论风向标发生了一次剧烈偏移。曾经被誉为开启“AI代驾”时代的超级智能体OpenClaw(俗称“龙虾”),在经历了一年的野蛮生长后,正陷入一场空前的信任危机。根据最新的行业调研数据显示ÿ…...
别再手动切换收发!用SP3485芯片实现RS485自动收发电路的保姆级教程
用SP3485芯片实现RS485自动收发电路的完整设计指南 在工业控制、楼宇自动化等长距离通信场景中,RS485接口因其抗干扰能力强、传输距离远等优势成为首选。然而传统RS485设计需要手动控制收发使能信号,不仅增加软件复杂度,还容易因时序错误导致…...
基于深度学习的CT肺部分割技术:在医学影像分析中实现95% Dice系数的精准自动化方案
基于深度学习的CT肺部分割技术:在医学影像分析中实现95% Dice系数的精准自动化方案 【免费下载链接】lungmask Automated lung segmentation in CT 项目地址: https://gitcode.com/gh_mirrors/lu/lungmask 在医学影像分析领域,CT肺部分割一直是临…...
【风电功率预测】到了2026年,企业为什么总输在“最后一公里”?从气象到功率再到电力交易,少赚的钱到底丢在哪
2026年,风电行业已经进入一个非常现实的新阶段。过去,很多企业讨论风电功率预测,核心问题还是“预报准不准”。而到了今天,这个问题虽然仍然重要,却已经不是决定收益高低的唯一变量。真正拉开差距的,是企业…...
开源音频格式转换终极指南:ncmdumpGUI实现数字音乐资产自由流转的完整方案
开源音频格式转换终极指南:ncmdumpGUI实现数字音乐资产自由流转的完整方案 【免费下载链接】ncmdumpGUI C#版本网易云音乐ncm文件格式转换,Windows图形界面版本 项目地址: https://gitcode.com/gh_mirrors/nc/ncmdumpGUI 在数字音乐时代…...
从入门到精通:用OmenSuperHub打造专属惠普游戏本性能方案
从入门到精通:用OmenSuperHub打造专属惠普游戏本性能方案 【免费下载链接】OmenSuperHub 项目地址: https://gitcode.com/gh_mirrors/om/OmenSuperHub 🔍 问题发现:官方游戏控制中心的五大痛点 作为惠普OMEN游戏本用户,你…...
