企业 网站 推广,旅游网站建设规范,网站建设宣传psd,无极电影网手机在线观看2024.1.4 题目来源我的题解方法一 回溯位运算优化 题目来源
力扣每日一题#xff1b;题序#xff1a;2397
我的题解
方法一 回溯位运算优化 这道题一看就会想到使用回溯法#xff0c;但是采用回溯法后如何判断有多少行被覆盖#xff0c;直接计算矩阵时间复杂度较高… 2024.1.4 题目来源我的题解方法一 回溯位运算优化 题目来源
力扣每日一题题序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;}
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
