Remove K Digits

2019-01-18  本文已影响0人  想跳舞的兔子

1.题目描述(难度Medium)

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.

2.题目分析

题目要求是在给定的数字字符串中,删掉k个字符,使剩下的字符串的数最小。其中字符串的原始顺序是不变的,分析如何从前往后删除字符是我们求解的关键。这题反向思维可能更便于处理所有字符。
解题思路1:
删掉k个字符,意味着,
最小的第一个字符,是在0:N-k+1中选,其索引为index0,k=k-1
最小的第二个字符,是在index0+1:N-k+1中选,其索引为index1,k=k-1
...
如此,直到k=0.我们把剩下的字符串追加即可。
这种思路也可以倒过来,我们要留N-k个字符。即令k=N-k
思路同上,只是当k=0时,我们就得到我们需要的字符,不需要额外追加了。

解题思路2:
我们可以从前往后遍历数字,并用一个栈辅助,每次来一个数就循环判断 栈里最后一位的是否>新来的数字,是则出栈且k=k-1, 不是则继续遍历下一个数字,当k=0的时候,说明我们已经把可以移出去的数字都移出去了。剩下的数字就是我们要的。
这里要注意的一个边界情况,可能数字有部分是按照从小到大的顺序排列,这个时候k不为零,我们只要取[:-k]即可

3.解题过程

Begin(算法开始)
输入 长度为N的数字字符串num,和删除的个数k
IF len(num) == k: return '0'
定义输出列表
遍历字符串:
  while k and out and 列表末端字符>当前字符:
    末端出列
    k-=1
  当前字符加入列表
当k不为零的时候表示当前列表中前[:-k]使我们要的结果
当k为零时,列表中所有的字符即为我们要串联的数字
返回连接列表后的结果
End (算法结束)

Begin(算法开始)
输入 长度为N的数字字符串num,和删除的个数k
IF len(num) == k: return '0'
剩余的字符串个数为res=N-k
ind = 0
while res>0://尚没有凑够我们需要的字数
  求出num[ind:N-res+1]之间最小的数 cur_min并把其加入输出字 符串out,并记录其在num中的index
  ind = ind+index+1,res-=1
 重复上述直到res==0
return str(int(out))
End (算法结束)

具体代码(python)已对应实现,但是测试用例代码还没完善,如上述思路有不足之处请批评指正。

上一篇下一篇

猜你喜欢

热点阅读