โปรแกรมตรวจสอบว่าสามารถแบ่งรายการเป็นสับลิสต์เพิ่มขึ้นติดต่อกันได้หรือไม่ใน Python

สมมติว่าเรามีรายการตัวเลข nums ที่เรียงลำดับไม่ลดลง (non-decreasing) เราต้องตรวจสอบว่าสามารถแบ่งเป็น subsequences ได้หรือไม่ โดยแต่ละ subsequence ต้องมีความยาวอย่างน้อย 3 และเป็นตัวเลขเพิ่มขึ้นติดต่อกัน (consecutive increasing)

เช่น ถ้าข้อมูลนำเข้าคือ nums = [2, 3, 4, 4, 5, 6, 7] ผลลัพธ์จะเป็น True เนื่องจากแบ่งได้เป็น [2, 3, 4] และ [4, 5, 6, 7]

ขั้นตอนการแก้ปัญหา (นับจุดเริ่มต้นและจุดสิ้นสุด)

• counts := Counter(nums)
• starts := [], ends := []
• วน x ในคีย์ของ counts เรียงลำดับ:
  • ถ้า count[x] > count[x-1]: เพิ่ม x จำนวน count[x] - count[x-1] ครั้งเข้า starts
  • ถ้า count[x] > count[x+1]: เพิ่ม x จำนวน count[x] - count[x+1] ครั้งเข้า ends
• คืน True ถ้าทุกคู่ (start, end) ต้องมากว่า start + 2 <= end, มิฉะนั้น False

ตัวอย่างโค้ด

from collections import Counter
class Solution:
    def solve(self, nums):
        count = Counter(nums)
        starts = []
        ends = []
        for x in sorted(count):
            if count[x] > count[x - 1]:
                starts.extend([x] * (count[x] - count[x - 1]))
            if count[x] > count[x + 1]:
                ends.extend([x] * (count[x] - count[x + 1]))
        return all(s + 2 <= e for s, e in zip(starts, ends))

ob = Solution()
nums = [2, 3, 4, 4, 5, 6, 7]
print(ob.solve(nums))

ข้อมูลนำเข้า

[6, 7, 5, 10, 13], 2

ผลลัพธ์

True