402. Remove K Digits

402. Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note: The length of num is less than 10002 and will be ≥ k. The given num does not contain any leading zero. Example 1:

Input: num = "1432219", k = 3Output: "1219"Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the

Example 2:

Input: num = "10200", k = 1Output: "200"Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain

Example 3:

Input: num = "10", k = 2Output: "0"Explanation: Remove all the digits from the number and it is left with nothing which is 0.

思路： 有一个N为长的数字，用字符串来代替了，现在要求你将它删除K位，使得其得到的结果最小。 首先这是一个贪心问题，即我们可以将问题转化为，一个长度为N的数字里面，删除哪个数可以使得数变得最小，那么如何删除呢？ 1、因为数字开头不允许是0，当第二位是0的情况下下，这时候我们删除了第一位数，那么至少可以使数字小两个量级，而其他位置最多也就是小一个数量级，所以这种情况毫无疑问删除第一个，后面打头的0也自动消解 。 2、否则，我们从头开始找，找到第一个下降的数，如1234553，那么最后一个3前面的5就是，删除它得到的数字是最小的。

class Solution { public String removeKdigits(String num, int k) { int n; while(true){ n = num.length(); if(n <= k || n == 0) return "0"; if(k-- == 0) return num; if(num.charAt(1) == '0'){ int firstNotZero = 1; while(firstNotZero < num.length() && num.charAt(firstNotZero) == '0') firstNotZero ++; num = num.substring(firstNotZero); } else{ int startIndex = 0; while(startIndex < num.length() - 1 && num.charAt(startIndex) <= num.charAt(startIndex + 1)) startIndex ++; num = num.substring(0, startIndex) + num.substring(startIndex + 1); } } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。