สมมติว่าเรามีอาร์เรย์ arr ซึ่งเป็นการเรียงสับเปลี่ยนของตัวเลขตั้งแต่ 1 ถึง n ถ้าเรามีสตริงไบนารีขนาด n และเริ่มต้นบิตทั้งหมดเป็นศูนย์ ตอนนี้ในแต่ละขั้นตอน i (การจัดทำดัชนีเริ่มจาก 1 สำหรับทั้งสตริงไบนารีและ arr) จาก 1 ถึง n บิตที่ตำแหน่ง arr[i] ถูกตั้งค่าเป็น 1 เรายังมีอีกค่าหนึ่งคือ m และเราจำเป็นต้องค้นหาค่าล่าสุด ขั้นตอนที่มีกลุ่มคนขนาด m. ในที่นี้ กลุ่มของ one หมายถึงสตริงย่อยที่ต่อเนื่องกันของ 1s ซึ่งไม่สามารถขยายไปในทิศทางใดทิศทางหนึ่งได้ เราต้องหาขั้นตอนล่าสุดที่มีกลุ่มของความยาวพอดี m. หากไม่พบกลุ่มดังกล่าว ให้คืนค่า -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
-
ตอบ :=-1
-
l :=อาร์เรย์ขนาด n และเติม 0
-
r :=อาร์เรย์ขนาด n และเติม 0
-
สำหรับฉันอยู่ในช่วง 0 ถึง n - 1 ทำ
-
คู :=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]
-
l[idx + r[idx] + 1] :=cur
-
-
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
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
