算法leetcode

【贪心难题】力扣1183-矩阵中1的最大数量（排序）

字数统计: 560字   |   阅读时长: 2分
,

摘要: 一个排序贪心的问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，今天我们来看一个排序贪心的问题。比较难想，但是想通了之后就非常简单。

$1 题目

现在有一个尺寸为 width * height 的矩阵 M，矩阵中的每个单元格的值不是 0 就是 1。

而且矩阵 M 中每个大小为 sideLength * sideLength 的 正方形 子阵中，1 的数量不得超过 maxOnes。

请你设计一个算法，计算矩阵中最多可以有多少个 1。

提示：

1
2
3
1 <= width, height <= 100
1 <= sideLength <= width, height
0 <= maxOnes <= sideLength * sideLength

示例 1：
输入：width = 3, height = 3, sideLength = 2, maxOnes = 1
输出：4
解释：
题目要求：在一个 33 的矩阵中，每一个 22 的子阵中的 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]

$2 题解

算法：贪心

矩形宽W和高H, 小正方形边长 l。

考察最左上角的 l * l 正方形中的每个位置 (i, j)，看该点有多少个等效的点 (i + k * l, j + k * l)。

1
2
3
4
5
6
7
8
9
(i + k * l, j + k * l)
求最大的 ki 使得 i + ki * l <= W - 1
求最大的 kj 使得 j + kj * l <= H - 1

ki * l <= W - 1 - i
kj * l <= H - 1 - j

(i, j) 的等效点个数 (ki + 1) * (kj + 1)
取等效点个数最大的前 k 个

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
        vector<int> up_left(sideLength * sideLength);
        for(int i = 0; i < sideLength; ++i)
            for(int j = 0; j < sideLength; ++j)
            {
                int ki = (width - 1 - i) / sideLength;
                int kj = (height - 1 - j) / sideLength;
                up_left[i * sideLength + j] = (ki + 1) * (kj + 1);
            }
        nth_element(up_left.begin(), up_left.begin() + maxOnes, up_left.end(), greater<int>());
        int ans = 0;
        for(int i = 0; i < maxOnes; ++i)
            ans += up_left[i];
        return ans;
    }
};
Share