带你读《图解算法小抄》十七、栈(10)

简介: 带你读《图解算法小抄》十七、栈(10)

带你读《图解算法小抄》十七、栈(9)https://developer.aliyun.com/article/1348069?groupCode=tech_library


11.移除k位数字


给定一个非负整数字符串num和一个整数k,从该整数中移除k位数字,使得剩下的数字形成的整数尽可能小。返回移除k位数字后的结果。

 

示例:

 

输入:num = "1432219", k = 3 输出:"1219" 解释:移除数字4、3和2后,剩下的数字形成的整数最小,即为1219。

 

输入:num = "10200", k = 1 输出:"200" 解释:移除数字1后,剩下的数字形成的整数最小,即为200。

1题目分析与解题步骤:

这个问题可以使用栈来解决。我们可以遍历整数字符串中的每个数字,然后使用一个栈来模拟移除数字的过程。对于每个数字,我们将其与栈顶元素比较,如果当前数字小于栈顶元素且还有剩余的移除次数k,则将栈顶元素出栈。最后,栈中的元素即为移除k位数字后的结果。

 

解题步骤如下:

 

创建一个栈stack,用于模拟移除数字的过程。

遍历整数字符串num中的每个数字,并执行以下操作:

将当前数字转换为整数类型。

如果栈不为空且当前数字小于栈顶元素且还有剩余的移除次数k,则将栈顶元素出栈,减少移除次数k

将当前数字入栈。

 

如果移除次数k大于0,则从栈顶依次出栈,直到移除次数k减为0

将栈中的元素按照出栈的顺序组合成字符串,并返回最终结果。

2JavaScript解题框架:

function removeKDigits(num, k) {
  let stack = new Stack();
  for (let digit of num) {
    while (!stack.isEmpty() && digit < stack.peek() && k > 0) {
      stack.pop();
      k--;
    }
    stack.push(digit);
  }  while (k > 0) {
    stack.pop();
    k--;
  }
  let result = '';
  while (!stack.isEmpty()) {
    result = stack.pop() + result;
  }  // 移除前导零
  result = result.replace(/^0+/, '');  // 处理结果为空的情况
  if (result === '') {
    return '0';
  }
  return result;
}

 

在这个框架中,我们首先定义了一个栈类Stack,其中包含了常用的栈操作方法。然后,我们使用栈来移除k位数字。

 

removeKDigits函数中,我们遍历整数字符串num,并使用栈来模拟移除数字的过程。对于每个数字,我们将其与栈顶元素比较,如果当前数字小于栈顶元素且还有剩余的移除次数k,则将栈顶元素出栈,减少移除次数k

 

最后,我们将栈中的元素按照出栈的顺序组合成字符串,并返回最终结果。同时,我们需要处理结果为空的情况和移除前导零的情况。


带你读《图解算法小抄》十七、栈(11)https://developer.aliyun.com/article/1348066?groupCode=tech_library

相关文章
|
16天前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
37 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
19天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
5月前
|
存储 算法 调度
数据结构与算法-栈篇
数据结构与算法-栈篇
30 3
|
19天前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
34 3
|
5月前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
26天前
|
算法 C++
【算法单调栈】 矩形牛棚(C/C++)
【算法单调栈】 矩形牛棚(C/C++)
|
3月前
|
算法
【算法】栈算法——逆波兰表达式求值
【算法】栈算法——逆波兰表达式求值
|
3月前
|
存储 算法
【算法】栈算法——最小栈
【算法】栈算法——最小栈
|
3月前
|
算法
【算法】栈算法——栈的压入、弹出序列
【算法】栈算法——栈的压入、弹出序列
|
5月前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)