难度: Medium
Submission
运行时间: 699 ms
内存: 26.4 MB
class Solution:
def equalizeWater(self, buckets: List[int], loss: int) -> float:
left, right = 0, max(buckets)
loss_factor = 1 - loss / 100.0
def canAchieve(x):
pour_in, pour_out = 0, 0
for water in buckets:
if water > x:
pour_out += (water - x)
else:
pour_in += (x - water)
# 考虑损耗后，需要倒出的水量是否足够
return pour_out * loss_factor >= pour_in
while right - left > 1e-5:
mid = (left + right) / 2
if canAchieve(mid):
left = mid
else:
right = mid
return left
Explain
此题解采用二分查找方式来确定能够使所有水桶中水量相等的最大水量。首先设定搜索范围，即从0到最大桶中的水量。通过不断调整搜索范围的中间值来逼近目标值。在每次的迭代中，使用一个辅助函数 `canAchieve(x)` 来检查是否可以通过倒水和损耗达到每个水桶的水量都为 x。这个函数计算需要往桶中倒入的水量以及可以从桶中倒出的水量（考虑到有一定比例的损耗），如果考虑损耗后可倒出的水量不小于需要倒入的水量，则说明可以实现目标。通过二分查找逐步缩小可能的水量范围，直至达到足够的精度。
时间复杂度: O(n log(maxBucket))
空间复杂度: O(1)
class Solution:
def equalizeWater(self, buckets: List[int], loss: int) -> float:
left, right = 0, max(buckets)
loss_factor = 1 - loss / 100.0 # 计算损耗系数
def canAchieve(x):
pour_in, pour_out = 0, 0
for water in buckets: # 遍历每个桶
if water > x:
pour_out += (water - x) # 计算可以倒出的水量
else:
pour_in += (x - water) # 计算需要倒入的水量
return pour_out * loss_factor >= pour_in # 检查是否满足条件
while right - left > 1e-5: # 二分查找直到精度足够
mid = (left + right) / 2
if canAchieve(mid):
left = mid
else:
right = mid
return left
Explore
在这个问题中，选择0作为初始的最小值(left)是因为理论上，如果所有桶的水量都可以调整到0，那么一定可以调整到任何大于0且小于等于桶中最小水量的目标值。更实际的考虑是，可能存在一种情况，即所有桶的水量都被调整到非常接近0的水平（假设没有最小限制或可以完全倒空），此时从0开始搜索可以保证覆盖所有可能的目标水量。此外，从0开始也简化了实现，因为不需要先检查并获取桶中的最小水量。
精度的选择`1e-5`（即0.00001）是基于问题的实际需求和性能考虑。在许多实际应用中，这种精度已经足够用来保证结果的实用性，同时避免了过度计算导致的性能下降。这个精度值足够小，可以使得计算得到的水量分配方案在实际操作中感觉上是均等的，同时又足够大，以避免在计算中进入过深的递归或过多的迭代，确保算法的执行效率。
在`canAchieve`函数中，水的损耗是通过设置一个损耗系数`loss_factor`来考虑的，该系数等于`1 - loss / 100.0`，其中`loss`是以百分比形式给出的。具体地，在计算可以从桶中倒出的水量时，实际上只有倒出水量的`loss_factor`倍能够用于其他桶。这意味着如果你从一个桶中倒出100单位的水，并且损耗率为10%，那么实际上只有90单位的水可以被用来填充其他桶。这样的损耗计算确保了每次倒水操作的实际效果都按照损耗率减少，从而精确控制水量平衡的过程。
在`canAchieve`函数中，如果桶中的水量正好等于x，这种情况确实被考虑了，但它对倒水操作没有任何影响。当水量正好等于目标水量x时，不需要从这个桶倒出水也不需要向这个桶倒入水。这意味着这个桶既不增加倒入需求量，也不增加可倒出水量。因此，这种情况下桶的水量是处于理想状态，不影响`canAchieve`函数的结果，因为它不改变倒入或倒出水量的总计算值。