题目
题目描述
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 = 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.
题解
题目意思就是给出一个数字然后去掉其中k个数得出一个最小的数字。
对于一串(n)上升数字来说如果去掉一位数字来得到最小的(n-1)数字去掉最后一位就是他的最小的(n-1)数，
123456789 =>12345678
而 题目输入的 num我们可以看做多个上升序列合成的序列然后我们从i=0开始对i+1判断能否和 i组成上升序列（当num[i]==num[i+1]） 我们也认为能组成上升序列，当遇到i与i+1不能组成上升序列时 remove（i） 并且 i-- 再次判断新的i与i+1能不能组成上升序列 ， 下面数列模拟
1234545678 >123445678 >12344567
代码
fun removeKdigits(num: String, k: Int): String {
var result = ""
var nums: ArrayList<Char> = num.toCollection(arrayListOf())
var index = 0
var count = 0
while (count < k && index + 1 < nums.size) {
if (nums[index] == '0' && index == 0) {
nums.removeAt(index)
continue
}
if (nums[index + 1] < nums[index]) {
nums.removeAt(index)
index--
if (index < 0)
index = 0
count++
} else {
index++
}
}
var couut = if (k - count > nums.size) {
nums.size
} else {
k - count
}
result = nums.joinToString("").substring(0, nums.size - couut)
var cout = -1
for (i in result.indices) {
if (result[i] != '0') {
cout = i
break
}
}
if (cout == -1) {
cout = result.length
}
result = if (cout == result.length)
""
else
result.substring(cout, result.length)
if (result == "")
result = "0"
println(result)
return result
}
提交结果
