LeetCode——2397. 被列覆盖的最多行数

2024-01-08 07:49:15

通过万岁!!!

  • 题目:给你一个二维数组,然后里面是0和1,然后让你从里面选择numSelect列,使得去掉选择的列以后不存在1的行的数量最少。
  • 思路:
    • 看到这个题目,本来以为是每一列求和以后相加然后贪心就完了,但是发现是不对的。也没有更好的思路,就想着暴力一下吧。之前也做过类似的,就是找到所有的可能,找最优解。这里需要用到递归找到所有的可能,我们把所有的可能都记录在一个一维数组中,数组的长度等于给定的二位数组的列。然后如果我们选择在的数量等于numSelect的话,就进行计算行数就好了。然后就是如何递归构造一维数组,
      • 首先是退出递归的条件:当选择完毕,也就是选择了numSelect个,或者剩余元素都选也达不到numSelect的时候就可以退出了。
      • 然后是递归干的事情:递归需要在一维数组中加入一个点,但是记得要回退。
      • 最后是入参:这个其实就根据自己用哪个就传哪个就好了,或者是弄成成员变量。
    • 在递归的时候,我们需要通过for来不断的往数组中添加元素,为了不重复出现相同的情况,这个for的起始位置需要进行设定,每次递归这个for的起始位置都+1。并且将剩余元素达不到numSelect的退出条件写在for的判断中。
    • 然后就是选择完以后如果统计结果,这里我使用了一个set,我们只需要遍历选择的列数组,统计不选择的列中行是1的行号,最后返回行数减去set的长度即可。其实这里不用set也可以,我们只需要遍历二维数组,如果存在1,并且没有被选中,则num+1,但是记得要退出列的循环,因为这一行只要有一个1就num+1就好了。
  • 技巧:递归

java代码——使用set

class Solution {
    int n, m, max = Integer.MIN_VALUE;
    int[][] myMatrix;

    public int maximumRows(int[][] matrix, int numSelect) {
        myMatrix = matrix;
        n = matrix.length;
        m = matrix[0].length;
        int[] choice = new int[m];
        fun(choice, numSelect, 0);
        return max;
    }

    public void fun(int[] choice, int numSelect, int begin) {
        if (numSelect == 0) {
            max = Math.max(max, computerRowNum(choice));
            return;
        }
        for (int i = begin; i < m && numSelect <= m - i; i++) {
            if (choice[i] == 1) {
                continue;
            }
            choice[i] = 1;
            fun(choice, numSelect - 1, i + 1);
            choice[i] = 0;
        }
    }

    public int computerRowNum(int[] choice) {
        Set<Integer> existRow = new HashSet<>();
        // 不选的列中,那些行是1
        for (int i = 0; i < m; i++) {
            if (choice[i] == 0) {
                for (int j = 0; j < n; j++) {
                    if (myMatrix[j][i] == 1) {
                        existRow.add(j);
                    }
                }
            }
        }
        return n - existRow.size();
    }
}

java代码——不使用set

class Solution {
    int n, m, max = Integer.MIN_VALUE;
    int[][] myMatrix;

    public int maximumRows(int[][] matrix, int numSelect) {
        myMatrix = matrix;
        n = matrix.length;
        m = matrix[0].length;
        int[] choice = new int[m];
        fun(choice, numSelect, 0);
        return max;
    }

    public void fun(int[] choice, int numSelect, int begin) {
        if (numSelect == 0) {
            max = Math.max(max, computerRowNum(choice));
            return;
        }
        for (int i = begin; i < m && numSelect <= m - i; i++) {
            if (choice[i] == 1) {
                continue;
            }
            choice[i] = 1;
            fun(choice, numSelect - 1, i + 1);
            choice[i] = 0;
        }
    }

    public int computerRowNum(int[] choice) {
        int num = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (myMatrix[i][j] == 1 && choice[j] == 0) {
                    num++;
                    break;
                }
            }
        }
        return n - num;
    }
}
  • 总结:题目还是比较挺有意思的,而且递归的代码写出来以后确实给人一种赏心悦目的感觉。

文章来源:https://blog.csdn.net/qq_39056803/article/details/135398814
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。