LC402.移动K位数字leetcode,数据结构,算法Milan1in的博客-

注意:

num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。

示例 1 :

输入: num = “1432219”, k = 3
输出: “1219”
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例 2 :

输入: num = “10200”, k = 1
输出: “200”
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 :

输入: num = “10”, k = 2
输出: “0”
解释: 从原数字移除所有的数字，剩余为空就是0。

解题思路1：

1、贪心策略。

2、题目要求的是移除k个数字，我的做法是在合适的范围提取num.size()-k个数字，因为移除的话用贪心做不了，你每次移除最大或者最小的数字答案都不正确。

1432219 移除最大的：1221 ；移除最小的：4329（更不对）。

3、合适的范围是多少呢？比如：num = “1432219”, k = 3；就是找7-3，4个数。第一次你要从1432里面去找，后面的219三位不能动，因为你找了一位，要保证还有三位，凑够四位。

4、关键是找到后怎么处理。如下图：1432，找到1之后，保存1，并截取1之后的数：432219。

5、在合适的范围边查找边截取，最后就能够得到正确答案了，不过时间复杂度和空间复杂度过高。

代码如下1：

string removeKdigits(string num, int k) { if(num.size()<=k){//长度小于等于k则直接返回“0” return "0"; }         string s;         k=num.size()-k; while(k--){//选取num.size()-k个 char ch='9'; int n=0;//位置，方便截取 for(int i=0;i<num.size()-k;i++){//合适的范围 if(num[i]<ch){//寻找最小                 ch=num[i];                 n=i; } }            num=num.substr(n+1);//截取             s+=ch;//加上 } int i=0; while(s[i]=='0'){//开头的清零    i++; }   s=s.substr(i); if(s.size()==0){//清完0可能位空，所以这里要返回0 return "0"; } return s; } 

解题思路2：

1、上面的方法，在合适的范围循环选择最小然后提取，可以用栈来提高效率。

2、循环判断num的每一个字符，判断栈顶的元素是否比该字符大，是的话就出栈，否则就进栈，有种将字符串从小到大排序的感觉。

3、注意出栈就是题目中的删除，出栈一次k–，所以不会出现将字符串完全从小到大排序，这取决于k是否足够大，当k的次数用完了，后面的字符就算比栈顶的字符小也没办法出栈。

4、用栈来做有一种特殊情况，就是字符串已经排好序了，比如：num = “123456789”, k = 3；这样就没办法出栈了，我们得到的字符串超长了，所以要在后面判断字符串的长度是否过长，过长的话就去掉后面的k个字符，“123456789”，去掉后3个，剩下“123456”，最小。

5、用栈做需要将字符串拿出来再逆序，因为先进后出，当然也要判断最高位是否为0，还有是否全为0的情况。

代码如下2：

string removeKdigits(string num, int k) { if(num.size()<=k){//长度小于等于k则直接返回“0” return "0"; }         stack<char>s;         s.push(num[0]); for(int i=1;i<num.size();i++){ while(!s.empty()&&k!=0&&s.top()>num[i]){ //栈空或者k的次数用完了或者栈顶最小则不用进入while            s.pop();//出栈            k--;//次数减一 }     s.push(num[i]); }   string ss; while(!s.empty()){//提取字符    ss+=s.top();    s.pop(); } reverse(ss.begin(),ss.end());//逆序 int i=0; while(ss[i]=='0'){//跳过最高位为0    i++; }   ss=ss.substr(i); if(ss.size()==0){//全为0 return "0"; } if(ss.size()>n){//长度过长 return ss.substr(0,n); } return ss; }