2024.1.4力扣每日一题——被列覆盖的最多行数

2024-01-07 21:32:09

题目来源

力扣每日一题;题序:2397

我的题解

方法一 回溯+位运算优化

这道题一看就会想到使用回溯法,但是采用回溯法后如何判断有多少行被覆盖,直接计算矩阵时间复杂度较高,因此可以将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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。