难度: Hard
Submission
运行时间: 27 ms
内存: 16.2 MB
class Solution:
def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:
a = []
wq, wr = divmod(width, sideLength)
hq, hr = divmod(height, sideLength)
for r in range(sideLength):
for c in range(sideLength):
ww = wq + 1 if r < wr else wq
hh = hq + 1 if c < hr else hq
#print((r,c),(ww,hh))
a.append(ww * hh)
a.sort(reverse = True)
#print(a)
return sum(a[:maxOnes])
Explain
该题解的核心思路是通过计算每个小矩形内1的可能数量来确定整个矩阵中1的最大数量。首先，算法将矩阵分割为边长为sideLength的小矩形，并计算这些小矩形完整填充大矩阵的次数（整除部分），以及边缘可能多出来的部分（余数部分）。对于每一个可能的位置(r, c)，算法计算出这个位置在所有小矩形中出现的次数（这取决于它是否位于边缘部分）。然后将所有这些计数存入数组a，并对数组a进行降序排序，最后选取前maxOnes个元素的和，作为结果返回，这是因为我们想要最大化矩阵中1的数量，而每个位置的贡献是不一样的。
时间复杂度: O(sideLength^2 * log(sideLength^2))
空间复杂度: O(sideLength^2)
class Solution:
def maximumNumberOfOnes(self, width: int, height: int, sideLength: int, maxOnes: int) -> int:
a = [] # 存放每个位置的贡献值
wq, wr = divmod(width, sideLength) # 宽度整除和余数
hq, hr = divmod(height, sideLength) # 高度整除和余数
for r in range(sideLength): # 遍历每一个可能的行位置
for c in range(sideLength): # 遍历每一个可能的列位置
ww = wq + 1 if r < wr else wq # 计算此行位置的重复次数
hh = hq + 1 if c < hr else hq # 计算此列位置的重复次数
a.append(ww * hh) # 计算此位置的总贡献并添加到列表中
a.sort(reverse = True) # 对贡献值降序排序
return sum(a[:maxOnes]) # 返回最大的maxOnes个贡献值之和
Explore
算法仅基于位置和大小来计算每个小矩形内1的可能数量，而并没有考虑矩阵中实际的1的分布情况。这种方法基于统计和概率的假设，即每个位置的1的出现概率是均等的，因此可以通过计算每个位置在小矩形中的出现次数来估算它的总贡献。
题解中并未详细说明sideLength的选择方法，通常这种参数的选择依赖于具体问题的需求和矩阵的尺寸。sideLength可能是一个预设的参数，或者需要通过实验和优化来确定最适合问题的值。在不同的宽度和高度下，可能需要调整sideLength以达到最佳的性能或结果。
这种逻辑基于整除和余数的计算。当矩阵的宽度或高度不能被sideLength完全整除时，边缘会有剩余的部分。如果行位置r小于余数wr，意味着这一行在边缘的额外部分中，因此它会多填充一次，从而增加一次重复次数。这确保了每个位置的出现次数准确反映了其在整个矩阵中被小矩形覆盖的次数。
这种方法在假设每个位置的1出现概率相等时，能够尽可能地获取最大数量的1。然而，如果实际的1的分布不均或有特定的模式，则仅选择出现次数最多的位置可能不会总是得到最大的1的数量。在某些特殊情况下，其他未选取的组合可能由于分布的特性而包含更多的1。因此，这种方法最适用于1的分布相对均匀的情况。