一, 题目: 移除 K 位数字
给定一个以字符串表示的非负整数 num, 移除这个数中的 k 位数字, 使得剩下的数字最小.
注意:
num 的长度小于 10002 且 ≥ k.
num 不会包含任何前导零.
示例 1 :
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219.
示例 2 :
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零.
示例 3 :
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字, 剩余为空就是 0.
思路 1:
采用一个栈: 若栈最后一个元素比 num 中当前元素大, 则存入栈中, 否则将栈中最后一个元素删除. 当 K==0 时停止.
代码 1:
- def removeKdigits(self, num, k):
- """
- :type num: str
- :type k: int
- :rtype: str
- """
- #采用栈
- if not num:
- return None
- if k == 0:
- return num
- stack =[]
- res = ""
- for n in num:
- while k>0 and stack and int(stack[-1])> int(n):
- k -= 1
- stack.pop()
- if n.isdigit():
- stack.append(n)
- print(stack)
- res = "".join(stack)
- if k>0:
- m = len(stack)-k
- res = "".join(stack[:m])
- print(res)
- return str(int(res)) if res else "0"
思路 2:
若 num 前一个元素比后一个元素大, 则删除. 直到 k==0
代码 2:
- def removeKdigits(self, num, k):
- if k>len(num)-1:
- return "0"
- i = 0
- while i<len(num)-1 and k>0:
- if int(num[i])> int(num[i+1]):
- num = num[:i]+num[i+1:]
- if i>0:
- i-=1
- k-=1
- else:
- i+=1
- num = num[:len(num)-k]
- return str(int(num))
来源: http://www.bubuko.com/infodetail-2843159.html