สมมติว่าเรามีรายการไบนารีที่เรียกว่า nums ที่มีเพียง 0s และ 1s โดยที่ 0 หมายถึงเซลล์ว่างและ 1 หมายถึงเซลล์นั้นเต็มไปด้วยลูกบอล เราต้องหารายการของ say 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
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ถ้า nums ว่างเปล่าก็
- คืนรายการใหม่
- left_count :=0
- right_count :=0
- left_sum :=0
- right_sum :=0
- ผลลัพธ์ :=รายการใหม่
- สำหรับแต่ละดัชนีและค่า num เป็น nums ทำ
- ถ้า num ไม่ใช่ศูนย์ แล้ว
- right_count :=right_count + 1
- right_sum :=right_sum + ดัชนี
- ถ้า num ไม่ใช่ศูนย์ แล้ว
- สำหรับแต่ละดัชนีและค่า num เป็น nums ทำ
- แทรก (left_sum + right_sum) ที่ส่วนท้ายของผลลัพธ์
- ถ้า num ไม่ใช่ศูนย์ แล้ว
- right_count :=right_count - 1
- left_count :=left_count + 1
- left_sum :=left_sum + left_count
- right_sum :=right_sum - right_count
- ผลตอบแทน
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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]
