โปรแกรมตรวจสอบจำนวนการสืบค้นที่ค้นหาลำดับเลขคณิตที่ถูกต้องใน Python

สมมติว่าเรามีรายการหมายเลขที่เรียกว่า nums และยังมีรายการการสืบค้นอีกด้วย โดยที่แต่ละองค์ประกอบการสืบค้นมี [i, j] แบบสอบถามนี้จึงถามว่ารายการย่อยของ nums จาก [i, j] (รวมทั้งสองอย่าง) เป็นลำดับเลขคณิตหรือไม่ สุดท้ายเราต้องหาจำนวนการสืบค้นที่คืนค่าเป็นจริง

ดังนั้น หากอินพุตเป็น nums =[2, 4, 6, 8, 7, 6, 5, 2] query =[[3, 4],[0, 3],[2, 4]] แล้ว ผลลัพธ์จะเป็น 2 เนื่องจาก [2, 4, 6, 8] เป็นลำดับเลขคณิต ดังนั้นข้อความค้นหา [0, 3] จึงเป็นจริง และสำหรับ [8, 7] ก็เป็นลำดับเลขคณิตเช่นกัน ดังนั้นแบบสอบถาม [3, 4] ก็เป็นจริงเช่นกัน แต่ [6, 8, 7] ไม่ใช่ลำดับเลขคณิต ดังนั้น [2, 4] จึงไม่เป็นความจริง

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

• ถ้า nums ว่างเปล่าก็
  • คืน 0
• n :=ขนาดของ nums
• diff :=รายการที่มีองค์ประกอบ (nums[i + 1] - nums[i]) สำหรับแต่ละ i ในช่วง 0 ถึง n - 2
• rle :=รายการขนาด (n - 1) และเติม 0
• สำหรับฉันในช่วง 0 ถึง n - 2 ทำ
  • ถ้า i> 0 และ diff[i] เหมือนกับ diff[i - 1] แล้ว
    • rle[i] :=rle[i - 1] + 1
  • มิฉะนั้น
    • rle[i] :=1
• ตอบ :=0
• สำหรับคำถามแต่ละข้อ (i, j) ให้ทำ
  • ถ้าฉันเหมือนกับ j แล้ว
    • อัน :=ans + 1
  • มิฉะนั้น
    • ans :=ans + (1 if rle[j - 1]>=(j - i) มิฉะนั้น 0)
• คืนสินค้า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def solve(nums, queries):
   if not nums:
      return 0

   n = len(nums)
   diff = [nums[i + 1] - nums[i] for i in range(n - 1)]

   rle = [0] * (n - 1)
   for i in range(n - 1):
      if i > 0 and diff[i] == diff[i - 1]:
         rle[i] = rle[i - 1] + 1
      else:
         rle[i] = 1

   ans = 0
   for i, j in queries:
      if i == j:
         ans += 1
      else:
         ans += rle[j - 1] >= (j - i)
   return ans

nums = [2, 4, 6, 8, 7, 6, 5, 2]
queries = [[3, 4],[0, 3],[2, 4]]
print(solve(nums, queries))

อินพุต

[2, 4, 6, 8, 7, 6, 5, 2], [[3, 4],[0, 3],[2, 4]]

ผลลัพธ์

2