前往
大廳
主題

LeetCode - 1566. Detect Pattern of Length M Repeated K or More Times 解題心得

Not In My Back Yard | 2023-01-04 12:00:19 | 巴幣 0 | 人氣 191

題目連結:


題目意譯:
給定一正整數陣列 arr,請找到一個長度 m 的模式其重複了 k 次或更多次以上。

一個模式為一個子陣列,其由一個或多個數值所組成,在不彼此重疊的狀況下連續重複出現複數次。一個模式是由它的長度以及重複次數來定義。

如果存在一個長度 m 且重複了 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
解釋: 長度 1 的模式 (4) 連續出現了 4 次。注意到模式可以出現 k 次或更多,但絕對不得更少次。

範例 2:
輸入: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
輸出: true
解釋: 長度 2 的模式 (1,2) 連續出現了 2 次。另一個合法的模式 (2,1) 同樣也連續出現了 2 次。

範例 3:
輸入: arr = [1,2,1,2,1,3], m = 2, k = 3
輸出: false
解釋: 模式 (1,2) 長度是 2 但是其只重複了 2 次。沒有長度為 2 的模式重複了 3 次或更多次。


解題思維:
由於 arr 的長度最長不超過 100 個數字長。因此我們可以直接窮舉出 100 - m + 1 個子陣列(也就是窮舉子陣列開頭 arr[i],則 arr[i] ~ arr[i + m - 1] 就是我們要檢查的子陣列)。

然後檢查每一個是不是在 arr 中連續出現 k 次(即 arr[i] ~ arr[i + m - 1] 本身是一次,然後檢查 arr[i + m] ~ arr[i + 2m - 1] 是不是又是一次,以此類推)




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作