Giả sử chúng ta có một danh sách nhị phân gọi là nums chỉ chứa các số 0 và 1 trong đó số 0 cho biết ô trống và 1 cho biết ô được lấp đầy bởi một quả bóng. Chúng ta phải tìm một danh sách mới bao gồm L, có kích thước cũng giống như kích thước nums, trong đó L [i] được đặt thành tổng khoảng cách cần thiết để di chuyển tất cả các quả bóng đến L [i]. Ở đây khoảng cách để di chuyển một quả bóng từ chỉ số j đến chỉ số i là | j - i |.
Vì vậy, nếu đầu vào là nums =[1, 1, 0, 1], thì đầu ra sẽ là [4, 3, 4, 5], bởi vì
- 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 |
Vì vậy, để di chuyển tất cả các quả bóng đến L [1] chúng ta phải di chuyển quả bóng từ chỉ số 0 đến 1 với khoảng cách 1 và di chuyển bóng từ chỉ số 3 đến 1 với khoảng cách 2.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- nếu nums trống, thì
- trả lại một danh sách mới
- left_count:=0
- right_count:=0
- left_sum:=0
- right_sum:=0
- kết quả:=một danh sách mới
- đối với mỗi chỉ mục và giá trị num trong nums, hãy thực hiện
- nếu num khác 0, thì
- right_count:=right_count + 1
- right_sum:=right_sum + index
- nếu num khác 0, thì
- đối với mỗi chỉ mục và giá trị num trong nums, hãy thực hiện
- chèn (left_sum + right_sum) vào cuối kết quả
- nếu num khác 0, thì
- right_count:=right_count - 1
- left_count:=left_count + 1
- left_sum:=left_sum + left_count
- right_sum:=right_sum - right_count
- trả về kết quả
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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))
Đầu vào
[1, 1, 0, 1]
Đầu ra
[4, 3, 4, 5]