13.二进制枚举练习题

文章目录

二进制枚举练习题
- [78. 子集](https://leetcode.cn/problems/subsets/)
- [77. 组合](https://leetcode.cn/problems/combinations/)
- [1286. 字母组合迭代器](https://leetcode.cn/problems/iterator-for-combination/)
- [2397. 被列覆盖的最多行数](https://leetcode.cn/problems/maximum-rows-covered-by-columns/)
- [2212. 射箭比赛中的最大得分](https://leetcode.cn/problems/maximum-points-in-an-archery-competition/)
- [1601. 最多可达成的换楼请求数目](https://leetcode.cn/problems/maximum-number-of-achievable-transfer-requests/)
- [2959. 关闭分部的可行集合数目](https://leetcode.cn/problems/number-of-possible-sets-of-closing-branches/)

二进制枚举练习题

1、从空集枚举到全集

for (int s = 0; s < (1 << n); s++) {// 处理 s 的逻辑
}

2、遍历集合

设元素范围从 0 到 n−1，挨个判断元素是否在集合 s 中：

for (int i = 0; i < n; i++) {if (((s >> i) & 1) == 1) { // i 在 s 中// 处理 i 的逻辑}
}

题单

https://leetcode.cn/problems/number-of-possible-sets-of-closing-branches/solutions/2560722/er-jin-zhi-mei-ju-floydgao-xiao-xie-fa-f-t7ou/

78. 子集
77. 组合
1286. 字母组合迭代器 1591
2397. 被列覆盖的最多行数 1719
2212. 射箭比赛中的最大得分 1869
1601. 最多可达成的换楼请求数目 2119
2959. 关闭分部的可行集合数目

78. 子集

中等

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

// 位运算优化
class Solution {public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> res = new ArrayList<>();int n = nums.length;// 从空集枚举到全集for(int s = 0; s < (1 << n); s++){List<Integer> tmp = new ArrayList<>();// 遍历集合for(int j = 0; j < n; j++){if(((s >> j) & 1) == 1){ // j 在 s 中tmp.add(nums[j]);}}res.add(new ArrayList<>(tmp));}return res;}
}

77. 组合

中等

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

1 <= n <= 20
1 <= k <= n

枚举所有大小为k的子集

class Solution {public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res = new ArrayList<>();for(int s = 0; s < (1 << n); s++){if(Integer.bitCount(s) == k){List<Integer> tmp = new ArrayList<>();for(int j = 0; j < n; j++){if(((s >> j) & 1) == 1)tmp.add(j+1);}res.add(tmp);}}return res;}
}

1286. 字母组合迭代器

中等

请你设计一个迭代器类 CombinationIterator ，包括以下内容：

CombinationIterator(string characters, int combinationLength) 一个构造函数，输入参数包括：用一个 有序且字符唯一 的字符串 characters（该字符串只包含小写英文字母）和一个数字 combinationLength 。
函数 next() ，按 字典序 返回长度为 combinationLength 的下一个字母组合。
函数 hasNext() ，只有存在长度为 combinationLength 的下一个字母组合时，才返回 true

示例 1：

输入:
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
输出：
[null, "ab", true, "ac", true, "bc", false]
解释：
CombinationIterator iterator = new CombinationIterator("abc", 2); // 创建迭代器 iterator
iterator.next(); // 返回 "ab"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "ac"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "bc"
iterator.hasNext(); // 返回 false

提示：

1 <= combinationLength <= characters.length <= 15
characters 中每个字符都不同
每组测试数据最多对 next 和 hasNext 调用 104次
题目保证每次调用函数 next 时都存在下一个字母组合。

class CombinationIterator {List<String> list;int idx;public CombinationIterator(String characters, int combinationLength) {list = new ArrayList<>();// 转为组合问题，枚举所有长度为combiantionlength的组合int n = characters.length();for(int s = 0; s < (1 << n); s++){if(Integer.bitCount(s) == combinationLength){StringBuilder sb = new StringBuilder();for(int j = 0; j < n; j++){if(((s >> j) & 1) == 1)sb.append(characters.charAt(j));}list.add(sb.toString());}}Collections.sort(list, (a, b) -> a.compareTo(b));idx = 0;}public String next() {String s = list.get(idx);idx++;return s;}public boolean hasNext() {return idx < list.size();}
}

使用list的迭代器

class CombinationIterator {Iterator<String> iterator;public CombinationIterator(String characters, int combinationLength) {List<String> list = new ArrayList<>();// 转为组合问题，枚举所有长度为combiantionlength的组合int n = characters.length();for(int s = 0; s < (1 << n); s++){if(Integer.bitCount(s) == combinationLength){StringBuilder sb = new StringBuilder();for(int j = 0; j < n; j++){if(((s >> j) & 1) == 1)sb.append(characters.charAt(j));}list.add(sb.toString());}}Collections.sort(list);iterator = list.iterator();}public String next() {return iterator.next();}public boolean hasNext() {return iterator.hasNext();}
}

2397. 被列覆盖的最多行数

中等

给你一个下标从 0 开始、大小为 m x n 的二进制矩阵 matrix ；另给你一个整数 numSelect，表示你必须从 matrix 中选择的不同列的数量。

如果一行中所有的 1 都被你选中的列所覆盖，则认为这一行被覆盖了。

形式上，假设 s = {c1, c2, ...., cnumSelect} 是你选择的列的集合。对于矩阵中的某一行 row ，如果满足下述条件，则认为这一行被集合 s 覆盖：

对于满足 matrix[row][col] == 1 的每个单元格 matrix[row][col]（0 <= col <= n - 1），col 均存在于 s 中，或者
row 中 不存在 值为 1 的单元格。

你需要从矩阵中选出 numSelect 个列，使集合覆盖的行数最大化。

返回一个整数，表示可以由 numSelect 列构成的集合覆盖的 最大行数 。

示例 1：

输入：matrix = [[0,0,0],[1,0,1],[0,1,1],[0,0,1]], numSelect = 2
输出：3
解释：
图示中显示了一种覆盖 3 行的可行办法。
选择 s = {0, 2} 。
- 第 0 行被覆盖，因为其中没有出现 1 。
- 第 1 行被覆盖，因为值为 1 的两列（即 0 和 2）均存在于 s 中。
- 第 2 行未被覆盖，因为 matrix[2][1] == 1 但是 1 未存在于 s 中。
- 第 3 行被覆盖，因为 matrix[2][2] == 1 且 2 存在于 s 中。
因此，可以覆盖 3 行。
另外 s = {1, 2} 也可以覆盖 3 行，但可以证明无法覆盖更多行。

示例 2：

输入：matrix = [[1],[0]], numSelect = 1
输出：2
解释：
选择唯一的一列，两行都被覆盖了，因为整个矩阵都被覆盖了。
所以我们返回 2 。

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 12
matrix[i][j] 要么是 0 要么是 1
1 <= numSelect <= n

class Solution {/**1. 将二维矩阵压缩为一维矩阵，中间的元素用位(1<<j)标识2. 枚举所有选择numSelect的列， 	*/public int maximumRows(int[][] matrix, int numSelect) {int m = matrix.length, n = matrix[0].length;int[] rows = new int[m];for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(matrix[i][j] == 1)rows[i] |= (1 << j);}}int res = 0;for(int s = 1; s < (1 << n); s++){if(Integer.bitCount(s) == numSelect){int x = 0;for(int i = 0; i < n; i++){if(((s >> i) & 1) == 1)x |= (1 << i);}int cnt = 0;for(int i = 0; i < m; i++){if((rows[i] & x) == rows[i])cnt += 1;}res = Math.max(res, cnt);}}return res;}
}

2212. 射箭比赛中的最大得分

中等

Alice 和 Bob 是一场射箭比赛中的对手。比赛规则如下：

Alice 先射 numArrows 支箭，然后 Bob 也射 numArrows 支箭。
分数按下述规则计算：
1. 箭靶有若干整数计分区域，范围从 0 到 11 （含 0 和 11）。
2. 箭靶上每个区域都对应一个得分 k（范围是 0 到 11），Alice 和 Bob 分别在得分 k 区域射中 ak 和 bk 支箭。如果 ak >= bk ，那么 Alice 得 k 分。如果 ak < bk ，则 Bob 得 k 分
3. 如果 ak == bk == 0 ，那么无人得到 k 分。

例如，Alice 和 Bob 都向计分为 11 的区域射 2 支箭，那么 Alice 得 11 分。如果 Alice 向计分为 11 的区域射 0 支箭，但 Bob 向同一个区域射 2 支箭，那么 Bob 得 11 分。

给你整数 numArrows 和一个长度为 12 的整数数组 aliceArrows ，该数组表示 Alice 射中 0 到 11 每个计分区域的箭数量。现在，Bob 想要尽可能 最大化 他所能获得的总分。

返回数组 bobArrows ，该数组表示 Bob 射中 0 到 11 每个计分区域的箭数量。且 bobArrows 的总和应当等于 numArrows 。

如果存在多种方法都可以使 Bob 获得最大总分，返回其中 任意一种 即可。

示例 1：

输入：numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0]
输出：[0,0,0,0,1,1,0,0,1,2,3,1]
解释：上表显示了比赛得分情况。
Bob 获得总分 4 + 5 + 8 + 9 + 10 + 11 = 47 。
可以证明 Bob 无法获得比 47 更高的分数。

示例 2：

输入：numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2]
输出：[0,0,0,0,0,0,0,0,1,1,1,0]
解释：上表显示了比赛得分情况。
Bob 获得总分 8 + 9 + 10 = 27 。
可以证明 Bob 无法获得比 27 更高的分数。

提示：

1 <= numArrows <= 105
aliceArrows.length == bobArrows.length == 12
0 <= aliceArrows[i], bobArrows[i] <= numArrows
sum(aliceArrows[i]) == numArrows

class Solution {/**由于只有 12 个区域，可以枚举Bob在哪些区域获胜为了节省箭的数量，Bob在获胜区域只需要比Alice多射一支箭如果有多余的箭未射出，则累加到任意一个区域上*/public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {int n = aliceArrows.length;int[] res = new int[n];int maxScore = 0;for(int s = 0; s < (1 << n); s++){int score = 0;int usedArrows = 0;int[] bobArrows = new int[n];for(int j = 0; j < 12; j++){if((s >> j & 1) == 1){score += j;usedArrows += aliceArrows[j] + 1;bobArrows[j] = aliceArrows[j] + 1;}}if(usedArrows > numArrows){continue; // 需要的箭数超过最大个数}if(score > maxScore){maxScore = score;bobArrows[0] += (numArrows - usedArrows); // 没用完的箭随意放在第一个区域res = bobArrows;}}return res;}
}

1601. 最多可达成的换楼请求数目

困难

我们有 n 栋楼，编号从 0 到 n - 1 。每栋楼有若干员工。由于现在是换楼的季节，部分员工想要换一栋楼居住。

给你一个数组 requests ，其中 requests[i] = [fromi, toi] ，表示一个员工请求从编号为 fromi 的楼搬到编号为 toi 的楼。

一开始 所有楼都是满的，所以从请求列表中选出的若干个请求是可行的需要满足 每栋楼员工净变化为 0 。意思是每栋楼离开的员工数目等于该楼搬入的员工数数目。比方说 n = 3 且两个员工要离开楼 0 ，一个员工要离开楼 1 ，一个员工要离开楼 2 ，如果该请求列表可行，应该要有两个员工搬入楼 0 ，一个员工搬入楼 1 ，一个员工搬入楼 2 。

请你从原请求列表中选出若干个请求，使得它们是一个可行的请求列表，并返回所有可行列表中最大请求数目。

示例 1：

输入：n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
输出：5
解释：请求列表如下：
从楼 0 离开的员工为 x 和 y ，且他们都想要搬到楼 1 。
从楼 1 离开的员工为 a 和 b ，且他们分别想要搬到楼 2 和 0 。
从楼 2 离开的员工为 z ，且他想要搬到楼 0 。
从楼 3 离开的员工为 c ，且他想要搬到楼 4 。
没有员工从楼 4 离开。
我们可以让 x 和 b 交换他们的楼，以满足他们的请求。
我们可以让 y，a 和 z 三人在三栋楼间交换位置，满足他们的要求。
所以最多可以满足 5 个请求。

示例 2：

输入：n = 3, requests = [[0,0],[1,2],[2,1]]
输出：3
解释：请求列表如下：
从楼 0 离开的员工为 x ，且他想要回到原来的楼 0 。
从楼 1 离开的员工为 y ，且他想要搬到楼 2 。
从楼 2 离开的员工为 z ，且他想要搬到楼 1 。
我们可以满足所有的请求。

示例 3：

输入：n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
输出：4

提示：

1 <= n <= 20
1 <= requests.length <= 16
requests[i].length == 2
0 <= fromi, toi < n

class Solution {/**1 <= requests.length <= 161 <= n <= 20枚举可以满足的请求列表*/public int maximumRequests(int n, int[][] requests) {int m = requests.length;int maxRequest = 0;for(int s = 1; s < (1 << m); s++){int[] cnt = new int[n]; // 变化数组for(int j = 0; j < m; j++){if((s >> j & 1) == 1){int from = requests[j][0], to = requests[j][1];cnt[from] -= 1;cnt[to] += 1;}}boolean available = true;for(int i = 0; i < n; i++){if(cnt[i] != 0){available = false;break;}}if(available){maxRequest = Math.max(maxRequest, Integer.bitCount(s));}}return maxRequest;}
}

2959. 关闭分部的可行集合数目

困难

一个公司在全国有 n 个分部，它们之间有的有道路连接。一开始，所有分部通过这些道路两两之间互相可以到达。

公司意识到在分部之间旅行花费了太多时间，所以它们决定关闭一些分部（也可能不关闭任何分部），同时保证剩下的分部之间两两互相可以到达且最远距离不超过 maxDistance 。

两个分部之间的距离是通过道路长度之和的 最小值 。

给你整数 n ，maxDistance 和下标从 0 开始的二维整数数组 roads ，其中 roads[i] = [ui, vi, wi] 表示一条从 ui 到 vi 长度为 wi的无向道路。

请你返回关闭分部的可行方案数目，满足每个方案里剩余分部之间的最远距离不超过 maxDistance。

注意，关闭一个分部后，与之相连的所有道路不可通行。

注意，两个分部之间可能会有多条道路。

示例 1：

输入：n = 3, maxDistance = 5, roads = [[0,1,2],[1,2,10],[0,2,10]]
输出：5
解释：可行的关闭分部方案有：
- 关闭分部集合 [2] ，剩余分部为 [0,1] ，它们之间的距离为 2 。
- 关闭分部集合 [0,1] ，剩余分部为 [2] 。
- 关闭分部集合 [1,2] ，剩余分部为 [0] 。
- 关闭分部集合 [0,2] ，剩余分部为 [1] 。
- 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。
总共有 5 种可行的关闭方案。

示例 2：

输入：n = 3, maxDistance = 5, roads = [[0,1,20],[0,1,10],[1,2,2],[0,2,2]]
输出：7
解释：可行的关闭分部方案有：
- 关闭分部集合 [] ，剩余分部为 [0,1,2] ，它们之间的最远距离为 4 。
- 关闭分部集合 [0] ，剩余分部为 [1,2] ，它们之间的距离为 2 。
- 关闭分部集合 [1] ，剩余分部为 [0,2] ，它们之间的距离为 2 。
- 关闭分部集合 [0,1] ，剩余分部为 [2] 。
- 关闭分部集合 [1,2] ，剩余分部为 [0] 。
- 关闭分部集合 [0,2] ，剩余分部为 [1] 。
- 关闭分部集合 [0,1,2] ，关闭后没有剩余分部。
总共有 7 种可行的关闭方案。

示例 3：

输入：n = 1, maxDistance = 10, roads = []
输出：2
解释：可行的关闭分部方案有：
- 关闭分部集合 [] ，剩余分部为 [0] 。
- 关闭分部集合 [0] ，关闭后没有剩余分部。
总共有 2 种可行的关闭方案。

提示：

1 <= n <= 10
1 <= maxDistance <= 105
0 <= roads.length <= 1000
roads[i].length == 3
0 <= ui, vi <= n - 1
ui != vi
1 <= wi <= 1000
一开始所有分部之间通过道路互相可以到达。

class Solution {/**0 <= roads.length <= 1000枚举保留哪些节点,在这些节点之间连边然后用Floyd算法求出任意两点之间的最短路,若保留节点之间的最短路均不超过maxDistance,记录答案*/public int numberOfSets(int n, int maxDistance, int[][] roads) {// 预处理原图的邻接矩阵gint[][] g = new int[n][n];for(int i = 0; i < n; i++){Arrays.fill(g[i], Integer.MAX_VALUE / 2); // 加法防溢出g[i][i] = 0;}for(int[] e : roads){int x = e[0], y = e[1], wt = e[2];g[x][y] = Math.min(g[x][y], wt);g[y][x] = Math.min(g[y][x], wt);}int res = 0;int[][] f = new int[n][n];next://遍历所有方案数，当前方案i的二进制中为1的位置则表示该节点没有被删除，为0则表示被删除for(int s = 0; s < (1 << n); s++){for(int i = 0; i < n; i++){if(((s >> i) & 1) == 1){System.arraycopy(g[i], 0, f[i], 0, n);}}// Floydfor (int k = 0; k < n; k++) {if ((s >> k & 1) == 0) continue;for (int i = 0; i < n; i++) {if ((s >> i & 1) == 0) continue;for (int j = 0; j < n; j++) {f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j]);}}}for (int i = 0; i < n; i++) {if ((s >> i & 1) == 0) continue;for (int j = 0; j < n; j++) {if ((s >> j & 1) == 1 && f[i][j] > maxDistance) {continue next;}}}res++;}return res;}
}