算法题:翻转列
假设我们有一个由 0 和 1 组成的 mxn 网格,并且想要转换该网格,以便最大行数仅由 1 组成。我们被允许在网格上执行的唯一操作是选择某个列并翻转该列中的所有零和一。我们还得到了一些整数 k,并且必须精确执行 k 列翻转。给定网格和 k 值,我们如何确定翻转哪些列以最大化全为 1 的行数?
我认为需要做一些动态的事情,但我无法得出一个好的答案。有人可以帮忙吗?
Suppose that we are given an m x n grid of zeros and ones and want to transform the grid so that the maximum number of rows are composed solely of ones. The only operation we are allowed to perform on the grid is picking some column and flipping all of the zeros and ones in that column. We are also given some integer k and must perform exactly k columns flips. Given the grid and the value of k, how do we determine which columns to flip to maximize the number of rows that are all ones?
I'm thinking something dynamic would need to be done, but I'm not able to arrive at a good answer. Can someone help out?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(6)
这可能是可能的代码:
int candidateRowCount=0;
void populateHash(int *input, int **hash, int col)
{
bool found = false;
for (int i=0; i<candidateRowCount; i++)
{
for (int j=0; j<col; j++)
{
if(input[j] !=hash[i][j])
break;
else
{
if (j==(col-1))
{
found = true;
hash[i][col] +=1;
}
}
}
}
if (!found)
{ // save current candidate Row in hash to be used for comparison in else block of above steps of this function
for (int i=0; i<col; i++)
{
hash[candidateRowCount][i] = input[i];
}
hash[candidateRowCount][col] +=1;
candidateRowCount++;
}
}
int getMaxCount(int** input, int N , int M, int K)
{
int **hash= new int *[N];
// an extra column to save frequency of row i
for(int i=0; i<M+1; i++)
{
hash[i]= new int[M+1];
hash[i][M] =0;
}
for(int i=0; i<N; i++)
for(int j=0; i<M; j++)
hash[i][j]=0;
for(int i=0; i<N; i++)
{
int count = 0;
for (int j=0; j<M; j++)
{
if(input[i][j]==0)
count++;
}
if(count<=K)
{
int diff= K-count;
if ((diff >= 0) && ((diff %2)== 0))
{
populateHash(input[i], hash, M);
}
}
}
int maxVal = 0;
for (int i=0; i<candidateRowCount; i++)
{
if(hash[i][M]>maxVal)
maxVal = hash[i][M];
}
return maxVal;
}
int main()
{
freopen("input.txt", "r", stdin);
int testcase;
cin >> testcase;
for (int t=0; t<testcase; t++)
{
int N,M,K;
cin >> N >>M;
cin >>K;
int **input = new int *[N];
for (int i=0; i<N; i++)
input[i] = new int [M];
for (int i=0; i<N; i++)
{
for (int j=0; j<M; j++)
{
cin >> input[i][j];
}
}
int val= getMaxCount(input, N, M, K);
cout << "Max Val" <<val << endl;
candidateRowCount= 0;
}
return 0;
}
#include <iostream>
using namespace std;
// Solved in O(n*m)
int count_normal(int **mat, int n, int m)
{
int count = 0;
for (int i = 0; i < n; i++)
{
int tempCount = 0;
for (int j = 0; j < m; j++)
tempCount += mat[i][j];
if (tempCount == m)
count += 1;
}
return count;
}
int *rowWiseSum(int **mat, int n, int m)
{
int *rowwisesum = new int[n];
for (int i = 0; i < n; i++)
{
int tempSum = 0;
for (int j = 0; j < m; j++)
tempSum += mat[i][j];
rowwisesum[i] = tempSum;
}
return rowwisesum;
}
int count_toggled(int *rowwisesum, int **mat, int toggle, int n, int m)
{
int count = 0;
for(int i=0; i<n; i++){
if(mat[i][toggle]==1){
rowwisesum[i]-=1;
}else{
rowwisesum[i]+=1;
}
}
for(int i=0; i<n; i++){
if(rowwisesum[i]==m)
count+=1;
}
//resetting rowwisesum
for (int i = 0; i < n; i++){
if (mat[i][toggle] == 1){
rowwisesum[i] += 1;
}else{
rowwisesum[i] -= 1;
}
}
return count;
}
int main()
{
int n, m, k;
cout << "Enter the value of N : ";
cin >> n;
cout << "Enter the value of M : ";
cin >> m;
cout << "Enter the value of k : ";
cin >> k;
int **mat = new int *[n];
for (int i = 0; i < n; i++)
{
mat[i] = new int[m];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
cin >> mat[i][j];
}
// for (int i = 0; i < n; i++){
// for (int j = 0; j < m; j++)
// cout << mat[i][j]<<" ";
// cout<<endl;
// }
int normalCount = count_normal(mat, n, m);
if (k % 2 == 0)
{
cout << normalCount << endl;
}
else
{
int *rowwisesum = rowWiseSum(mat, n, m);
int maxCount = normalCount, toggled = -1;
for (int i = 0; i < m; i++)
{
int count = count_toggled(rowwisesum, mat, i, n, m);
if (count > maxCount)
{
maxCount = count;
toggled = i;
}
}
cout << "\n\nMaxRowsWithAll1 = " << maxCount << " Upon toggling column " << toggled + 1 << ", " << k << " times" << endl;
}
return 0;
}
Python 中简短而清晰的实现
t = int(input())
def getMaxCount(inp_arr,N,M,K):
hash_map = dict()
for row in inp_arr:
hash_map[str(row)] = 0
for row in inp_arr:
zeros = row.count(0)
if (zeros <= k and (k-zeros)%2==0):
hash_map[str(row)] += 1
return max(hash_map.values())
for _ in range(t):
n,m,k = map(int,input().split())
inp_arr=[]
for i in range(n):
sub = list(map(int,input().split()))
inp_arr.append(sub)
ans = getMaxCount(inp_arr,n,m,k)
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
让我们首先考虑问题的一个重要细节:如果两行包含行间不同的列(例如,在一行中它是零,在一行中它是一),那么就没有可能的方法使两行都是 1。为了看到这一点,假设 x 行在某列中有一个 0,而 y 行在该列中有一个 1。然后,如果我们不翻转该列,则行 x 不能全为 1,如果我们翻转该列,则行 y 不能全为 1。因此,如果我们查看原始矩阵并尝试考虑哪些行全部为 1,我们本质上只是选择一些彼此相等的行集。我们的目标是选择尽可能大的一组相同的行,并且可以使用恰好 k 次翻转将其变成所有行。假设可以使用恰好 k 次翻转将其变成所有行的行是“候选行”。那么我们只需要找到矩阵中出现次数最多的候选行即可。
执行此操作的实际算法取决于是否允许我们将同一列翻转两次。如果不是,那么候选行就是其中正好有 k 个零的行。如果我们可以多次翻转同一列,那么这就有点棘手了。为了使该行全为 1,我们需要将每个 0 转换为 1,然后需要继续花费剩余的翻转次数来翻转同一列两次,以避免将任何 1 更改为 0。如果 k 与行中零的数量之间的差是非负偶数,则这种情况成立。
使用它,我们得到以下算法:
总的来说,在 mxn 矩阵(m 行,n 列)上,我们每行访问一次。在访问期间,我们执行 O(n) 工作来计算零的数量,然后执行 O(1) 工作来查看它是否有效。如果是这样,则更新哈希表需要预计的 O(n) 时间,因为哈希步骤需要 O(n) 时间来哈希该行。这意味着我们花费 O(mn) 时间填写表格。最后,最后一步需要时间 O(m) 来查找最大频率行,净运行时间为 O(mn),与输入大小呈线性关系。此外,这是渐近最优的,因为如果我们花费的时间少于这个时间,我们就无法查看矩阵元素!
希望这有帮助!这是一个很酷的问题!
Let's begin by thinking about an important detail of the problem: if two rows contain a column that differ across the rows (for example, in one row it's a zero and in one row it's a one), then there is no possible way to make both rows all ones. To see this, suppose that row x has a zero in some column and row y has a one in that column. Then if we don't flip that column, row x can't be all ones, and if we do flip the column then row y can't be all ones. Consequently, if we take a look at the original matrix and try to think about what rows we are going to make all ones, we are essentially just going to pick some set of rows that are all equal to one another. Our goal is then to pick the set of identical rows that is as large as possible and can be made into all ones using exactly k flips. Let's say that a row that can be made into all ones using exactly k flips is a "candidate row.". Then we just need to find the candidate row in the matrix that appears the greatest number of times.
The actual algorithm for doing this depends on whether or not we are allowed to flip the same column twice. If we aren't, then a candidate row is one that has exactly k zeros in it. If we can flip the same column multiple times, then this is a bit trickier. To make the row all ones, we would need to convert each zero to a one, then would need to keep spending the remaining flips flipping the same column twice to avoid changing any one to a zero. This is true if the difference between k and the number of zeros in the row is a nonnegative even number.
Using this, we get the following algorithm:
Overall, on an m x n matrix (m rows, n columns), we visit each row once. During the visit, we do O(n) work to count the number of zeros, then O(1) work to see if it is valid. If so, it takes an expected O(n) time to update the hash table, since the hashing step takes O(n) time to hash the row. This means that we spend O(mn) time filling in the table. Finally, the last step takes time O(m) to find the max frequency row, for a net runtime of O(mn), which is linear in the size of the input. Moreover, this is asymptotically optimal, since if we spent less time than this we couldn't look at al, the matrix elements!
Hope this helps! This is a cool problem!