借用评论区一位哥们的说法就是:假设有一个m*n的草坪,每块草坪分为有僵尸(1)和每僵尸(0)的情况,现在有numslect个竖排生效的火爆辣椒,问在哪几竖排使用火爆辣椒可以保住最多的小推车
思路:根据提示知道范围不大,可以暴力求解,首先将每一行的情况作为一个二进制数保存起来,例如:
如图所示,每位数的二进制位都对应则数组中一行的1和0分布情况,这样就可以使用一个一维数组来存储数组中的每行
那么该如何枚举所有情况呢?假设对应二进制为1则代表此列被选中,假设我们的数组有n列,那么只需要在1<<n之内遍历每个数,就可以列举出n列之内所有选中列的情况了
显然,这样穷举所有情况并不会或者说大多数时候选中的列数都不符合题目规定的要求,此时只需考虑选中列数 == 题目要求选中列数的情况,因为二进制位中为1则代表该列被选中,所以只需要判断该数二进制位1的个数是否等于题目要求就行了
__builtin_popcount()函数,功能为返回括号中的数的二进制位1的个数
那么就只剩最后一个问题,遍历每种情况时,如何判断当前情况被覆盖的行(该行没有僵尸即视为为被覆盖)的数量
假设使用了rows[]数组用二进制方式存储了数组的每一行,那么我们只需要逐个遍历rows[]中的数,并与当前遍历到的代表选中行的情况的数做对比,判断该行是否被覆盖就ok了,至于如何判断,只需要将rows[i]与代表当前选中情况的数做一个&运算然后再比较rows[i]是否发生变化就解决了
准备一个变量来记录当前被覆盖行数,再准备一个变量记录最大被覆盖行数然后返回即可
代码:
class Solution {
public:
int maximumRows(vector<vector<int>>& matrix, int numSelect) {
int col = matrix[0].size(); //数组列数
int row = matrix.size(); //数组行数
vector<int> rows(row,0); //用二进制记录每行情况
for(int i = 0; i < row; i++) //记录每行情况
for(int j = 0; j < col; j++){
rows[i] <<= 1; //先左移一位
if(matrix[i][j]) rows[i] |= 1; //如果要记录的值为1则|1,也就是对应二进制位赋1,否则为0
}
int maxrow = 0; //记录最大被覆盖行数
for(int cols = 1; cols < 1 << col; cols++){ //枚举每种情况
if(__builtin_popcount(cols) == numSelect){ //只有满足题意的选中列数才计算
int t = 0; //存储当前情况的被覆盖行数
for(int r : rows){ //遍历每行
t += (r & cols) == r; //是否被覆盖
}
maxrow = max(maxrow,t); //记录最大被覆盖行数
}
}
return maxrow;
}
};