โปรแกรมหาโซนที่ถูกเยี่ยมชมมากที่สุดบนวงจรกลมใน Python

หาโซนที่ถูกเยี่ยมชมมากที่สุดบนวงจรแข่ง

มีวงจรกลมที่มี n โซน หมายเลข 1 ถึง n แข่งขันประกอบด้วย m รอบ รอบที่ i เริ่มที่โซน rounds[i-1] และจบที่โซน rounds[i] ต้องการหาโซนที่ถูกเยี่ยมชมมากที่สุด เรียงจากน้อยไปมาก (หมายเลขโซนเพิ่มขึ้นทวนเข็มนาฬิกา)

ตัวอย่าง

n = 4, rounds = [1,3,1,2]

ผลลัพธ์: [1, 2]

การแข่งเริ่มที่โซน 1 ลำดับโซนที่ผ่าน: [1,2,3 (จบรอบ1),4,1 (จบรอบ2), 2 (จบรอบ3)] โซน 1 และ 2 ถูกเยี่ยมชม 2 ครั้ง ส่วนโซน 3 และ 4 เพียง 1 ครั้ง

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

1. สร้าง dictionary d เก็บจำนวนครั้งที่เยี่ยมชมแต่ละโซน
2. กำหนดค่าเริ่มต้น d[j] = 0 สำหรับ j = 1 ถึง n
3. d[rounds[0]] = 1 (นับจุดเริ่มต้น)
4. วนลูป i จาก 1 ถึง len(rounds)-1:
   • ถ้า rounds[i] > rounds[i-1]: วน j จาก rounds[i-1]+1 ถึง rounds[i] บวก d[j]
   • อื่นๆ: วน j จาก rounds[i-1]+1 ถึง n บวก d[j], แล้ววน j จาก 1 ถึง rounds[i] บวก d[j]
5. หาค่าสูงสุดของ d และรวบรวมโซนที่มีค่าเท่าสูงสุด
6. คืนค่ารายการโซนที่เรียงแล้ว

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

def solve(n, rounds):
    d = {}
    for j in range(1, n+1):
        d[j] = 0
    d[rounds[0]] = 1
    for i in range(1, len(rounds)):
        if rounds[i] > rounds[i-1]:
            for j in range(rounds[i-1]+1, rounds[i]+1):
                d[j] += 1
        else:
            for j in range(rounds[i-1]+1, n+1):
                d[j] += 1
            for j in range(1, rounds[i]+1):
                d[j] += 1
    curr = d[rounds[0]]
    out = [rounds[0]]
    for i in range(1, n+1):
        if i != rounds[0]:
            if d[i] > curr:
                curr = d[i]
                out = [i]
            elif d[i] == curr:
                out.append(i)
    return sorted(out)

n = 4
rounds = [1,3,1,2]
print(solve(n, rounds))  # Output: [1, 2]

อินพุต

4, [1,3,1,2]

เอาต์พุต

[1, 2]