我正在嘗試一些 python 練習，我在其中一項測驗中達到了 5 秒超時。該函式預先填充了引數，我的任務是撰寫足夠快的代碼，以便在 5 秒的最大時間范圍內運行。
一條 kaiten 帶上一排有 N 個盤子，第 i 個盤子的型別是 Di 。有些菜肴可能彼此屬于同一型別。這N道菜會依次出現在你面前，每道菜只要不是你吃過的任何K道菜的型別，你都會吃掉。你吃得很快，所以你可以在下一道菜之前吃完一道菜。您選擇不吃的任何菜肴都會被其他人吃掉。確定你最終會吃多少道菜。
問題
代碼“有效”，但速度不夠快。
代碼
這里的想法是D[i]如果條目不在pastDishes串列中（可以是 K 大小），則添加條目。
from typing import List
# Write any import statements here
def getMaximumEatenDishCount(N: int, D: List[int], K: int) -> int:
# Write your code here
numDishes=0
pastDishes=[]
i=0
while (i<N):
if(D[i] not in pastDishes):
numDishes =1
pastDishes.append(D[i])
if len(pastDishes)>K:
pastDishes.pop(0)
i =1
return numDishes
有沒有更有效的方法？
uj5u.com熱心網友回復：
我們可以使用適當的資料結構嗎？如果是這樣：
資料結構
似乎是一個有序集，您必須將其縮小到K.
為了滿足這一點，如果超過 ( len(ordered_set) > K) 我們必須洗掉第一個n專案 where n = len(ordered_set) - K。理想情況下，洗掉將在O(1) 中執行。
但是，由于對集合的移除是無序的。我們首先將其轉換為串列。一個串列，其中包含按原始順序出現的唯一元素。
然后，我們可以從該有序串列中洗掉前 n 個元素。
例如：該函式lru回傳受容量限制限制的序列的最近最少使用的專案。seqk
要獲得長度，我們可以簡單地呼叫len()該 LRU 回傳值：
maximumEatenDishCount = len(lru(seq, k))
也可以看看：
- Python 有有序集嗎？
- 在python中獲得排序唯一串列的最快方法？
使用set唯一性（直到 Python 3.6）
def lru(seq, k):
return list(set(seq))[:k]
使用dict唯一性（從 Python 3.6 開始）
與上述相同的機制，但使用自 3.7 以來保留的dicts插入順序：
OrderedDict顯式使用
from collections import OrderedDict
def lru(seq, k):
return list(OrderedDict.fromkeys(seq).keys())[:k]
- 使用
dict工廠方法：
def lru(seq, k):
return list(dict.fromkeys(seq).keys())[:k]
- 使用字典理解：
def lru(seq, k):
return list({i:0 for i in seq}.keys())[:k]
也可以看看：
- 字典中鍵的順序
- 使用有序字典作為有序集
- 如何在保留順序的同時從串列中洗掉重復項？
- 真正的 Python：OrderedDict 與 Python 中的 dict：作業的正確工具
uj5u.com熱心網友回復：
經過多次反復試驗，我終于找到了一個足夠快的解決方案，可以通過您正在處理的難題中的最后一個案例。我以前的代碼非常簡潔和快速，但是，我終于找到了一個帶有工具的模塊，它可以讓這變得更快。它的collections原樣deque，但它被稱為Counter。
這是我的原始代碼：
def getMaximumEatenDishCount(N: int, D: list, K: int) -> int:
numDishes=lastMod=0
pastDishes=[0]*K
for Dval in D:
if Dval in pastDishes:continue
pastDishes[lastMod] = Dval
numDishes,lastMod = numDishes 1,(lastMod 1)%K
return numDishes
然后我像這樣實作了 Counter ：
from typing import List
# Write any import statements here
from collections import Counter
def getMaximumEatenDishCount(N: int, D: 'list[int]', K: int) -> int:
eatCount=lastMod = 0
pastDishes=[0]*K
eatenCounts = Counter({0:K})
for Dval in D:
if Dval in eatenCounts:continue
eatCount =1
eatenCounts[Dval] =1
val = pastDishes[lastMod]
if eatenCounts[val] <= 1: eatenCounts.pop(val)
else: eatenCounts[val] -= 1
pastDishes[lastMod]=Dval
lastMod = (lastMod 1)%K
return eatCount
最終效果很好。我相信你可以讓它不那么笨重，但這應該可以單獨作業。
我在做什么的一些解釋：
通常，while 回圈實際上比 for 回圈快一點，但是，如果我使用它，我需要多次訪問索引處的值，所以我認為在這種情況下使用 for 回圈實際上更好。您可以看到我還將串列初始化為它需要的最大大小，并且正在寫入值而不是彈出 追加，這節省了大量時間。此外，正如@outis 所指出的，通過將模運算子與變數結合使用，對我的代碼進行了另一項小改進，從而無需額外的 if 陳述句。Counter 本質上是一個特殊的 dict 物件，它持有一個 hashable 作為鍵，一個 int 作為值。我使用的事實是lastMod 是通常通過 list.pop(0) 訪問的索引，以訪問需要在計數器中洗掉或遞減的物件
請注意，在一行上分配多個變數不被認為是“pythonic”，但是我相信它會稍微提高性能，這就是我這樣做的原因。不過，這可以說是有爭議的，請參閱這篇文章。
如果其他人對我們試圖解決的問題感興趣，可以在這里找到：https : //www.facebookrecruiting.com/portal/coding_puzzles/?puzzle=958513514962507
uj5u.com熱心網友回復：
由于該問題是一個練習，因此不包括確切的解決方案。相反，描述了策略。
至少有幾種潛在的方法：
使用支持快速遏制測驗的資料結構（使用中的一組，如果沒有名稱），僅限于 K 最近吃的菜肴。幸運的是，由于
dict在較新的 Python 版本中保留了插入順序并且測驗密鑰包含速度很快，所以它符合要求。dict要求鍵是可散列的，但由于問題使用ints 表示菜肴型別，因此滿足該要求。使用這種方法，問題中的演算法保持不變。
與其檢查下一道菜型別是否是最后一道
K菜，不如檢查上一次吃下一道菜的時間是否K在當前盤子數之內。如果是，請跳過這道菜。如果沒有，就吃這道菜（更新下一道菜上次吃的時間記錄和當前菜數）。在資料結構方面，程式將需要記錄最后一次食用任何給定菜肴型別的時間（初始化-K-1以確保第一次遇到菜肴型別時會被食用；defaultdict這對此非常有用）。使用這種方法，演算法略有不同。代碼最終會稍微短一些，因為存盤菜肴資訊的資料結構沒有像原始演算法中那樣縮短。
在解決其他問題時，可能會應用后一種方法的兩個要點：
- 更廣泛地說，重新定義一個問題（例如從“這道菜在最后 K 道菜中吃”到“這道菜最后在 K 道菜中吃”）可以導致更簡單的方法。
- 更廣泛地說，有時使用翻轉的資料結構、交換鍵/索引和值會更有效。
方法和要點 2 都讓我想起了一個子字串搜索演算法（這個名字讓我忘記了），它使用針中的位置表（要搜索的字串）每個字符首次出現的位置（對于不在字串中的字符，表具有字串的長度）；當發生不匹配時，演算法使用表格將子字串與不匹配的字符對齊，然后從子字串的開頭開始檢查。它不是最有效的字串搜索演算法，但它比樸素演算法更簡單、更高效。它類似于跳過搜索演算法，但比跳過搜索演算法更簡單但效率較低，后者使用針中每個字符的每次出現的位置。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/404904.html
標籤：