Leetcode

这道题目是一道偏推理型的题,题目原始的信息如下:

Given a non-negative integernumrepresented as a string, removekdigits from the number so that the new number is the smallest possible.

Note:

The length ofnumis less than 10002 and will be ≥k.

The givennumdoes not contain any leading zero.

翻译过来就是从一个整数中移除掉K个数,使得留下来的数尽可能的大.例如输入是1432219,k=3,那么输出的结果就是1219,从1432219中移除掉432之后,留下来的数是最小的.

为了解决这个问题,我们首先将问题进行简化,得出规律验证进而解决问题.针对本道题,简化方法是如果只移除一个数得到最小值,那应该移除哪个数?我们很容易可以得出,如果从1432219中移除一个数,那么应该移除4,得到最小的数是132219,那么从132219中移除一个数呢?这个时候我们发现移除3,得到12219为最小.此时我们就可以发现两个规律:

1. 移除K个数得到最小值跟每次移除一个数,移除K次得到最小值结果是一样的

2. 从一个整数中移除一个数使得值最小,这个数满足从左侧起第一个大于相邻右侧的数.例如1432219中,4是左侧起第一个比右侧数大的一个数,所以需要移除.同理132219中3是第一个比右侧数大的.

下一步就是需要证明这种方法是正确的,假设一个数是,其中存在一个数满足

,我们需要证明从数中任意移除一个数,得到的最终结果总是大于移除本身.我们首先从小于的数中任意移除一个数,得到,移除,得到的数是两个数位数相同,但是在第k个位置,因此移除之后的数比较大.同理可证明移除之后的数大于移除.

因此题目的解法就是每次从原始的数中找到左侧起第一个大于相邻右侧的数删掉,重复k次,具体代码如下

#include 

#include

using namespace std;

class Solution {

public:

string removeKdigits(string num,int k) {

string reSult = num;

while(k >0){

if(k >= num.size()){

reSult ="0";

break;

}

else{

int lo = findMinLo(num);

num = removeLo(num, lo);

num = removeZeros(num);

reSult = num;

}

k--;

}

return reSult;

}

string removeZeros(string S){

int lo =0;

while(lo < S.size() && S[lo] =='0'){

lo++;

}

if(lo == S.size())return "0";

else{

return S.substr(lo);

}

}

string removeLo(string S,int lo){

if(lo +1 < S.size()){

return S.substr(0, lo) + S.substr(lo+1);

}

else{

return S.substr(0,lo);

}

}

int findMinLo(string S){

int pre=-1,lo=-1;

for(int i=0;i

int nowD = S[i] -'0';

if(nowD < pre){

lo = i-1;

break;

}

else{

pre=nowD;

}

}

if(lo == -1){

lo = S.size() -1;

}

return lo;

}

};

int main() {

Solution se;

cout<

return 0;

}