数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中最多翻转二进制矩阵 K 次后的最大分数
在这个问题中，我们给定一个由布尔值（即 0 和 1）组成的二维数组 arr[] 和一个整数 K。我们的任务是创建一个程序，在 C++ 中找到最多翻转二进制矩阵 K 次后的最大分数。
问题描述 - 在这里，对于二维数组和 k 次移动，我们需要找到由数组元素创建的数字。在每次移动中，我们将取一行或一列并翻转该行或列的所有元素。将进行选择以记住我们需要最大化在矩阵的行中进行 K 次翻转后创建的数字。我们需要返回每一行创建的所有数字的总和。
让我们举一个例子来理解这个问题，
输入
arr[][] = {
{1, 0, 0},
{0, 1, 1},
{1, 0, 1}
}
K = 2输出
19
解释
我们有两次翻转，
第一次翻转 - 我们将翻转第 2 行的元素。这将使数组变为，
{{1, 0, 0},
{1, 0, 0},
{1, 0, 1}}第二次翻转 - 我们将翻转第 2 列的元素。这将使数组变为，
{{1, 1, 0},
{1, 1, 0},
{1, 1, 1}}每一行创建的最终数字为 6、6、7。
Maximum sum = 19.
解决方案方法
为了解决这个问题，我们需要首先使第一列的元素为 1。因为第 i 列的 1 将贡献 2i，这将是最大的可能数字（如果考虑一个设置位）。因此，最左边的列需要具有最大数量的 1（设置位）以使总和最大化。然后，我们将转到每一行的其他元素。
要检查是否需要翻转行或列。我们需要检查该列中的其他值。即所有行的第一个元素。如果 0 的数量大于 1 的数量。我们将翻转列，否则翻转行。
为了解决这个问题，我们将使用 map 数据结构。
程序说明我们解决方案的工作原理，
示例
#include <bits/stdc++.h>
using namespace std;
const int row = 3;
const int col = 3;
int MaxSumAfterFlip(int mat[row][col], int K) {
map<int, int> flipValues;
int updateVal, MaxSum = 0;
for (int i = 0; i < row; ++i) {
if (mat[i][0] == 0) {
updateVal = 0;
for (int j = 1; j < col; ++j)
updateVal = updateVal + mat[i][j] * pow(2, col - j- 1);
flipValues[updateVal] = i;
}
}
map<int, int>::iterator it = flipValues.begin();
while (K > 0 && it != flipValues.end()) {
int updateIndex = it->second ;
for (int j = 0; j < col; ++j)
mat[updateIndex][j] = (mat[updateIndex][j] + 1) % 2;
it++;
K--;
}
MaxSum = 0;
int zeros, ones = 0;
for (int j = 0; j < col; ++j) {
zeros = ones = 0;
for (int i = 0; i < row; ++i) {
mat[i][j] == 0 ? zeros++ : ones++;
}
if (K > 0 && zeros > ones) {
MaxSum += zeros * pow(2, (col - j - 1));
K--;
}
else
MaxSum += ones * pow(2, (col - j - 1));
}
return MaxSum;
}
int main() {
int mat[row][col] = {{1, 0, 0 },{0, 1, 1},{1, 0, 1}};
int K = 2;
cout<<"The Maximum score after flipping the matrix atmost K times is "<<MaxSumAfterFlip(mat, K);
return 0;
}输出
The Maximum score after flipping the matrix atmost K times is 19
更新于: 2020 年 9 月 15 日
265 次查看
广告