在Python中找出一个列表中每个分区的大小,其中每个字母最多只出现一次的程序

在Python中找出一个列表中每个分区的大小,其中每个字母最多只出现一次的程序

假设我们有一个小写字符串s,我们可以将s分成尽可能多的部分,使得每个字母最多只出现在一部分中,并将分区的大小作为列表查找。

因此,如果输入是s =“momoplaykae”,那么输出将是[4, 1, 1, 4, 1],因为字符串被分成 [“momo”,“p”,“l”,“ ayka”,“e”]。

为了解决这个问题,我们将遵循以下步骤-

  • count:包含s中字符及其出现次数的映射

  • out:一个新的列表,stk:一个空堆栈

  • 长度:0

  • 对于s中的每个字符,执行以下操作

    • count [char]:=count [char] -1

    • 长度:=长度+1

    • while count [char]与0不同或stk不为空

      • 如果count [char]不同于0,则

      • 将char推入stk中

      • 退出循环

      • 如果stk不为空且count [stk顶部]与0相同,则

      • 从stk弹出

      • 否则,

      • 退出循环

    • 如果stk为空并且count [char]与0相同,则

      • 在out后插入长度

      • 长度:= 0

  • 返回out

更多Python相关文章,请阅读:Python 教程

示例

让我们看下面的实现,以更好地理解-

from collections import Counter
class Solution:
   def solve(self, s):
      count = Counter(s)
      out = []
      stk = []
      length = 0
      for char in s:
         count[char] -= 1
         length += 1
         while count[char] != 0 or stk:
            if count[char] != 0:
               stk.append(char)
               break
            if stk and count[stk[-1]] == 0:
               stk.pop()
            else:
               break
            if not stk and count[char] == 0:
               out += [length]
               length = 0
         return out
ob = Solution()
s = "momoplaykae"
print(ob.solve(s))

输入

"momoplaykae"

输出

[4, 1, 1, 4, 1]

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程