给定一个正整数,去掉其中的k位数,剩下的数字按原先次序排列,如何让生成的数最小。
时间: 2023-05-24 18:06:15 浏览: 107
这是一个经典的贪心算法问题,可以使用单调栈求解。
具体做法如下:
1. 从左往右遍历原数的每一位,将其加入栈中,同时比较栈顶元素和当前元素的大小,如果栈顶元素大于当前元素且还没有删够k个数字,则弹出栈顶元素,重复该步骤。
2. 如果已经删够了k个数字或者遍历完原数的所有数字,则剩下的数字就是最终的结果。如果此时栈为空,则结果为0。
3. 去除结果前导0,输出。
代码实现如下:
```python
def remove_k_digits(num: str, k: int) -> str:
stack = []
# 遍历每一位数字
for n in num:
# 如果栈不为空且还可以删数且当前数字小于栈顶元素,弹出栈顶元素
while stack and k > 0 and n < stack[-1]:
stack.pop()
k -= 1
# 将当前数字加入栈中
stack.append(n)
# 如果还需要删数,则从栈顶依次删除数字
while k > 0:
stack.pop()
k -= 1
# 去除前导0,得到最终结果
res = "".join(stack).lstrip("0")
return res if res else "0"
```
时间复杂度为O(n),其中n为原数的位数。
相关问题
给定一个正整数,去掉其中的k位数,剩下的数字按原先次序排列,如何让生成的数最小。使用Java实现
可以使用贪心算法来解决这个问题。具体步骤如下:
1. 将给定的正整数转换为字符串,便于按位处理。
2. 从左到右遍历字符串中的每一位数字,如果当前数字比下一位数字大,则删除当前数字,k减1,直到k为0或者已经遍历完所有数字。
3. 如果k仍然大于0,说明需要删除更多数字才能满足要求,此时从右向左删除剩余的k位数字。
4. 将剩余的数字按原先次序排列,即为最小的生成数。
以下是Java实现代码:
```java
public static String removeKDigits(int num, int k) {
// 将数字转换为字符串
String numStr = String.valueOf(num);
int n = numStr.length();
// 如果需要删除的数字个数超过字符串长度,则直接返回空字符串
if (k >= n) {
return "";
}
char[] stack = new char[n];
int top = 0;
// 从左到右遍历字符串中的每一位数字
for (int i = 0; i < n; i++) {
// 当前数字比下一位数字大,则删除当前数字
while (k > 0 && top > 0 && stack[top - 1] > numStr.charAt(i)) {
top--;
k--;
}
// 将当前数字加入栈中
stack[top++] = numStr.charAt(i);
}
// 如果仍然有需要删除的数字,则从右向左删除剩余的数字
while (k > 0 && top > 0) {
top--;
k--;
}
// 将剩余的数字按原先次序排列,即为最小的生成数
StringBuilder sb = new StringBuilder();
boolean leadingZero = true;
for (int i = 0; i < top; i++) {
if (leadingZero && stack[i] == '0') {
continue;
}
leadingZero = false;
sb.append(stack[i]);
}
// 如果字符串为空,则返回0
if (sb.length() == 0) {
return "0";
}
return sb.toString();
}
```
可以使用以下代码进行测试:
```java
public static void main(String[] args) {
int num = 1432219;
int k = 3;
System.out.println(removeKDigits(num, k)); // 输出结果为:1219
}
```
使用Java实现给定一个正整数,去掉其中的k位数,剩下的数字按原先次序排列,如何让生成的数最小。
算法思路:
首先我们可以观察到一个结论,即要想让生成的数最小,就应当尽可能让高位的数小,因为高位数的权值更高。而为了让高位数最小,我们需要尽可能地保留低位数,因为低位数的权值越小。
所以,我们可以使用贪心算法来解决这个问题,具体思路如下:
- 从左往右遍历原数中的每个数字,依次将它们加入到生成的新数中。
- 对于当前加入到新数中的数字,如果它比前面已经加入到新数中的数字大,那么就应当将前面的数字删除掉,直到新数中前面的数字都小于等于当前数字,或者已经删掉了k个数字(因为只能删掉k个数字)。
- 如果已经删掉了k个数字,就将当前数字都加入到新数中,剩下的数字全部舍弃。
- 如果遍历完整个原数,新数中依然没有k位数字,就从后往前,将原数中剩下的数字依次加入到新数中,直到新数中的位数为k为止。
在实现上,我们可以使用一个栈来保存新数中已加入的数字,这样在进行数字删除时,只需要将栈中的数字弹出即可。栈中的数字按照由小到大的顺序排列,这样在加入新数字时,比栈顶数字小的数字就可以直接加入,因为它们肯定已经在新数的前面了。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)