資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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 次瀏覽
廣告