LeetCode第十七天栈之移掉K位数字402（多解：StringBuilder&&栈）

学有所思

写这个题的时候我觉得这个题很简单，示例一的用例没有问题，到了用例二三就相继出问题！
开始想着找一个数据结构，能够把它存下来，然后强转字符串输出，于是我用到栈，将栈中数字转为字符串并输出，输出结果：[1,2,1,9],答案并不理想。
于是同学给我提醒用StringBuilder，可变的字符序列。可以删除、追加，我想我找到了我要的数据类型了！

StringBuilder

    public static String removeKdigits(String num, int k) {
        if (num.length()<=k) return "0";
        StringBuilder s=new StringBuilder(num);
        for (int i=0;i<k;i++){
            //如果第一位大于第二位，删除第一位,否则删除第二位
            int index=0;
            for (int j=1;j<s.length()&&s.charAt(j)>=s.charAt(j-1);j++)
                index=j;
            s.deleteCharAt(index);
            //如果删除后的第一位是0，直接去掉0
        	while (s.length()>1&&s.charAt(0)=='0') 
        		s.deleteCharAt(0);
        }
        if(s.length()==0) return "0";
        return s.toString();
    }

或者

public static String removeKdigits(String num, int k) {
        if (num.length()<=k) return "0";
        java.lang.StringBuilder s=new java.lang.StringBuilder(num);
        for (int i=0;i<k;i++){
            //如果第一位大于第二位，删除第一位,否则删除第二位
            int index=0;
            for (int j=1;j<s.length()&&s.charAt(j)>=s.charAt(j-1);j++)
                index=j;
            s.deleteCharAt(index);
        }
        //如果删除后的第一位是0，直接去掉0
        while (s.length()>1&&s.charAt(0)=='0') s.deleteCharAt(0);
        return s.toString();
    }

单调栈+贪心（出自官网）

class Solution {
    public String removeKdigits(String num, int k) {
        Deque<Character> deque = new LinkedList<Character>();
        int length = num.length();
        for (int i = 0; i < length; ++i) {
            char digit = num.charAt(i);
            while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
                deque.pollLast();
                k--;
            }
            deque.offerLast(digit);
        }
        
        for (int i = 0; i < k; ++i) {
            deque.pollLast();
        }
        
        StringBuilder ret = new StringBuilder();
        boolean leadingZero = true;
        while (!deque.isEmpty()) {
            char digit = deque.pollFirst();
            if (leadingZero && digit == '0') {
                continue;
            }
            leadingZero = false;
            ret.append(digit);
        }
        return ret.length() == 0 ? "0" : ret.toString();
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/remove-k-digits/solution/yi-diao-kwei-shu-zi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

学以致用

适合的题用适合的数据结构

• StringBuilder：可变的字符序列。
• append(String str)/append(Char c)：字符串连接System.out.println("StringBuilder:"+strB.append("ch").append("111").append('c'));StringBuilder:ch111c
• toString()：返回一个与构建起或缓冲器内容相同的字符串System.out.println("String:"+strB.toString());String:ch111c
• setCharAt(int i, char c)：将第 i 个代码单元设置为 c（可以理解为替换）strB.setCharAt(2, 'd');chd11c
• 替换等同于strB.replace(2,3,"")左开右闭
• insert(int offset, String str)/insert(int offset, Char c)：在指定位置之前插入字符(串)System.out.println("StringBuilder.insertString:"+ strB.insert(2, "LS"));StringBuilder.insert:String:chLSd11c
• delete(int startIndex,int endIndex)：删除起始位置（含）到结尾位置（不含）之间的字符串System.out.println("StringBuilder.delete:"+ strB.delete(2, 4));chSd11c

本文地址：https://blog.csdn.net/ss977/article/details/110878520