【华为OD-E卷 - 114 找最小数 100分(python、java、c++、js、c)】
【华为OD-E卷 - 找最小数 100分(python、java、c++、js、c)】
题目
给一个正整数NUM1,计算出新正整数NUM2,NUM2为NUM1中移除N位数字后的结果,需要使得NUM2的值最小
输入描述
- 输入的第一行为一个字符串,字符串由0-9字符组成,记录正整数NUM1,NUM1长度小于32。 输入的第二行为需要移除的数字的个数,小于NUM1长度
输出描述
- 输出一个数字字符串,记录最小值NUM2
用例
用例一:
输入:
2615371
4
输出:
131
python解法
- 解题思路:
- 要删除给定数字字符串中的k个字符,使得剩下的数字最小,可以采用贪心算法。具体步骤如下:
维护一个栈:用于构建最终结果,确保每次添加的数字尽可能小。
遍历每个字符:对于当前字符,若栈顶元素比它大且还有删除次数(k > 0),则弹出栈顶元素,直到不再满足条件。这样可以保证高位尽可能小。
处理剩余删除次数:遍历完成后,若仍有删除次数未使用,则从末尾删除剩余次数对应的字符。
去除前导零:最终结果可能存在前导零,需去除。若结果为空,返回’0’。
def minimize_number(num, k):# 最终需要保留的长度length = len(num) - kstack = []for digit in num:# 当栈不为空,且还有删除次数,且栈顶数字大于当前数字时,弹出栈顶while stack and k and stack[-1] > digit:stack.pop()k -= 1stack.append(digit)# 截取前length个字符(处理剩余k的情况)result = ''.join(stack[:length])# 去除前导零,若结果为空则返回'0'return result.lstrip('0') or '0'num = input()
k = int(input())
print(minimize_number(num, k))
java解法
- 解题思路
- 使用栈模拟单调递增序列
遍历 num 的字符时,使用一个字符数组 result 来存储最终保留的数字。这个数组类似于一个单调递增栈,我们尝试让栈顶元素尽可能小。
移除较大的数字
在遍历 num 时,如果当前字符比 result 的栈顶元素小,并且还可以删除数字(toRemove > 0),那么就弹出栈顶元素(减少 toRemove 的值),从而让剩下的数字形成更小的值。
控制最终结果的长度
最终需要保留 keepLength = num.length() - toRemove 个字符,因此 result 数组的长度设为 keepLength,只允许存入 keepLength 个字符。
去除前导零
由于可能会出现前导 0,如 “10200” 移除 1 个字符后可能变成 “0200”,所以要去掉前导 0,如果去掉后字符串为空,则返回 “0”。
import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String num = sc.next(); // 输入的数字字符串int toRemove = sc.nextInt(); // 需要移除的数字个数System.out.println(findSmallest(num, toRemove));}private static String findSmallest(String num, int toRemove) {// 如果需要移除的个数等于字符串长度,则返回 "0"if (num.length() == toRemove) return "0";int keepLength = num.length() - toRemove; // 需要保留的字符数char[] result = new char[keepLength]; // 结果数组(模拟栈)int pos = -1; // 当前存入 result 数组的最后一个元素位置(栈顶指针)for (char ch : num.toCharArray()) { // 遍历字符串中的每个字符// 维护单调递增栈:如果当前字符比栈顶元素小,并且还有删除名额,就弹出栈顶元素while (pos >= 0 && toRemove > 0 && result[pos] > ch) {pos--; // 退栈toRemove--; // 还需要删除的个数减少}// 只有在栈的长度不超过目标长度时,才将当前字符加入if (pos + 1 < keepLength) {result[++pos] = ch; // 入栈} else {// 如果栈已满,则直接减少 toRemove 计数toRemove--;}}// 去除前导零int start = 0;while (start < keepLength && result[start] == '0') start++;// 如果最终所有的数字都是 0,则返回 "0"return start == keepLength ? "0" : new String(result, start, keepLength - start);}
}
C++解法
- 解题思路
- 本题的目标是从一个数字字符串 num1 中移除 removeCount 个数字,使得剩下的数字形成的最小值。核心思想是使用单调递增栈,具体步骤如下:
利用双端队列(deque)作为单调递增栈
遍历 num1 的字符:
如果当前字符比 stack(单调递增栈)的栈顶元素小,并且仍然可以删除数字,就弹出栈顶元素(删除较大的数)。
这样可以确保数字整体变小。
将当前字符压入栈。
确保栈的长度符合要求
遍历结束后,如果 stack 仍然比需要保留的长度长,就继续弹出末尾元素。
去除前导零
由于可能会出现 000123 这样的情况,需要去掉前导零。
只要栈的第一个元素是 0 且长度大于 1,就不断弹出前面的 0。
返回最终的最小数字
将 stack 转换成字符串并返回。
#include <iostream>
#include <deque>
#include <string>using namespace std;// 获取移除指定个数后的最小数
string getResult(string num1, int removeCount) {// 如果需要移除的字符等于字符串长度,返回 "0"if (num1.length() == removeCount) return "0";int remainCount = num1.length() - removeCount; // 需要保留的字符数deque<char> stack; // 使用双端队列作为栈// 遍历整个字符串for (int i = 0; i < num1.length(); i++) {// 当栈非空、仍可以删除字符、栈顶元素大于当前字符时,弹出栈顶元素(保证剩下的数字尽可能小)while (!stack.empty() && removeCount > 0 && stack.back() > num1[i]) {stack.pop_back(); // 删除较大的字符removeCount--; // 递减待删除字符数}// 将当前字符压入栈stack.push_back(num1[i]);}// 若栈中元素仍然超出需要保留的个数,弹出多余的元素while (stack.size() > remainCount) {stack.pop_back();}// 去除前导零while (stack.front() == '0' && stack.size() > 1) {stack.pop_front();}// 将双端队列转换为字符串string result(stack.begin(), stack.end());return result;
}int main() {string num1;int count;getline(cin, num1); // 读取字符串cin >> count; // 读取要删除的字符个数cout << getResult(num1, count) << endl; // 输出结果return 0;
}
C解法
更新中
JS解法
更新中
注意:
如果发现代码有用例覆盖不到的情况,欢迎反馈!会在第一时间修正,更新。
解题不易,如对您有帮助,欢迎点赞/收藏
相关文章:
【华为OD-E卷 - 114 找最小数 100分(python、java、c++、js、c)】
【华为OD-E卷 - 找最小数 100分(python、java、c、js、c)】 题目 给一个正整数NUM1,计算出新正整数NUM2,NUM2为NUM1中移除N位数字后的结果,需要使得NUM2的值最小 输入描述 输入的第一行为一个字符串,字…...
快速搭建GPU环境 | docker、k8s中使用gpu
目录 一、裸机部署安装 GPU Driver安装 CUDA Toolkit测试 二、Docker 环境安装 nvidia-container-toolkit配置使用该 runtime 三、 k8s 环境安装 device-plugin安装 GPU 监控 一、裸机部署 裸机中要使用上 GPU 需要安装以下组件: GPU DriverCUDA Toolkit 二者的关…...
VSCode设置——通过ctrl+鼠标滚动改变字体大小(新版本的vs)
"editor.mouseWheelZoom": true 第一步: 第二步:...
【kafka实战】06 kafkaTemplate java代码使用示例
在 Spring Boot 中使用 KafkaTemplate 可以方便地向 Kafka 发送消息。下面为你详细介绍使用步骤和示例代码。 1. 创建 Spring Boot 项目 你可以使用 Spring Initializr(https://start.spring.io/ )来创建一个新的 Spring Boot 项目,添加以下…...
Java 23新特性
文章目录 Java 23新特性一、引言二、Markdown文档注释(JEP 467)示例 三、ZGC:默认的分代模式(JEP 474)1. 为什么要引入分代模式2. 使用分代模式的优势3. 如何启用分代模式 四、隐式声明的类和实例主方法(JE…...
bat脚本实现自动化漏洞挖掘
bat脚本 BAT脚本是一种批处理文件,可以在Windows操作系统中自动执行一系列命令。它们可以简化许多日常任务,如文件操作、系统配置等。 bat脚本执行命令 echo off#下面写要执行的命令 httpx 自动存活探测 echo off httpx.exe -l url.txt -o 0.txt nuc…...
[创业之路-285]:《产品开发管理-方法.流程.工具 》-1- IPD的功能列表以及导入步骤
一、概述: 对于没有IPD(集成产品开发)流程的公司来说,导入IPD需要循序渐进、有序进行,而不是一步到位。这是因为IPD不仅仅是一种新的产品开发流程,它还涉及到公司文化、组织结构、团队协作方式以及思维方式…...
Redis命令:列表模糊删除详解
前言 在Redis中,列表(List)是一种非常常用的数据结构,允许存储多个有序的元素。然而,在实际应用中,可能会遇到需要删除列表中符合某种模式的元素的需求。本文将详细介绍如何在Redis中实现列表的模糊删除。…...
Day36-【13003】短文,数组的行主序方式,矩阵的压缩存储,对称、三角、稀疏矩阵和三元组线性表,广义表求长度、深度、表头、表尾等
文章目录 本次课程内容第四章 数组、广义表和串第一节 数组及广义表数组的基本操作数组的顺序存储方式-借用矩阵行列式概念二维数组C语言对应的函数-通常行主序方式 矩阵的压缩存储对称矩阵和三角矩阵压缩存储后,采用不同的映射函数稀疏矩阵-可以构成三元组线性表三…...
大数据sql查询速度慢有哪些原因
1.索引问题 可能缺少索引,也有可能是索引不生效 2.连接数配置:连接数过少/连接池比较小 连接数过 3.sql本身有问题,响应比较慢,比如多表 4.数据量比较大 -这种最好采用分表设计 或分批查询 5.缓存池大小 可能是缓存问题ÿ…...
文件 I/O 和序列化
文件I/O C#提供了多种方式来读写文件,主要通过System.IO命名空间中的类来实现,下方会列一些常用的类型: StreamReader/StreamWriter:用于以字符为单位读取或写入文本文件。 BinaryReader/BinaryWriter:用于以二进制格…...
机器学习中的关键概念:通过SKlearn的MNIST实验深入理解
欢迎来到我的主页:【Echo-Nie】 本篇文章收录于专栏【机器学习】 1 sklearn相关介绍 Scikit-learn 是一个广泛使用的开源机器学习库,提供了简单而高效的数据挖掘和数据分析工具。它建立在 NumPy、SciPy 和 matplotlib 等科学计算库之上,支持…...
HELLOCTF反序列化靶场全解
level 2 <?php/* --- HelloCTF - 反序列化靶场 关卡 2 : 类值的传递 --- HINT:尝试将flag传递出来~# -*- coding: utf-8 -*- # Author: 探姬 # Date: 2024-07-01 20:30 # Repo: github.com/ProbiusOfficial/PHPSerialize-labs # email: adminhello-ctf.com…...
十二、Docker Compose 部署 SpringCloudAlibaba 微服务
一、部署基础服务 0、项目部署结构 项目目录结构如下: /home/zhzl_hebei/ ├── docker-compose.yml └── geochance-auth/└── Dockerfile└── geochance-auth.jar └── geochance-system/└── Dockerfile└── geochance-system.jar └── geochance-gateway/…...
VUE之插槽
1、默认插槽 <template><div class"father"></div><h3>父组件</h3><div class"content"><Category title"热门游戏列表"><ul><li v-for"g in games" :key"g.id">{{…...
4. Go结构体使用
1、结构体的简介 结构体(Struct)是编程语言中常见的一种复合数据类型,它将不同类型的数据元素(成员)组合成一个单一的实体。通过结构体,程序员可以将具有不同类型和性质的信息绑定到一个对象中,…...
版本控制的重要性及 Git 入门
版本控制:软件开发的基石 在软件开发的浩瀚宇宙中,版本控制无疑是那颗最为闪耀的恒星,照亮了整个开发过程,成为现代软件开发不可或缺的基石。 历史追溯,定位问题根源 版本控制就像是一位不知疲倦的史官,…...
[NKU]C++安装环境 VScode
bilibili安装教程 vscode 关于C/C的环境配置全站最简单易懂!!大学生及初学初学C/C进!!!_哔哩哔哩_bilibili 1安装vscode和插件 汉化插件 2安装插件 2.1 C/C 2.2 C/C Compile run 2.3 better C Syntax 查看已…...
deepseek本地部署
DeepSeek本地部署详细指南 DeepSeek作为一款开源且性能强大的大语言模型,提供了灵活的本地部署方案,让用户能够在本地环境中高效运行模型,同时保护数据隐私,这里记录自己DeepSeek本地部署流程。 主机环境 cpu:amd 7500Fgpu:406…...
网络编程day1
实例: struct sockaddr_in addr {0};//初始化 addr.sin_family AF_INET;//设置地址族 addr.sin_port htons(8888);//设置端口号 addr.sin_addr.s_addr inet_addr("192.168.1.1"); //设置ip地址 bind(sock,(struct sockaddr *)&addr,sizeof(ad…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...
实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
stm32进入Infinite_Loop原因(因为有系统中断函数未自定义实现)
这是系统中断服务程序的默认处理汇编函数,如果我们没有定义实现某个中断函数,那么当stm32产生了该中断时,就会默认跑这里来了,所以我们打开了什么中断,一定要记得实现对应的系统中断函数,否则会进来一直循环…...
