程序以查找在Python中完全包含k个不同单词的子列表数量

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个单词列表和另一个值k。我们必须找到给定单词中的子列表的数量，以便有k个完全不同的单词。

因此，如果输入像单词= [“ Kolkata”，“ Delhi”，“ Delhi”，“ Kolkata”] k = 2，则输出将为5，因为以下子列表具有2个唯一的单词：[“ Kolkata” ，“ Delhi”]，[“ Delhi”，“ Kolkata”]，[“ Kolkata”，“ Delhi”，“ Delhi”]，[“ Delhi”，“ Delhi”，“ Kolkata”]，[“ Kolkata”，“德里”，“德里”，“加尔各答”]，但没有[“德里”，“德里”]，因为只有一个唯一的单词。

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

  • 定义一个功能work()。这将需要单词，k

  • n：=字数

  • 如果k等于0，则

    • 返回0

  • cnt：=新映射

  • 回答：= 0

  • l：= 0

  • 对于0到n范围内的r，执行

    • cnt [words [l]]：= cnt [words [l]]-1

    • 如果cnt [words [l]]与0相同，则

    • l：= l + 1

    • 从cnt删除单词[l]

    • cnt [word]：= 0

    • 字：=字[r]

    • 如果cnt中没有单词，则

    • cnt [word]：= cnt [word] + 1

    • 当cnt的大小> k时，

    • ans：= ans + r-l + 1

    • 返回ans

    从主方法返回（work(words, k)-work(words,k-1)）

    范例(Python)

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

    class Solution:
       def solve(self, words, k):
          return self.work(words, k) - self.work(words, k - 1)
       def work(self, words, k):
          n = len(words)
          if k == 0:
             return 0
          cnt = dict()
          ans = 0
          l = 0
          for r in range(n):
             word = words[r]
             if word not in cnt:
                cnt[word] = 0
             cnt[word] += 1
             while len(cnt) > k:
                cnt[words[l]] -= 1
                if cnt[words[l]] == 0:
                   del cnt[words[l]]
                l += 1
             ans += r - l + 1
          return ans
    ob = Solution()
    words = ["Kolkata", "Delhi", "Delhi", "Kolkata"]
    k = 2
    print(ob.solve(words, k))

    输入值

    ["Kolkata", "Delhi", "Delhi", "Kolkata"], 2

    输入值

    5

    以上是 程序以查找在Python中完全包含k个不同单词的子列表数量 的全部内容， 来源链接： utcz.com/z/340739.html

    回到顶部