吴良超的学习笔记

LeetCode 解题报告(402,316,321)--删除字符串k个字符使剩余字符串取最值

本文主要讲述如何解决这一类问题:给定一个含有数字或英文字母的字符串,从中删除k个字符,使得剩下的字符取得最小值或最大值。数字的大小的比较容易理解,而字母的大小则是按照其ASCII码来排列,如’abc’>’abd’。

下面以 LeetCode 上的几道题目为例进行讲解:
402. Remove K Digits
316. Remove Duplicate Letters
321. Create Maximum Number

解决这类题目的关键点是借助栈这种数据结构,遍历给出的字符串,将当前元素与栈顶元素比较大小,从而决定是否要将当前元素出栈,最后栈内剩余元素就是所需结果。这只是大致的过程,具体的步骤需要根据题目的具体要求。下面以上面的题目为例讲解

402. Remove K Digits 这个题目要求去掉给定字符串(全是数字)中的 k 个字符,使得剩余的字符串表示的数字最小。根据我们上面说到的大致流程,这道题目的解决步骤如下:

1.创建一个栈,以及记录当前已经删除的字符数量的计数器
2.对于字符串中的每个字符,记为当前字符,先将其与栈顶元素比较(假如栈不为空),若当前字符小于栈顶元素,则将栈顶元素出栈,将计数器加一,重复该操作直到栈为空栈顶元素小于当前元素计数器等于k,然后将当前元素入栈

具体的 python 代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def removeKdigits(self, num, k):
"""
:type num: str
:type k: int
:rtype: str
"""

stack = []
remain = len(num) - k
for dig in num:
while k and stack and stack[-1] > dig:
stack.pop()
k -= 1
stack.append(dig)
return ''.join(stack[:remain]).lstrip('0') or '0'

最后return语句之所以要选取前len(num) - k个字符是因为 result 中可能会有多余这个数目的字符,如对于从小到大排列的字符串就会出现这种情况,另外还需要处理掉前缀0以及当结果为空的时候返回 ‘0’

316. Remove Duplicate Letters 的要求跟 402. Remove K Digits 类似,只是这次要求删除的是字母,而且每个字符要求出现一次且只能出现一次

解决的思路跟上面的一样,只是因为要求每个字符出现且只出现一次,在入栈和出栈的时候需要特殊的限制条件。具体步骤入下

1.创建一个栈,记录每个字符在字符串中出现的次数的table
2.对于字符串中的每个字符,先判断其是否已在栈内,若已在栈内,将table中对应该字符的计数减去1,然后跳到字符串的下一字符;若不在栈内,栈顶元素大于当前字符且table内剩余的栈顶元素的个数大于1时,将栈顶元素出栈,重复该操作直到栈为空栈顶元素小于当前元素,然后将当前字符入栈

实现的 python 代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""

result, stored, count = [], set(), {}
for char in s:
count.setdefault(char, 0)
count[char] += 1
for char in s:
if char in stored:
count[char] -= 1
continue
else:
while result and result[-1] > char and count[result[-1]] > 1:
count[result[-1]] -= 1
stored.remove(result.pop())
stored.add(char)
result.append(char)
return ''.join(result)

321. Create Maximum Number 题目要求与上面两题相比不是相似性不高,但是也是利用这种思想的,题目要求从两个数组 nums1nums2 中共选出k个数字,从而使得这k个数字组成的数最大。

解决方法就是先从 nums1 中选出 i 个数(0 <= i <= k)使得这i个数组成的数字最大,然后从 nums2 中选出 k-i 个数,同样使得这 k-i 个数组成的数字最大,最后将从两个数组中抽出的最大数字合并起来。

实现的代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def maxNumber(self, nums1, nums2, k):
"""
:type nums1: List[int]
:type nums2: List[int]
:type k: int
:rtype: List[int]
"""

return max(self.merge(self.single_max(nums1, i), self.single_max(nums2, k-i)) for i in xrange(k+1) if i <= len(nums1) and (k-i) <= len(nums2))


def single_max(self, nums, k):
drop = len(nums) - k
stack = []
for digit in nums:
while drop and stack and stack[-1] < digit:
stack.pop()
drop -= 1
stack.append(digit)
return stack[:k]

def merge(self, nums1, nums2):
return [max(nums1,nums2).pop(0) for _ in xrange(len(nums1)+len(nums2))]

上面的代码中 max(num1, num2)中的 nums1nums2是两个数组,比较的时候回比较两个数组的第一个元素,然后返回第一个元素较大的数组,若第一个元素相等,则比较第二个元素,依此类推;pop(0)则是删除并返回下标为0的元素,也就是第一个元素。通过这些语法可以简化代码