class081 状压dp-下【算法】
Code1 1434. 每个人戴不同帽子的方案数
// 每个人戴不同帽子的方案数
// 总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40
// 给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表
// 请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数
// 由于答案可能很大，请返回它对10^9+7取余后的结果
// 测试链接 : https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-other
package class081; import java.util.Arrays; import java.util.List; // 每个人戴不同帽子的方案数 // 总共有 n 个人和 40 种不同的帽子，帽子编号从 1 到 40 // 给你一个整数列表的列表 hats ，其中 hats[i] 是第 i 个人所有喜欢帽子的列表 // 请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数 // 由于答案可能很大，请返回它对10^9+7取余后的结果 // 测试链接 : https://leetcode.cn/problems/number-of-ways-to-wear-different-hats-to-each-other public class Code01_NumberOfWaysWearDifferentHats { public static int MOD = 1000000007; public static int numberWays(List<List<Integer>> arr) { // 帽子颜色的最大值 int m = 0; for (List<Integer> person : arr) { for (int hat : person) { m = Math.max(m, hat); } } int n = arr.size(); // 1 ~ m 帽子，能满足哪些人，状态信息 -> int int[] hats = new int[m + 1]; for (int pi = 0; pi < n; pi++) { for (int hat : arr.get(pi)) { hats[hat] |= 1 << pi; } } int[][] dp = new int[m + 1][1 << n]; for (int i = 0; i <= m; i++) { Arrays.fill(dp[i], -1); } return f2(hats, m, n, 1, 0, dp); } // m : 帽子颜色的最大值, 1 ~ m // n : 人的数量，0 ~ n-1 // i : 来到了什么颜色的帽子 // s : n个人，谁没满足状态就是0，谁满足了状态就是1 // dp : 记忆化搜索的表 // 返回 : 有多少种方法 public static int f1(int[] hats, int m, int n, int i, int s, int[][] dp) { if (s == (1 << n) - 1) { return 1; } // 还有人没满足 if (i == m + 1) { return 0; } if (dp[i][s] != -1) { return dp[i][s]; } // 可能性1 : i颜色的帽子，不分配给任何人 int ans = f1(hats, m, n, i + 1, s, dp); // 可能性2 : i颜色的帽子，分配给可能的每一个人 int cur = hats[i]; // 用for循环从0 ~ n-1枚举每个人 for (int p = 0; p < n; p++) { if ((cur & (1 << p)) != 0 && (s & (1 << p)) == 0) { ans = (ans + f1(hats, m, n, i + 1, s | (1 << p), dp)) % MOD; } } dp[i][s] = ans; return ans; } public static int f2(int[] hats, int m, int n, int i, int s, int[][] dp) { if (s == (1 << n) - 1) { return 1; } if (i == m + 1) { return 0; } if (dp[i][s] != -1) { return dp[i][s]; } int ans = f2(hats, m, n, i + 1, s, dp); int cur = hats[i]; // 不用for循环枚举 // 从当前帽子中依次提取能满足的人 // 提取出二进制状态中最右侧的1，讲解030-异或运算，题目5，Brian Kernighan算法 // cur : // 0 0 0 1 1 0 1 0 // -> 0 0 0 0 0 0 1 0 // -> 0 0 0 0 1 0 0 0 // -> 0 0 0 1 0 0 0 0 int rightOne; while (cur != 0) { rightOne = cur & -cur; if ((s & rightOne) == 0) { ans = (ans + f2(hats, m, n, i + 1, s | rightOne, dp)) % MOD; } cur ^= rightOne; } dp[i][s] = ans; return ans; } }
Code2 465.最优账单平衡
// 最优账单平衡
// 给你一个表示交易的数组 transactions
// 其中 transactions[i] = [fromi, toi, amounti]
// 表示 ID = fromi 的人给 ID = toi 的人共计 amounti
// 请你计算并返回还清所有债务的最小交易笔数
// 测试链接 : https://leetcode.cn/problems/optimal-account-balancing/
465 最优账单平衡 困难
给你一个表示交易的数组 transactions ，其中 transactions[i] = [fromi，toi， amounti] 表示 ID =fromi的人给ID = toi的人共计amounti $
请你计算并返回还清所有债务的最小交易笔数
示例 1:
输入: transactions = [[0,1,10]，[2,0,5]] 输出:2 解释: #0给#1 $10 #2给#0 $5 需要进行两笔交易。一种结清债务的方式是 #1 给 #0 和 #2 各$5
package class081; import java.util.Arrays; // 最优账单平衡 // 给你一个表示交易的数组 transactions // 其中 transactions[i] = [fromi, toi, amounti] // 表示 ID = fromi 的人给 ID = toi 的人共计 amounti // 请你计算并返回还清所有债务的最小交易笔数 // 测试链接 : https://leetcode.cn/problems/optimal-account-balancing/ public class Code02_OptimalAccountBalancing { // 题目说了人员编号的最大范围：0 ~ 12 public static int MAXN = 13; public static int minTransfers(int[][] transactions) { // 加工出来的debt数组中一定不含有0 int[] debt = debts(transactions); int n = debt.length; int[] dp = new int[1 << n]; Arrays.fill(dp, -1); return n - f(debt, (1 << n) - 1, 0, n, dp); } public static int[] debts(int[][] transactions) { int[] help = new int[MAXN]; for (int[] tran : transactions) { help[tran[0]] -= tran[2]; help[tran[1]] += tran[2]; } int n = 0; for (int num : help) { if (num != 0) { n++; } } int[] debt = new int[n]; int index = 0; for (int num : help) { if (num != 0) { debt[index++] = num; } } return debt; } public static int f(int[] debt, int set, int sum, int n, int[] dp) { if (dp[set] != -1) { return dp[set]; } int ans = 0; if ((set & (set - 1)) != 0) { // 集合中不只一个元素 if (sum == 0) { for (int i = 0; i < n; i++) { if ((set & (1 << i)) != 0) { // 找到任何一个元素，去除这个元素 // 剩下的集合进行尝试，返回值 + 1 ans = f(debt, set ^ (1 << i), sum - debt[i], n, dp) + 1; // 然后不需要再尝试下一个元素了，因为答案一定是一样的 // 所以直接break break; } } } else { for (int i = 0; i < n; i++) { if ((set & (1 << i)) != 0) { ans = Math.max(ans, f(debt, set ^ (1 << i), sum - debt[i], n, dp)); } } } } dp[set] = ans; return ans; } }
Code3 1994. 好子集的数目
// 好子集的数目
// 给你一个整数数组 nums，好子集的定义如下：
// nums的某个子集，所有元素的乘积可以表示为一个或多个互不相同质数的乘积
// 比如nums = [1, 2, 3, 4]
// [2, 3]，[1, 2, 3]，[1, 3] 是好子集
// 乘积分别为6=23，6=23，3=3
// [1, 4]和[4]不是好子集，因为乘积分别为4=22和4=22
// 请你返回nums中不同的好子集的数目对10^9+7取余的结果
// 如果两个子集删除的下标不同，那么它们被视为不同的子集
// 测试链接 : https://leetcode.cn/problems/the-number-of-good-subsets/
package class081; import java.util.Arrays; // 好子集的数目 // 给你一个整数数组 nums，好子集的定义如下： // nums的某个子集，所有元素的乘积可以表示为一个或多个互不相同质数的乘积 // 比如nums = [1, 2, 3, 4] // [2, 3]，[1, 2, 3]，[1, 3] 是好子集 // 乘积分别为6=2*3，6=2*3，3=3 // [1, 4]和[4]不是好子集，因为乘积分别为4=2*2和4=2*2 // 请你返回nums中不同的好子集的数目对10^9+7取余的结果 // 如果两个子集删除的下标不同，那么它们被视为不同的子集 // 测试链接 : https://leetcode.cn/problems/the-number-of-good-subsets/ public class Code03_TheNumberOfGoodSubsets { public static int MAXV = 30; public static int LIMIT = (1 << 10); public static int MOD = 1000000007; // 打个表来加速判断 // 如果一个数字拥有某一种质数因子不只1个 // 那么认为这个数字无效，状态全是0，0b0000000000 // 如果一个数字拥有任何一种质数因子都不超过1个 // 那么认为这个数字有效，用位信息表示这个数字拥有质数因子的状态 // 比如12，拥有2这种质数因子不只1个，所以无效，用0b0000000000表示 // 比如14，拥有2这种质数因子不超过1个，拥有7这种质数因子不超过1个，有效 // 从高位到低位依次表示：...13 11 7 5 3 2 // 所以用0b0000001001表示14拥有质数因子的状态 // 质数: 29 23 19 17 13 11 7 5 3 2 // 位置: 9 8 7 6 5 4 3 2 1 0 public static int[] own = { 0b0000000000, // 0 0b0000000000, // 1 0b0000000001, // 2 0b0000000010, // 3 0b0000000000, // 4 0b0000000100, // 5 0b0000000011, // 6 0b0000001000, // 7 0b0000000000, // 8 0b0000000000, // 9 0b0000000101, // 10 0b0000010000, // 11 0b0000000000, // 12 0b0000100000, // 13 0b0000001001, // 14 0b0000000110, // 15 0b0000000000, // 16 0b0001000000, // 17 0b0000000000, // 18 0b0010000000, // 19 0b0000000000, // 20 0b0000001010, // 21 0b0000010001, // 22 0b0100000000, // 23 0b0000000000, // 24 0b0000000000, // 25 0b0000100001, // 26 0b0000000000, // 27 0b0000000000, // 28 0b1000000000, // 29 0b0000000111 // 30 }; // 记忆化搜索 public static int numberOfGoodSubsets1(int[] nums) { // 1 ~ 30 int[] cnt = new int[MAXV + 1]; for (int num : nums) { cnt[num]++; } int[][] dp = new int[MAXV + 1][LIMIT]; for (int i = 0; i <= MAXV; i++) { Arrays.fill(dp[i], -1); } int ans = 0; for (int s = 1; s < LIMIT; s++) { ans = (ans + f1(MAXV, s, cnt, dp)) % MOD; } return ans; } // 1....i范围的数字，每种数字cnt[i]个 // 最终相乘的结果一定要让质因子的状态为s，且每种质因子只能有1个 // 请问子集的数量是多少 // s每一位代表的质因子如下 // 质数: 29 23 19 17 13 11 7 5 3 2 // 位置: 9 8 7 6 5 4 3 2 1 0 public static int f1(int i, int s, int[] cnt, int[][] dp) { if (dp[i][s] != -1) { return dp[i][s]; } int ans = 0; if (i == 1) { if (s == 0) { ans = 1; for (int j = 0; j < cnt[1]; j++) { ans = (ans << 1) % MOD; } } } else { ans = f1(i - 1, s, cnt, dp); int cur = own[i]; int times = cnt[i]; if (cur != 0 && times != 0 && (s & cur) == cur) { // 能要i这个数字 ans = (int) (((long) f1(i - 1, s ^ cur, cnt, dp) * times + ans) % MOD); } } dp[i][s] = ans; return ans; } // 空间压缩优化 public static int[] cnt = new int[MAXV + 1]; public static int[] dp = new int[LIMIT]; public static int numberOfGoodSubsets2(int[] nums) { Arrays.fill(cnt, 0); Arrays.fill(dp, 0); for (int num : nums) { cnt[num]++; } dp[0] = 1; for (int i = 0; i < cnt[1]; i++) { dp[0] = (dp[0] << 1) % MOD; } for (int i = 2, cur, times; i <= MAXV; i++) { cur = own[i]; times = cnt[i]; if (cur != 0 && times != 0) { for (int status = LIMIT - 1; status >= 0; status--) { if ((status & cur) == cur) { dp[status] = (int) (((long) dp[status ^ cur] * times + dp[status]) % MOD); } } } } int ans = 0; for (int s = 1; s < LIMIT; s++) { ans = (ans + dp[s]) % MOD; } return ans; } }
Code4 1655. 分配重复整数
// 分配重复整数
// 给你一个长度为n的整数数组nums，这个数组中至多有50个不同的值
// 同时你有m个顾客的订单quantity，其中整数quantity[i]是第i位顾客订单的数目
// 请你判断是否能将nums中的整数分配给这些顾客，且满足：
// 第i位顾客恰好有quantity[i]个整数、第i位顾客拿到的整数都是相同的
// 每位顾客都要满足上述两个要求，返回是否能都满足
// 测试链接 : https://leetcode.cn/problems/distribute-repeating-integers/
package class081; import java.util.Arrays; // 分配重复整数 // 给你一个长度为n的整数数组nums，这个数组中至多有50个不同的值 // 同时你有m个顾客的订单quantity，其中整数quantity[i]是第i位顾客订单的数目 // 请你判断是否能将nums中的整数分配给这些顾客，且满足： // 第i位顾客恰好有quantity[i]个整数、第i位顾客拿到的整数都是相同的 // 每位顾客都要满足上述两个要求，返回是否能都满足 // 测试链接 : https://leetcode.cn/problems/distribute-repeating-integers/ public class Code04_DistributeRepeatingIntegers { // 时间复杂度O(n * 3的m次方)，空间复杂度O(n * 2的m次方) // ppt上有时间复杂度解析 public static boolean canDistribute(int[] nums, int[] quantity) { Arrays.sort(nums); int n = 1; for (int i = 1; i < nums.length; i++) { if (nums[i - 1] != nums[i]) { n++; } } int[] cnt = new int[n]; int c = 1; for (int i = 1, j = 0; i < nums.length; i++) { if (nums[i - 1] != nums[i]) { cnt[j++] = c; c = 1; } else { c++; } } cnt[n - 1] = c; int m = quantity.length; int[] sum = new int[1 << m]; // 下面这个枚举是生成quantity中的每个子集，所需要数字的个数 for (int i = 0, v, h; i < quantity.length; i++) { v = quantity[i]; h = 1 << i; for (int j = 0; j < h; j++) { sum[h | j] = sum[j] + v; } } int[][] dp = new int[1 << m][n]; return f(cnt, sum, (1 << m) - 1, 0, dp); } // 当前来到的数字，编号index，个数cnt[index] // status : 订单状态，1还需要去满足，0已经满足过了 public static boolean f(int[] cnt, int[] sum, int status, int index, int[][] dp) { if (status == 0) { return true; } // status != 0 if (index == cnt.length) { return false; } if (dp[status][index] != 0) { return dp[status][index] == 1; } boolean ans = false; int k = cnt[index]; // 这是整个实现最核心的枚举 // j枚举了status的所有子集状态 // 建议记住 for (int j = status; j > 0; j = (j - 1) & status) { if (sum[j] <= k && f(cnt, sum, status ^ j, index + 1, dp)) { ans = true; break; } } if (!ans) { ans = f(cnt, sum, status, index + 1, dp); } dp[status][index] = ans ? 1 : -1; return ans; } }
2023-12-05 16:04:48
