Leetcode 402. Remove K Digits 删除K个数字 解题报告
1 解题思想
题目是这样的,有一个N为长的数字,用字符串来代替了,现在要求你将它删除K位,使得其得到的结果最小
分析: 首先这是一个贪心问题,即我们可以将问题转化为,一个长度为N的数字里面,删除哪个数可以使得数变得最小: 那么如何删除呢? 1、因为数字开头不允许是0,当第二位是0的情况下下,这时候我们删除了第一位数,那么至少可以使数字小两个量级,而其他位置最多也就是小一个数量级,所以这种情况毫无疑问删除第一个,后面打头的0也自动消解 2、否则,我们从头开始找,找到第一个下降的数,如 1234553,那么最后一个3前面的5就是,删除它得到的数字是最小的。
2 原题
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 105 and will be ≥ k. The given num does not contain any leading zero. Example 1: Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest. Example 2: Input: num = "10200", k = 1 Output: "200" Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes. Example 3: Input: num = "10", k = 2 Output: "0" Explanation: Remove all the digits from the number and it is left with nothing which is 0.
3 AC解
public class Solution { /** * 这是一个非常简单的问题,贪心解决法 * 即 removeKdigits(num,k) = removeKdigits(removeKdigits(num,1),k-1) * 进行最多K轮的删除,每次从头开始寻找一位删除: * 1、要么第二位是0,这样相当于至少删了两位,很值得,必须这么做 * 2、不然,找到第一个出现下降转折的位置 删除 * */ 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); } } } }