402. Remove K Digits

2018年4月12日 下午3:54

Remove K Digits - LeetCode

1. 我错误的解法是：想通过if-else将所有的情况罗列出来。那么此时的问题时：有哪些特殊情况需要考虑？每种情况下如何进行pop和push操作。这样会在和判断中重复pop和push操作，这就是我的代码长的原因。
2. 新的思考方式是：既然情况太多，还很有可能落下，那么干脆就不罗列了。想这么一个问题，拿到一个数我们只会pop和push操作，那么何时pop？何时push？pop，push分别集中在一起，而不是像上面的解法一样是分散的。

下面这个程序从头到尾都没有考虑：

1. 1572 2
   1. 是：
      1. 1，5，7———pop
      2. 1，5，————pop
      3. 1，
      4. 1，2
   2. 不是：
      1. 1，5，7———pop
      2. 1，5，
      3. 1，5，2

         class Solution {
         public:
             std::string removeKdigits(std::string num, int k) {
                 //栈
                 std::vector<int> S;
                 int i_k = 0;
                 std::string result="";
         
                 //扫描进行对比,入栈
                 for(int i = 0; i < num.length(); i++){
         //            if(S.size() >= (num.size()-k)) break;//12345
                     
                     if(i_k < k  ){//5,4,3,2,1
                         
                         if(  S.empty()){
                             S.push_back(num[i]-'0');
                         }
                         else if(S[S.size()-1] <= num[i]-'0' ){//=号 1223
                             S.push_back(num[i]-'0');
                         }
                         else if(S[S.size()-1] > num[i]-'0'){
                             S.pop_back();
                             if(!S.empty()||(num[i]-'0')!=0){//100200
                                 S.push_back(num[i]-'0');
                             }
                             i_k++;
                         }
                     }
                     else{
                         if(!S.empty()||(num[i]-'0')!=0){//100200
                             S.push_back(num[i]-'0');
                         }
                     }
                 }
         
                 while(S.size() > (num.size()-k)){
                     int back = S.back();
                     S.pop_back();
                     if(S.back() > back){
                         S.pop_back();
                         S.push_back(back);
                     }
                 }
                 //返回字符串
                 for(int i = 0; i < S.size(); i++){
                     result.append(1,'0'+S[i]);//这里不可以是""
                 }
         
                 //判空
                 if(result == ""){
                     result = "0";
                 }
         
                 return result;
             }
         };

ac的

class Solution {
public:
    std::string removeKdigits(std::string num, int k) {
        //栈
        std::vector<int> S;
        std::string result="";
        
        //扫描进行对比,入栈
        for(int i = 0; i < num.length(); i++){
            //这时拿上一个数，只有是否进入？进入到哪个位置？
            int number = (num[i]-'0') ;
            //定位置
            while(!S.empty() && k > 0  && number < S.back()){
                S.pop_back();
                k--;
            }
            
            // 何时入栈
            if( number !=0 || !S.empty()){
                S.push_back(num[i]-'0');
            }
            
        }
        
        while(!S.empty() && k>0){
            S.pop_back();
            k--;
        }
        //返回字符串
        for(int i = 0; i < S.size(); i++){
            result.append(1,'0'+S[i]);//这里不可以是""
        }
        
        //判空
        if(result == ""){
            result = "0";
        }
        
        return result;
    }
};