資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告