class Solution {
public:
int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
}
};
1183. 矩阵中 1 的最大数量
现在有一个尺寸为 width * height 的矩阵 M，矩阵中的每个单元格的值不是 0 就是 1。
而且矩阵 M 中每个大小为 sideLength * sideLength 的 正方形 子阵中，1 的数量不得超过 maxOnes。
请你设计一个算法，计算矩阵中最多可以有多少个 1。
示例 1：
输入：width = 3, height = 3, sideLength = 2, maxOnes = 1 输出：4 解释： 题目要求：在一个 3*3 的矩阵中，每一个 2*2 的子阵中的 1 的数目不超过 1 个。 最好的解决方案中，矩阵 M 里最多可以有 4 个 1，如下所示： [1,0,1] [0,0,0] [1,0,1]
示例 2：
输入：width = 3, height = 3, sideLength = 2, maxOnes = 2 输出：6 解释： [1,0,1] [1,0,1] [1,0,1]
提示：
1 <= width, height <= 1001 <= sideLength <= width, height0 <= maxOnes <= sideLength * sideLength原站题解
python3 解法, 执行用时: 56 ms, 内存消耗: 16.3 MB, 提交时间: 2023-10-22 08:46:00
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])
java 解法, 执行用时: 9 ms, 内存消耗: 38.9 MB, 提交时间: 2023-10-22 08:45:39
class Solution {
public int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
int ans = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i = 0; i < sideLength; ++i)
for(int j = 0; j < sideLength; ++j) {
pq.add(((width - 1 - i) / sideLength + 1) * ((height - 1 - j) / sideLength + 1));
if(pq.size() > maxOnes)
pq.poll();
}
while(!pq.isEmpty())
ans += pq.poll();
return ans;
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.4 MB, 提交时间: 2023-10-22 08:45:12
class Solution {
public:
int maximumNumberOfOnes1(int width, int height, int sideLength, int maxOnes) {
int ret = 0;
vector<int> all;
for (int i = 0; i < sideLength; ++i) {
for (int j = 0; j < sideLength; ++j) {
int w = width/sideLength;
if (width%sideLength > i) {
w++;
}
int h = height/sideLength;
if (height%sideLength > j) {
h++;
}
all.emplace_back(w * h);
}
}
sort(all.begin(), all.end(), [](int a, int b) {
return a > b;
});
for (int i = 0; i < maxOnes; i++) {
ret += all[i];
}
return ret;
}
int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
vector<int> data;
for (int i = 0; i < sideLength; ++i)
for (int j = 0; j < sideLength; ++j)
data.push_back(ceil((double)(width - i) / sideLength) * ceil((double)(height - j) / sideLength));
sort(data.begin(), data.end(), greater<int>());
int result = 0;
for (int i = 0; i < maxOnes; ++i)
result += data[i];
return result;
}
};
golang 解法, 执行用时: 4 ms, 内存消耗: 4 MB, 提交时间: 2023-10-22 08:44:40
func maximumNumberOfOnes(width int, height int, sideLength int, maxOnes int) int {
all := []int{}
ret := 0
for i := 0; i < sideLength; i++ {
for j := 0; j < sideLength; j++ {
w := width/sideLength
if width%sideLength > i {
w++
}
h := height/sideLength
if height%sideLength > j {
h++
}
all = append(all, w * h)
}
}
sort.Ints(all)
n := len(all)
for i := 0; i < maxOnes; i++ {
ret += all[n - i - 1]
}
return ret
}