难度: Medium
Submission
运行时间: 248 ms
内存: 28.1 MB
class Solution:
def maxLength(self, ribbons: List[int], k: int) -> int:
# corner case
if not ribbons:
return 0
if len(ribbons) == 1:
return (ribbons[0] // k) if (ribbons[0] // k) > 0 else 0
n = len(ribbons)
# targeted wood len
start, end = 1, min(max(ribbons), sum(ribbons) // k)
# can not obtain k ribbons
if end < 1:
return 0
# we exclude no answer situation, hence there must have an answer
while start + 1 < end:
mid = (start + end) // 2
cur_cnt = self.get_wood_count(mid, ribbons)
if cur_cnt < k:
# cnt is smaller than target
# we need to make cnt bigger, making wood_len smaller
end = mid
elif cur_cnt > k:
# cnt is larger than target
# we need to make cnt smaller, making wood_len bigger
start = mid
elif cur_cnt == k:
# we need to find max wood_len, which is the last element == target
start = mid
# goal is to find max wood_len
return end if self.get_wood_count(end, ribbons) >= k else start
def get_wood_count(self, targeted_wood_len, ribbons):
return sum(i // targeted_wood_len for i in ribbons)
Explain
此题解采用的是二分查找的方法来解决割绳子问题。题目要求将一组绳子割成若干段，每段长度相等，且段数至少为k。这里的关键是确定每段绳子的最大可能长度。使用二分查找在可能的长度范围内寻找最大的满足条件的长度。起始长度为1，最大长度设为绳子中的最大值和所有绳子总长除以k的最小值之间的较小者。通过二分查找，每次计算中间值mid，然后根据mid来计算可以割出的绳子段数。如果段数少于k，减小长度上限；如果段数多于或等于k，增大长度下限并继续搜索，以找出最大可能的长度。
时间复杂度: O(n log(maxLength))
空间复杂度: O(1)
class Solution:
def maxLength(self, ribbons: List[int], k: int) -> int:
if not ribbons:
return 0 # 没有绳子直接返回0
if len(ribbons) == 1:
return (ribbons[0] // k) if (ribbons[0] // k) > 0 else 0 # 只有一根绳子的情况
n = len(ribbons)
start, end = 1, min(max(ribbons), sum(ribbons) // k)
if end < 1:
return 0 # 如果最大长度小于1，无法割出任何段
while start + 1 < end:
mid = (start + end) // 2
cur_cnt = self.get_wood_count(mid, ribbons)
if cur_cnt < k:
end = mid
elif cur_cnt >= k:
start = mid
return end if self.get_wood_count(end, ribbons) >= k else start
def get_wood_count(self, targeted_wood_len, ribbons):
return sum(i // targeted_wood_len for i in ribbons) # 计算当前长度下可割得的总段数
Explore
这个选择基于两个考虑：首先，割出的每段绳子长度不可能超过绳子中的最大值，因为你不能从一根比这根短的绳子中割出更长的段。其次，所有绳子的总长度除以k给出了理论上每段绳子最大可能的平均长度。如果这个计算值小于绳子中的最大值，说明即使所有绳子均匀分割，每段的最大长度也不会超过这个平均值。因此，取这两者之间的较小者作为搜索的上界，可以有效缩小搜索范围，并保证找到的最大长度是合理的。
在这种情况下，算法先通过条件`end = min(max(ribbons), sum(ribbons) // k)`设定最大长度`end`。如果所有绳子的总长除以k小于1（即`sum(ribbons) < k`），则`end`会被设定为0。随后在二分查找过程中，如果`end`小于1，则算法会直接返回0，表示无法割出满足条件的绳子段。这是一种边界情况处理，确保算法在逻辑上严谨并能正确处理所有输入情况。
整除操作确实会忽略小数部分，但这对于割绳子问题是适当的。因为我们不能考虑不完整的绳子段，整段的长度必须是整数。使用整除可以确保只计算完整段，即使这意味着忽略了一部分绳子。这种方法是为了确保每段绳子的实际可用性，而不是仅仅从理论上分割绳子。因此，这不会影响结果的准确性，而是符合问题的实际需求。
在二分查找中使用`start + 1 < end`作为终止条件是为了防止进入无限循环，并确保可以探讨所有可能的长度。当`start`和`end`相邻时，中点`mid`将会等于`start`，此时如果继续使用`start < end`或`start <= end`作为条件，可能导致重复计算同一个中值，从而陷入循环。而当使用`start + 1 < end`时，一旦`start`和`end`相邻，循环就会停止，此时可以安全地检查`end`处的值是否满足条件，然后再决定是否使用`start`或`end`作为最终结果，这样可以更精确地找到最大可能长度。