将数组拆分为m个子数组，使最大的子数组和最小。

Question

这是一个Leetcode问题 -

给定一个由非负整数和整数m__组成的数组，则可以将数组拆分为m非空连续子数组。编写一个算法来最小化这些m子数组中最大的和。Note -如果n是数组的长度，则假设满足以下约束：

• 1 n≤≤1000
• 1 m≤min(50，n__)

这是我对这个挑战的解决方案-

类解决方案(Object)：def __init__(self，num，m)：self.nums =numssel.m=max split_array(self，num，m)：“”类型num: List :type m: int :rtype: int“min_res =max(Num) max_res =sum(Num) low，高= min_res，max_res而低+1<高: mid =低+(高-低)//2如果self.is_valid(nums，m，mid)：高= mid = mid if self.is_valid(nums，m，low)：返回低回报高def is_valid(自，num，self.is_valid，m，n)：计数，当前= 1，0表示i在范围内(len(Num))：if num> n:返回假当前+= num如果当前> n:当前=num计数+= 1如果计数> m:返回假返回真

这里，我只是优化了二进制搜索方法(用于搜索排序列表中的元素的技术)，将low <= high的条件更改为low + 1 < high，并在low + high大于max int的情况下将其更改为mid = low + (high - low) / 2。

下面是一个输入/输出示例-

output = Solution([7,2,5,10,8], 2)
print(output.split_array([7,2,5,10,8], 2))
>>> 18

Explanation -

将nums分成两个子数组有四种方法。最好的方法是将其拆分为[7,2,5]和[10,8]，其中两个子数组中最大的和仅为18。

现在是输出的时候了-

%timeit output.split_array([7,2,5,10,8], 2)
12.7 µs ± 512 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

所以，我想知道我是否能使这个程序更短、更高效。

Answer 1

(某种程度上)不必要的OOP

由于可能的提交原因，许多像LeetCode这样的东西都需要将解决方案放在class中，但是如果我们只关心手头的任务，我建议您摆脱类，只使用函数。(如果去掉不必要的类，您将缩短代码，不过，我不会鼓励您全神贯注于缩短代码。)

此外，如果你不得不(无论出于什么原因)继续上课，请注意：

def __init__(self, nums, m):
    self.nums = nums
    self.m = m

当您传递这样的参数时，您可以一次又一次地重用它们。它们有点像伪全局变量。所以你需要做：

def is_valid(self, nums, m, n):

只是：

def is_valid(self):

并且(通常)您将访问self.m和self.n。

对可迭代性进行迭代，而不是在可迭代.

的len上迭代。

除非您正在变异nums (我不相信您是这样的)，否则更惯用的方法是迭代可迭代，因此：

for i in range(len(nums)):

变成：

for num in nums:

nums[i]的实例被num替换，例如if nums[i] > n:变为if num > n:。

附带注意:如果您需要值i和nums[i]，如果需要两者，您可能需要考虑使用enumerate。

Answer 2

if nums[i] > n:
    return False

这是不必要的，您开始二进制搜索的最大(名词)作为最小，所以n将永远是至少等于最大的名词。

为什么您的构造函数和split_array方法都接受问题的参数？要么只使用构造函数，要么使split_array成为一个静态方法，而不使用构造函数。

你为什么有min_res和max_res？要么在二进制搜索中使用这些变量，要么用低和高替换它们，没有理由同时使用这些变量和低/高变量。

如果保留数组的累计和，则可以更改is_valid以执行二进制搜索，以查找下一组的索引。这将使复杂性从O(x=n，n)变为O(m *log(N))*log(sum(N))。对于如此少量的n，在这种情况下可能不值得这样做，但是如果您有小m和大n，它肯定会更好。