資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用 Python 查詢大小為 M 的最新分組的程式
假設我們有一個數組 arr，它包含從 1 到 n 的數字排列。如果我們有一個大小為 n 的二進位制字串，並且最初所有位都設定為零。現在，在從 1 到 n 的每個步驟 i（二進位制字串和 arr 的索引都從 1 開始），位置 arr[i] 的位設定為 1。我們還有另一個值 m，我們需要找到存在大小為 m 的 1 的分組的最新步驟。這裡，1 的分組指的是連續的 1 的子字串，不能向任何方向擴充套件。我們必須找到存在長度正好為 m 的 1 的分組的最新步驟。如果找不到這樣的分組，則返回 -1。
因此，如果輸入類似於 arr = [3,5,1,2,4] m = 3，則輸出將為 4，因為初始二進位制字串為“00000”，然後按照以下步驟進行：
“00100”，分組：["1"]
“00101”，分組：["1", "1"]
“10101”，分組：["1", "1", "1"]
“11101”，分組：["111", "1"]
“11111”，分組：["11111"]
這裡，存在大小為 3 的分組的最新步驟是步驟 4。
為了解決這個問題，我們將遵循以下步驟：
n := arr 的大小
num := 0
ans := -1
l := 一個大小為 n 的陣列，並填充 0
r := 一個大小為 n 的陣列，並填充 0
對於 i in range 0 到 n - 1，執行：
cur := 1
idx := arr[i] - 1
如果 r[idx] 等於 m，則：
num := num - 1
如果 l[idx] 等於 m，則：
num := num - 1
cur := cur + l[idx] + r[idx]
num := num + (cur 等於 m)
如果 num > 0，則：
ans := ans 和 i + 1 的最大值
如果 idx - l[idx] > 0，則：
r[idx - l[idx] - 1] := cur
如果 idx + r[idx] < n - 1，則：
l[idx + r[idx] + 1] := cur
返回 ans
讓我們看看下面的實現以更好地理解：
示例
def solve(arr, m): n = len(arr) num = 0 ans = -1 l = [0] * n r = [0] * n for i in range(n): cur = 1 idx = arr[i] - 1 if r[idx] == m: num -= 1 if l[idx] == m: num -= 1 cur += l[idx] + r[idx] num += cur == m if num > 0: ans = max(ans, i + 1) if idx - l[idx] > 0: r[idx - l[idx] - 1] = cur if idx + r[idx] < n - 1: l[idx + r[idx] + 1] = cur return ans arr = [3,5,1,2,4] m = 3 print(solve(arr, m))
輸入
[3,5,1,2,4], 3
輸出
4
142 次檢視
