题目描述:
给定一个十进制的正整数 number,该正整数有 N 位,选择从里面去掉 K 个数字,希望留下来的数字组成的正整数最小。
输入描述:
输入为两个数字,第一个数字是一个正整数 number, 1<=length(number)<=50000。第二个数字是希望去掉的数字数量 cnt, 并且 1<=cnt<=length(number)。
输出描述:
输出保留下来的结果。
示例:
输入
124682385 2
输出
1242385
思路:
删除 K 个,可以使用贪心算法,每次删除 1 个。
那么每次删除哪一个呢?
如果 N>=2 的话,我们可以将该整数写成 XabY 的形式,其中 X 和 Y 分别是前缀和后缀,并且其长度可以为 0。因为 a 和 b 相邻并且 a 在 b 左边,所以删除一个的话,剩下的数就变成了 XaY 或 XbY 了。分下面两种情况讨论:
(1)若 a!=b 的话,为了使剩下的数最小,我们倾向于删除 a 和 b 中较大的那个数
(2)若 a==b 的话,删除 a 和删除 b 是等价的,所以我们就跳过 a,去比较 b 和它的后继,这就转变成了问题(1)了。
综上所述:
如果要使的剩下的数字最小,可以每次从左向右扫描,找出连续的非严格递增串,删除该串的最后一个数字。
如果要使剩下的数字最大,可以每次从左向右扫描,找出连续的非严格递减串,删除该串的最后一个数字。
下面给出求剩下数字最小的 C++ 代码:
string deleteKNumbers(string &str, int k)
{
string::iterator start;
bool flag;
for(int i = k; i > 0; --i)
{
flag = 0;
for(start = str.begin(); start < str.end() - 1; ++start)
{
// 每次删除第一个比下一个数字大的数
if(*start > *(start + 1))
{
str.erase(start);
flag = 1;
break;
}
}
//如果所有数字递增,则删除最后几个数字直接返回
if(!flag)
{
str.erase(str.end() - i, str.end());
break;
}
}
return str;
}
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于