C语言给定一个以字符串表示的非负整数num,移除这个数中的k位数 字,使得剩下的数字最小。
时间: 2024-03-14 13:44:13 浏览: 104
这道题可以使用贪心算法来解决。具体做法是,从左往右遍历整个数字,如果当前数字比后面的数字大,则删除当前数字,直到删除的数字个数达到k或者已经遍历完整个数字。如果删除的数字个数还没有达到k,那么从后往前再删除剩余的数字,直到删除的数字个数达到k为止。
代码如下:
```c
#include <stdio.h>
#include <string.h>
void removeKdigits(char *num, int k) {
int len = strlen(num);
int top = 0;
for (int i = 0; i < len; i++) {
while (top > 0 && num[top - 1] > num[i] && k > 0) {
top--;
k--;
}
num[top++] = num[i];
}
while (k-- > 0) {
top--;
}
num[top] = '\0';
// 去除前导0
int i = 0;
while (num[i] == '0') {
i++;
}
if (i == top) {
num[0] = '0';
num[1] = '\0';
} else {
memmove(num, num + i, top - i + 1);
}
}
int main() {
char str[] = "1432219";
int k = 3;
removeKdigits(str, k);
printf("%s\n", str); // "1219"
return 0;
}
```
这里使用了一个栈来保存数字,每次遍历到一个数字时,如果栈顶的数字比当前数字大,则弹出栈顶的数字,直到栈顶的数字不再比当前数字大或者删除的数字个数达到k为止。然后将当前数字入栈。最后再从栈顶弹出剩余的数字,直到删除的数字个数达到k为止。注意需要去除前导0。
阅读全文