2024.1.4力扣每日一题——被列覆盖的最多行数
2024-01-07 21:32:09
2024.1.4
题目来源
我的题解
方法一 回溯+位运算优化
这道题一看就会想到使用回溯法,但是采用回溯法后如何判断有多少行被覆盖,直接计算矩阵时间复杂度较高,因此可以将0-1矩阵的每一行抽象为一个整数R,以及将选中列形成的整数L,然后根据位运算计算 R^L 是否等于R本身,若等于本身则表示该行被覆盖,然后在回溯过程中更新最终结果
时间复杂度:O(m× 2 n 2^n 2n)
空间复杂度:O(m)。矩阵的行转换为整数需要的空间
int ans = 0;
public int maximumRows(int[][] matrix, int numSelect) {
int m = matrix.length, n = matrix[0].length;
if (n <= numSelect) return m;
int[] nums = new int[m];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 1) nums[i] |= 1 << j;
}
}
backTrace(n - 1, m, nums, numSelect);
return ans;
}
public void backTrace(int n, int m, int[] nums, int numSelect) {
// 当给定的列数选完或者矩阵的列遍历完,更新结果
if (n < 0 || numSelect == 0) {
int c = 0;
//计算覆盖的行数
for (int num : nums) if (num == 0) c++;
ans = Math.max(ans, c);
return;
}
//不选择第n列 并缩小列的范围
backTrace(n - 1, m, nums, numSelect);
// modify表示选中的列的二进制数对应的整数
int modify = 0, index = 0;
//把对应列上的1去除
for (int i = 0; i < m; i++) {
if (((nums[i] >> n) & 1) == 1) {
nums[i] ^= 1 << n;
modify |= 1 << i;
}
}
//选择第n列 并缩小列的范围
backTrace(n - 1, m, nums, numSelect - 1);
// 回退
while (modify > 0 && index < m) {
if ((modify & 1) == 1) {
nums[index] |= 1 << n;
}
modify = modify >> 1;
index++;
}
}
有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~
文章来源:https://blog.csdn.net/weixin_42075274/article/details/135444184
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!