博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode 402. 移掉K位数字 java题解
阅读量:749 次
发布时间:2019-03-23

本文共 1223 字,大约阅读时间需要 4 分钟。

题目

在这里插入图片描述

分析

遍历每个数字,如果数字小于相邻数字则丢弃相邻数字。

如果输入数字有序,为了必须丢弃k个,要丢弃末尾k个返回。

复杂度

时间复杂度:虽然内层还有一个 while 循环,但是由于每个数字最多仅会入栈出栈一次,因此时间复杂度仍然为 O(N),其中 N 为数字长度。

空间复杂度:我们使用了额外的栈来存储数字,因此空间复杂度为 O(N),其中 N 为数字长度。

代码

class Solution {
public String removeKdigits(String num, int k) {
if(num==null||num.length()==0) return ""; if(k==0) return num; if(k==num.length()) return "0"; int len=num.length()-k;//最终的长度 Deque
stack=new LinkedList<>(); for(int i=0;i
c&&k>0){
stack.removeLast(); k--; } stack.addLast(c); } StringBuilder sb=new StringBuilder(len); int flag=0;//去除前导0 for(Character c:stack){
//后面的不需要了,跳出循环 if(len==0) break; //需要数量-1 len--; //是前导0 if(flag==0&&c=='0') continue; //不会是前导0了 if(c!='0') flag=1; //加入结果 sb.append(c.charValue()); } //字符串为空时,返回0 String res=sb.toString(); if(res.length()==0) return "0"; else return res; }}

结果

在这里插入图片描述

转载地址:http://tgczk.baihongyu.com/

你可能感兴趣的文章