给定一个以字符串表示的非负整数num,移除这个数中的k位数 字,使得剩下的数字最小。 注意: num 的长度小于10002且≥k。num不会包含任何前导零。按照示例 : 输入:num=“1432219",k=3 输出:编写c++代码
时间: 2024-03-10 11:46:53 浏览: 83
n位正整数去掉k位数字得到最小数(回溯法C++代码)
这道题可以使用贪心算法来解决。具体思路为:从左往右扫描数字,如果当前数字比后面的数字大,则删除当前数字,直到删除 k 个数字或者扫描到最后一个数字。删除数字时需要注意,如果当前数字是0,则不能删除它,因为删除它后可能会使得剩余数字的开头出现前导零。
C++代码如下:
```c++
#include <iostream>
#include <string>
using namespace std;
string removeKdigits(string num, int k) {
int n = num.size();
string res = "";
for (int i = 0; i < n; i++) {
while (k > 0 && !res.empty() && res.back() > num[i]) {
res.pop_back();
k--;
}
if (num[i] != '0' || !res.empty()) res.push_back(num[i]);
}
while (k > 0 && !res.empty()) {
res.pop_back();
k--;
}
return res.empty() ? "0" : res;
}
int main() {
string num = "1432219";
int k = 3;
cout << removeKdigits(num, k) << endl;
return 0;
}
```
阅读全文