[問題]算法 k distinct letters suhang PTT批踢踢實業坊

[問題]算法 k distinct letters

作者: suhang (suhang) 2018-03-13 07:10:36

https://imgur.com/a/2GAU3
my solution
https://repl.it/@shih_hsuanhsu/KDistinctCharacter
def KDistinctCharacter3
def KDistinctCharacter2
兩個方法應該都正確，但是複雜度為O(nk)
網路上高手說可以做到O(n)
我試著又寫了 KDistinctCharacter
但是我想不透該怎麼做
求助!
謝謝

作者: djshen (djshen) 2018-03-13 10:00:00

想想看iterate的時候哪些東西可以不用重算

作者: Jeffrey11061 (Jeff) 2018-03-19 13:39:00

大概就是不用每個run都檢查window中的character用記錄該字元上次出現的位置來達到O(n)

繼續閱讀

Re: [問題] 跑Keras的model正常GPU使用率會是多少pipidog [問題] gurobi 最佳化多重解問題jasonfghx [問題] Pycharm安裝library問題HybridSC [問題] 新手pycharm skimage一直裝不好jerryhsieh30 [問題] Selenium xpath 讀取href的問題zo6596001 [問題]PYTHON 新手請教，如何重複運行程式xmsun [問題]各位大大想請問data anaylsis的一些問題lance5487 Re: 如何呼叫另一檔案裡def裡的參數flarehunter Re: 如何呼叫另一檔案裡def裡的參數Paudse [問題] 將for迴圈中所出現的值儲存成矩陣RX480