สมมติว่าเรามีสตริงไบนารีที่เรียกว่ากล่อง โดยที่ Boxes[i] คือ '0' แสดงว่ากล่อง ith ว่างเปล่า และ '1' แสดงว่ามีหนึ่งลูกบอล ในการดำเนินการครั้งเดียว เราสามารถย้ายลูกบอลหนึ่งลูกจากกล่องหนึ่งไปยังกล่องที่อยู่ติดกัน หลังจากทำเช่นนั้น อาจมีมากกว่าหนึ่งลูกในบางกล่อง เราต้องหาคำตอบอาร์เรย์ขนาด n โดยที่ answer[i] คือจำนวนการดำเนินการขั้นต่ำที่จำเป็นในการย้ายลูกบอลทั้งหมดไปยังกล่อง ith
ดังนั้น หากอินพุตเป็นเหมือนกล่อง ="1101" ผลลัพธ์จะเป็น [4, 3, 4, 5]
-
ในการวางลูกบอลทั้งหมดบนกล่องแรก เราต้องรับจากกล่องที่ 2 ด้วยการผ่าตัดหนึ่งครั้ง และจากลูกบอลสุดท้ายด้วยการแทง 3 ครั้ง ดังนั้นรวมทั้งหมด 4 ครั้ง
-
ในการนำลูกบอลทั้งหมดไปไว้ในกรอบที่สอง เราต้องรับจากกล่องที่ 1 ด้วยการแทงครั้งเดียว และจากบอลสุดท้ายสองลูก รวมทั้งหมด 3 ครั้ง
-
ในการนำลูกบอลทั้งหมดไปไว้ในกรอบที่สาม เราต้องใช้จากกล่องที่ 2 และสุดท้ายด้วยการแทงอย่างละ 1 ครั้ง และจากกล่องที่ 1 สองครั้ง รวมทั้งหมด 4 ครั้ง
-
ในการนำลูกบอลทั้งหมดไปไว้ในกรอบสุดท้าย เราต้องรับจากกล่องที่ 1 สามครั้ง และจากกล่องที่ 2 กับ 2 ครั้ง รวมทั้งหมด 5 ครั้ง
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ซ้าย :=0, ขวา :=0, dist :=0
-
สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของกล่อง - 1 ทำ
-
ถ้า box[i] เหมือนกับ "1" แล้ว
-
dist :=dist + ฉัน
-
ถ้าฉันเหมือนกับ 0 แล้ว
-
ซ้าย :=ซ้าย + 1
-
-
มิฉะนั้น
-
ขวา :=ขวา + 1
-
-
-
-
arr :=รายการและเริ่มต้นใส่ dist ลงไป
-
สำหรับฉันอยู่ในช่วง 1 ถึงขนาดของกล่อง - 1 ทำ
-
ใส่ arr[i-1] + ซ้าย - ขวาที่ท้าย arr
-
ถ้า box[i] เหมือนกับ "1" แล้ว
-
ซ้าย :=ซ้าย + 1
-
ขวา :=ขวา - 1
-
-
-
กลับ arr
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(boxes):
left = 0
right = 0
dist = 0
for i in range(len(boxes)):
if boxes[i] == "1":
dist += i
if i == 0:
left += 1
else:
right += 1
arr = [dist]
for i in range(1, len(boxes)):
arr.append(arr[i-1] + left - right)
if boxes[i] == "1":
left += 1
right -= 1
return arr
boxes = "1101"
print(solve(boxes)) อินพุต
"1101"
ผลลัพธ์
[4, 3, 4, 5]
