โปรแกรมค้นหาอาร์เรย์ย่อยที่ยาวที่สุดของ 1 วินาทีหลังจากลบหนึ่งองค์ประกอบโดยใช้ Python

สมมติว่าเรามีอาร์เรย์ไบนารีที่เรียกว่า nums เราสามารถลบหนึ่งองค์ประกอบออกจากมันได้ เราต้องหาขนาดของอาร์เรย์ย่อยที่ไม่ว่างที่ยาวที่สุดซึ่งมีเพียง 1 ในอาร์เรย์ผลลัพธ์ หากไม่มีอาร์เรย์ย่อยดังกล่าว ให้คืนค่า 0

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[1,0,1,1,1,0,1,1,0] เอาต์พุตจะเป็น 5 เพราะการลบ 0 ออกจากตำแหน่ง 5 เราจะได้ subarray [1 ,1,1,1,1] มี 5 1 วินาที

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ถ้า 0 ไม่เป็นตัวเลข ดังนั้น

  • ขนาดส่งคืนของ nums - 1

• ถ้า 1 ไม่เป็นตัวเลข ดังนั้น

  • คืนค่า 0

• a :=รายการใหม่

• cnt :=0

• สำหรับแต่ละ i ใน nums ทำ

  • ถ้าฉันเหมือนกับ 0 แล้ว

    • ถ้า cnt ไม่เหมือนกับ 0 แล้ว

      • ใส่ cnt ต่อท้าย a

      • cnt :=0

    • ใส่ i ต่อท้าย a

    • มิฉะนั้น

      • cnt :=cnt + 1

• ถ้า cnt ไม่เหมือนกับ 0 แล้ว

  • ใส่ cnt ต่อท้าย a

• สูงสุด :=0

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาด a ทำ

  • ถ้า a[i] ไม่เหมือนกับ 0 แล้ว

    • ไปทำซ้ำต่อไป

  • ถ้า a[i] เท่ากับ 0 และฉันมีขนาดเท่ากับ a - 1 แล้ว

    • สูงสุด :=สูงสุดของ Max และ a[i-1]

  • มิฉะนั้น เมื่อ a[i] เท่ากับ 0 และ i เท่ากับ 0 แล้ว

    • สูงสุด :=สูงสุด และ a[i+1]

  • มิฉะนั้นเมื่อ a[i] เท่ากับ 0 แล้ว

    • สูงสุด :=สูงสุด และ (a[i+1]+a[i-1])

• ผลตอบแทนสูงสุด

ตัวอย่าง

def solve(nums):
   if 0 not in nums:
      return len(nums)-1
   if 1 not in nums:
      return 0
      a = []
      cnt = 0
      for i in nums:
         if i == 0:
            if cnt != 0:
               a.append(cnt)
               cnt = 0
            a.append(i)
         else:
            cnt += 1
      if cnt!=0:
         a.append(cnt)
      Max = 0
      for i in range(len(a)):
         if a[i] != 0:
            continue
         if a[i] == 0 and i == len(a)-1:
            Max = max(Max,a[i-1])
         elif a[i] == 0 and i == 0:
            Max = max(Max,a[i+1])
         elif a[i] == 0:
            Max = max(Max,a[i+1]+a[i-1])
   return Max
nums = [1,0,1,1,1,0,1,1,0]
print(solve(nums))

อินพุต

[1,0,1,1,1,0,1,1,0]

ผลลัพธ์

5