網(wǎng)絡(luò)營銷專業(yè)專升本考什么,seo外包公司一般費用是多少,dw做購物網(wǎng)站,現(xiàn)在新手做電商能做好嗎算法我們設(shè)計一個哈希表 recall#xff1a;哈希表 recall 以 s2 字符串的下標(biāo) index 為索引#xff0c;存儲匹配至第 s1cnt 個 s1 的末尾#xff0c;當(dāng)前匹配到第 s2cnt 個 s2 中的第 index 個字符時#xff0c; 已經(jīng)匹配過的 s1 的個數(shù) s1cnt 和 s2 的個數(shù) s2cnt 。我們在…算法我們設(shè)計一個哈希表 recall哈希表 recall 以 s2 字符串的下標(biāo) index 為索引存儲匹配至第 s1cnt 個 s1 的末尾當(dāng)前匹配到第 s2cnt 個 s2 中的第 index 個字符時 已經(jīng)匹配過的 s1 的個數(shù) s1cnt 和 s2 的個數(shù) s2cnt 。我們在每次遍歷至 s1 的末尾時根據(jù)當(dāng)前匹配到的 s2 中的位置 index 查看哈希表中的對應(yīng)位置如果哈希表中對應(yīng)的位置 index 已經(jīng)存儲元素則說明我們找到了循環(huán)節(jié)。循環(huán)節(jié)的長度可以用當(dāng)前已經(jīng)匹配的 s1 與 s2 的數(shù)量減去上次出現(xiàn)時經(jīng)過的數(shù)量即哈希表中存儲的值來得到。然后我們就可以通過簡單的運算求出所有構(gòu)成循環(huán)節(jié)的 s2 的數(shù)量對于不參與循環(huán)節(jié)部分的 s1直接遍歷計算即可具體實現(xiàn)以及一些細(xì)節(jié)邊界的處理請看下文的代碼。Python 3 實現(xiàn)class Solution: def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) - int: if n1 0: return 0 s1cnt, index, s2cnt 0, 0, 0 # recall 是我們用來找循環(huán)節(jié)的變量它是一個哈希映射 # 我們?nèi)绾握已h(huán)節(jié)假設(shè)我們遍歷了 s1cnt 個 s1此時匹配到了第 s2cnt 個 s2 中的第 index 個字符 # 如果我們之前遍歷了 s1cnt 個 s1 時匹配到的是第 s2cnt 個 s2 中同樣的第 index 個字符那么就有循環(huán)節(jié)了 # 我們用 (s1cnt, s2cnt, index) 和 (s1cnt, s2cnt, index) 表示兩次包含相同 index 的匹配結(jié)果 # 那么哈希映射中的鍵就是 index值就是 (s1cnt, s2cnt) 這個二元組 # 循環(huán)節(jié)就是 # - 前 s1cnt 個 s1 包含了 s2cnt 個 s2 # - 以后的每 (s1cnt - s1cnt) 個 s1 包含了 (s2cnt - s2cnt) 個 s2 # 那么還會剩下 (n1 - s1cnt) % (s1cnt - s1cnt) 個 s1, 我們對這些與 s2 進(jìn)行暴力匹配 # 注意 s2 要從第 index 個字符開始匹配 recall dict() while True: # 我們多遍歷一個 s1看看能不能找到循環(huán)節(jié) s1cnt 1 for ch in s1: if ch s2[index]: index 1 if index len(s2): s2cnt, index s2cnt 1, 0 # 還沒有找到循環(huán)節(jié)所有的 s1 就用完了 if s1cnt n1: return s2cnt // n2 # 出現(xiàn)了之前的 index表示找到了循環(huán)節(jié) if index in recall: s1cnt_prime, s2cnt_prime recall[index] # 前 s1cnt 個 s1 包含了 s2cnt 個 s2 pre_loop (s1cnt_prime, s2cnt_prime) # 以后的每 (s1cnt - s1cnt) 個 s1 包含了 (s2cnt - s2cnt) 個 s2 in_loop (s1cnt - s1cnt_prime, s2cnt - s2cnt_prime) break else: recall[index] (s1cnt, s2cnt) ? # ans 存儲的是 S1 包含的 s2 的數(shù)量考慮的之前的 pre_loop 和 in_loop ans pre_loop[1] (n1 - pre_loop[0]) // in_loop[0] * in_loop[1] # S1 的末尾還剩下一些 s1我們暴力進(jìn)行匹配 rest (n1 - pre_loop[0]) % in_loop[0] for i in range(rest): for ch in s1: if ch s2[index]: index 1 if index len(s2): ans, index ans 1, 0 # S1 包含 ans 個 s2那么就包含 ans / n2 個 S2 return ans // n2