当前位置：首页 > news >正文

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

news 2025/8/17 9:26:53

通过万岁！！！

题目：给你一个二维数组，然后里面是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<>();// 不选的列中，那些行是1for (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;}
}