โปรแกรมหารายการแสดงระยะทางรวมในการย้ายลูกบอลทั้งหมดไปตำแหน่งปัจจุบันใน Python

สมมติว่าเรามีรายการไบนารีชื่อ nums มีแค่ 0 และ 1 โดย 0 แสดงเซลล์ว่าง และ 1 แสดงเซลล์ที่มีลูกบอล เราต้องหารายการใหม่ชื่อ L ขนาดเท่ากับ nums โดย L[i] คือระยะทางรวมที่ต้องใช้ย้ายลูกบอลทั้งหมดไปที่ L[i] ระยะทางย้ายลูกบอลจากดัชนี j ไป i คือ |j - i|

เช่น ถ้าอินพุตคือ nums = [1, 1, 0, 1] ผลลัพธ์จะเป็น [4, 3, 4, 5] เพราะ:

• L[0] = |0-0| + |1-0| + |3-0|
• L[1] = |0-1| + |1-1| + |3-1|
• L[2] = |0-2| + |1-2| + |3-2|
• L[3] = |0-3| + |1-3| + |3-3|

เพื่อย้ายลูกบอลทั้งหมดไป L[1] ต้องย้ายลูกบอลจากดัชนี 0 ไป 1 ระยะ 1 และจากดัชนี 3 ไป 1 ระยะ 2

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

1. ถ้า nums ว่าง คืนค่ารายการว่าง
2. left_count := 0, right_count := 0, left_sum := 0, right_sum := 0, result := รายการใหม่
3. สำหรับแต่ละดัชนีและค่า num ใน nums:
   • ถ้า num ไม่เป็นศูนย์: right_count += 1, right_sum += ดัชนี
4. สำหรับแต่ละดัชนีและค่า num ใน nums:
   • เพิ่ม (left_sum + right_sum) เข้า result
   • ถ้า num ไม่เป็นศูนย์: right_count -= 1, left_count += 1
   • left_sum := left_sum + left_count, right_sum := right_sum - right_count
5. คืนค่า result

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

def solve(nums):
    if not nums:
        return []
    left_count = right_count = 0
    left_sum = right_sum = 0
    result = []
    for index, num in enumerate(nums):
        if num:
            right_count += 1
            right_sum += index
    for index, num in enumerate(nums):
        result.append(left_sum + right_sum)
        if num:
            right_count -= 1
            left_count += 1
        left_sum += left_count
        right_sum -= right_count
    return result

nums = [1, 1, 0, 1]
print(solve(nums))

อินพุต

[1, 1, 0, 1]

เอาต์พุต

[4, 3, 4, 5]