C ++中的最大位数

假设我们有一个维度为wxh的矩阵M，使得每个像元的值为0或1，并且大小为1xl的M的任何正方形子矩阵最多具有maxOnes个数。我们必须找到矩阵M可以具有的最大可能数目。

因此，如果输入像w = 3，h = 3，l = 2，maxOnes = 1，那么输出将是3（如3 * 3矩阵），则2 * 2子矩阵不能有超过1。有4个的最好的解决方案是-

为了解决这个问题，我们将遵循以下步骤-

• ret：= 0

• 制作一个大小为nxn的2D数组平方

• 对于初始化i：= 0，当i <height时，更新（将i增加1），执行-

• 将sq [i mod n，j mod n]增加1

• 对于初始化j：= 0，当j <width时，更新（将j增加1），执行-

• 定义数组v

• 对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

• 在v的末尾插入sq [i，j]

• 对于初始化j：= 0，当j <n时，更新（将j增加1），执行-

• 以相反的顺序对数组v排序

• 对于初始化i：= 0，j：= 0，当i <v的大小且j <maxOnes时，更新（i增加1），（j增加1），-

• 返回ret

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maximumNumberOfOnes(int width, int height, int n, int maxOnes) {
      int ret = 0;
      vector < vector <int> > sq(n, vector <int>(n));
      for(int i = 0; i < height; i++){
         for(int j = 0; j < width; j++){
            sq[i % n][j % n]++;
         }
      }
      vector <int> v;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < n ; j++){
            v.push_back(sq[i][j]);
         }
      }
      sort(v.rbegin(), v.rend());
      for(int i = 0, j = 0; i < v.size() && j < maxOnes; i++, j++){
         ret += v[i];
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.maximumNumberOfOnes(3,3,2,1));
}

输入值

3, 3, 2, 1

输出结果

4