设计一个算法实现一个正整数,去掉若干位,不改变原顺序使得剩下的数字 字符组成的数最小。例如:输入 n 为 198642,s 为 4,结果为 12。
时间: 2024-02-25 22:52:15 浏览: 44
C++语言算法:大整数去掉N个数使其值最小
这个问题可以使用贪心算法来解决:
1. 从左往右扫描数字,如果当前数字比后面的数字大,则删去当前数字;
2. 删去 s 个数字后返回剩下的数字。
下面是 Python 代码实现:
```python
def remove_digits(n, s):
stack = []
for c in str(n):
while stack and s > 0 and stack[-1] > c:
stack.pop()
s -= 1
stack.append(c)
return int("".join(stack[:len(stack)-s]))
n = 198642
s = 4
result = remove_digits(n, s)
print(result) # 输出结果为 12
```
在这个算法中,我们使用了一个栈来保存当前的数字序列,同时不断地删去比栈顶元素大的数字,直到达到删去的数量 s 或者栈为空为止。最后,我们将栈中剩余的数字组成新的数字并返回结果。
阅读全文