欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode第十七天栈之移掉K位数字402(多解:StringBuilder&&栈)

程序员文章站 2022-07-10 17:28:11
学有所思写这个题的时候我觉得这个题很简单,示例一的用例没有问题,到了用例二三就相继出问题!开始想着找一个数据结构,能够把它存下来,然后强转字符串输出,于是我用到栈,将栈中数字转为字符串并输出,输出结果:[1,2,1,9],答案并不理想。于是同学给我提醒用StringBuilder,可变的字符序列。可以删除、追加,我想我找到了我要的数据类型了!StringBuilder public static String removeKdigits(String num, int k) { ....

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();
    }

LeetCode第十七天栈之移掉K位数字402(多解:StringBuilder&&栈)
或者

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();
    }

LeetCode第十七天栈之移掉K位数字402(多解:StringBuilder&&栈)

单调栈+贪心(出自官网)

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