C++贪心算法求解删除k位数字后的最小整数

本文将介绍如何使用C++中的贪心算法，解决从给定整数中删除k位数字后，如何获得最小的新整数。

问题描述

给定一个十进制正整数n (0 < n < 1000000000)，每个数位上的数字均不为0。n的位数为m。要求从m位中删除k位 (0 < k < m)，并求出生成的新整数的最小值。

例如: n = 9128456, k = 2，则生成的新整数最小为 12456。

算法思路

解决这个问题可以使用贪心算法。其基本思想是从高位到低位遍历数字n，每次删除一位数字。为了保证最终结果最小，我们每次都选择删除一位能够使得剩余数字序列保持字典序最小的数字。

具体步骤如下：

从左到右遍历数字n的每一位数字。2. 如果当前数字大于它右边的数字，则删除当前数字。3. 为了避免删除后索引越界，删除数字后需要将指针回退一位。4. 重复步骤1-3，直到删除k个数字。5. 如果删除k个数字后，还有数字剩余，则将剩余数字连接起来作为最终结果。6. 如果在删除k个数字之前，就已经遍历完所有数字，则说明剩余的数字都比它右边的数字小，此时需要从数字n的末尾开始删除剩余的k个数字。

代码实现

以下是使用C++语言实现上述算法的代码示例：cpp#include #include #include using namespace std;

string removeDigits(string n, int k) { int len = n.length(); // 特殊情况处理，如果需要删除的位数k等于整数n的位数m，则直接返回0 if (k == len) { return '0'; } // 使用贪心算法，从左往右扫描数字n，删除比右边数字大的数字 int i = 0; while (k > 0 && i < len - 1) { // 如果当前数字大于下一个数字，则删除当前数字 if (n[i] > n[i+1]) { n.erase(n.begin() + i); k--; // 回退一步，重新检查当前数字 if (i > 0) { i--; } } else { // 否则，继续扫描下一个数字 i++; } } // 如果还有剩余的需要删除的位数k，继续从右往左删除剩余的数字 while (k > 0) { n.erase(n.end() - 1); k--; } // 删除前导0 n.erase(0, n.find_first_not_of('0')); // 如果字符串为空，返回'0' return n.empty() ? '0' : n;}

int main() { int t; cin >> t; while (t--) { string n; int k; cin >> n >> k; string result = removeDigits(n, k); cout << result << endl; } return 0;}

示例

输入：

29128456 21444 3

输出：

124561

总结

本文介绍了如何使用C++中的贪心算法解决从给定整数中删除k位数字后，得到最小新整数的问题，并提供了详细的代码示例和解释。该算法简单易懂，并且能够有效地解决问题。