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