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

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

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

ขั้นตอนการแก้ปัญหา

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

ตัวอย่างการใช้งาน

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