题目描述
给定一个以字符串表示的数字 num 和一个数字 k ,从 num 中移除 k 位数字,使得剩下的数字最小。如果可以删除全部数字,则结果为 0。
1.num仅有数字组成
2.num是合法的数字,不含前导0
3.删除之后的num,请去掉前导0(不算在移除次数中)
数据范围:num的长度满足 1≤105 1≤k≤n≤105 ,保证 num 中仅包含 0~9 的十进制数
输入描述
第一行输入一个字符串数字,一个数字K文章来源:https://www.toymoban.com/news/detail-665145.html
输出描述
剩余的数字文章来源地址https://www.toymoban.com/news/detail-665145.html
示例一
输入
"1432219",3
输出
"1219"
示例二
输入
"100999",3
输出
"9"
代码实现
# coding:utf-8
# 移掉 K 位数字
# https://www.nowcoder.com/practice/0fe685c8272d40f1b9785fedd2499c1c?tpId=196&tqId=39412&ru=/exam/oj
"""
思路:
核心:以某字符为中心,寻找左边的最近比该字符严格小的字符。(单调栈:严格单调递增)
步骤:
从左到右遍历字符串,如果栈非空&&栈顶元素>=当前字符&&k!=0,则弹栈,并最后将当前字符入栈。
当k==0时,则说明弹栈次数用完了。
当弹出0的时候,不需k--,因为前导0忽略。
最后,当弹栈次数用完后,只需将栈中字符和未入栈字符拼接,即可得到数值最小化。
"""
class Solution:
def removeKnums(self, num, k):
# write code here
stack = []
for i in range(len(num)):
while stack and k and int(num[i]) < int(stack[-1]):
k -= 1
stack.pop()
if not stack and num[i] == '0':
continue
stack.append(num[i])
stack = stack[:-k] if k else stack
if not stack:
stack.append('0')
return ''.join(stack)
到了这里,关于华为OD-移掉K位数字的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!