今日題目

題目連結：1566. Detect Pattern of Length M Repeated K or More Times
題目主題：Array, Enumeration

昨天介紹了 Enumeration 的基本概念，今天會在練習一題以Enumeration 當主題的題目，建議還沒看過 Enumeration 先回 Day 19：1534. Count Good Triplets 看看簡單說說 Enumeration。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

題目會給一組數字陣列，目的是要確認是否有長度為 m 的子陣列連續出現 k 次，這個連續出現是不會有重疊的狀況。如果連續出現了 k 次以上，回傳 True，若沒有則回傳 False。

約束：

• 2 <= arr.length <= 100
• 1 <= arr[i] <= 100
• 1 <= m <= 100
• 2 <= k <= 100

範例1

輸入: arr = [1,2,4,4,4,4], m = 1, k = 3
輸出: true
解說: 範例輸入了 m = 1 代表要找到長度為 1 的子陣列，而 k = 3 代表這個子陣列要重複出現 3 次以上才算True，這邊可以看到 [4] 已經連續出現了 4 次，因此最後回true。

範例2

輸入: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
輸出: true
解說: 這邊可以看到 [2, 1] 及 [1, 2] 都符合長度為 2 的子陣列也不重疊的重複出現 2 次，因此最後回傳true。事實上，只要有一組 m 長度的子陣列連續出現 k 次以上，就可以下結論為true。

範例3

輸入: arr = [1,2,1,2,1,3], m = 2, k = 3
輸出: false
解說: 可以看到 [1, 2] 的子陣列只連續出現了兩次，[2, 1] 也只連續出現了兩次，[1, 3]只出現了一次，但目標是要連續出現 3 次才算，因此最後回false。

範例4

輸入: arr = [1,2,3,1,2], m = 2, k = 2
輸出: false
解說: 這個範例可以注意的是，[1, 2] 子陣列雖然出現了兩次，但因為中間隔著 3，不符合連續出現這個條件，因此最後回傳false。

範例5

輸入: arr = [2,2,2,2], m = 2, k = 3
輸出: false
解說: 這邊可以解釋，雖然子陣列長度為 2 的 [2, 2] 仔細算的話會出現 3 次，但因為是重疊的狀況出現才會有 3 次，如果連續不重疊的話只出現 2 次，因此這個範例也是回傳false。

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 宣告一個times用來記錄一個不重疊連續出現次數及一個nowIndex記錄目前的位置。
2. 另外在宣告一個tmpPattern用來記錄目前長度為 m 的子陣列。
3. 跑一個迴圈，將所有長度為 m 的子陣列都走過一次：
   • 若已經出現 times >= k 的狀況直接結束回傳true。
   • 每次移動會從 nowIndex 往前移動 m 。
   • 移動後確認目前長度為 m 的子陣列是否與先前紀錄的相同。
     • 相同：times + 1。
     • 不相同：nowIndex回原本的位置往前一步，times重新計算，最後重新紀錄一組新的長度為 m 的子陣列 。

圖解過程

範例：arr = [1, 2, 1, 2, 3, 1, 3], m = 2, k = 2

上圖中，每一圈會用 +m 在移動，step2 是有重複出現的例子，移動後取得目前長度為 m 的子陣列，與tmpPattern確認是否有連續出現，有的話times會+1表示出現次數。

而 step3 ~ step5 是沒有連續出現的例子，若發現子陣列不同會更新tmpPattern繼續往下確認，times重新算。

最後長度為 m 的子陣列都走過一次，沒有連續出現 k 次的子陣列，所以最後回傳false。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class Solution:
    def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
        times = 1 #不重疊連續出現次數
        nowIndex = 0 #目前走到的位置
        tmpPattern = arr[nowIndex:nowIndex+m] #紀錄目前長度為 m 的子陣列
        while nowIndex < (len(arr) - m):
            # 若不重疊連續出現 k 次或以上直接結束，代表以符合條件
            if times >= k: break
            # 不重疊，因此每次移動直接移動 m 
            nowIndex += m
            if tmpPattern == arr[nowIndex:nowIndex+m]:
                # 若目前子陣列與紀錄的子陣列相同，增加一次連續出現次數
                times += 1
            else:
                # 若不同，位置回到前一次的位置+1
                nowIndex -= m
                nowIndex += 1
                # 重新計算次數
                times = 1
                # 重新給一組新的長度為 m 的子陣列
                tmpPattern = arr[nowIndex:nowIndex+m]
        return times >= k

希望您今天能瞭解到...

1. 1566. Detect Pattern of Length M Repeated K or More Times 的解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：401. Binary Watch