企业建设网站费用,签名设计网站,网站维护一年一般多少钱?,什么网站排名做的最好通过万岁#xff01;#xff01;#xff01;
题目#xff1a;给你一个二维数组#xff0c;然后里面是0和1#xff0c;然后让你从里面选择numSelect列#xff0c;使得去掉选择的列以后不存在1的行的数量最少。思路#xff1a; 看到这个题目#xff0c;本来以为是每一列…通过万岁
题目给你一个二维数组然后里面是0和1然后让你从里面选择numSelect列使得去掉选择的列以后不存在1的行的数量最少。思路 看到这个题目本来以为是每一列求和以后相加然后贪心就完了但是发现是不对的。也没有更好的思路就想着暴力一下吧。之前也做过类似的就是找到所有的可能找最优解。这里需要用到递归找到所有的可能我们把所有的可能都记录在一个一维数组中数组的长度等于给定的二位数组的列。然后如果我们选择在的数量等于numSelect的话就进行计算行数就好了。然后就是如何递归构造一维数组 首先是退出递归的条件当选择完毕也就是选择了numSelect个或者剩余元素都选也达不到numSelect的时候就可以退出了。然后是递归干的事情递归需要在一维数组中加入一个点但是记得要回退。最后是入参这个其实就根据自己用哪个就传哪个就好了或者是弄成成员变量。 在递归的时候我们需要通过for来不断的往数组中添加元素为了不重复出现相同的情况这个for的起始位置需要进行设定每次递归这个for的起始位置都1。并且将剩余元素达不到numSelect的退出条件写在for的判断中。然后就是选择完以后如果统计结果这里我使用了一个set我们只需要遍历选择的列数组统计不选择的列中行是1的行号最后返回行数减去set的长度即可。 技巧递归
java代码
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) {SetInteger 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();}
}总结题目还是比较挺有意思的而且递归的代码写出来以后确实给人一种赏心悦目的感觉。
