Python程序：查找包含恰好k个不同单词的子列表

假设我们有一个单词列表和另一个值k。我们需要找到给定单词中包含恰好k个不同单词的子列表的数量。

因此，如果输入类似于 words = ["Kolkata", "Delhi", "Delhi", "Kolkata"] k = 2，则输出将为5，因为以下子列表具有2个唯一单词：["Kolkata", "Delhi"], ["Delhi", "Kolkata"],["Kolkata","Delhi","Delhi"], ["Delhi","Delhi","Kolkata"], ["Kolkata","Delhi","Delhi","Kolkata"], 但不包括["Delhi","Delhi"]，因为它只有一个唯一单词。

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

  • 定义一个函数 work()。它将接收 words 和 k 作为参数。
  • n := words 的大小
  • 如果 k 等于 0，则
    • 返回 0
  • cnt := 一个新的映射
  • ans := 0
  • l := 0
  • 对于 r 从 0 到 n，执行以下操作：
    • word := words[r]
    • 如果 cnt 中不存在 word，则
      • cnt[word] := 0
    • cnt[word] := cnt[word] + 1
    • 当 cnt 的大小 > k 时，执行以下操作：
      • cnt[words[l]] := cnt[words[l]] - 1
      • 如果 cnt[words[l]] 等于 0，则
        • 从 cnt 中移除 words[l]
      • l := l + 1
    • 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

更新于: 2020年12月12日

76 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告