2275. 按位与结果大于零的最长组合
对数组 nums 执行 按位与 相当于对数组 nums 中的所有整数执行 按位与 。
- 例如，对
nums = [1, 5, 3]来说，按位与等于1 & 5 & 3 = 1。 - 同样，对
nums = [7]而言，按位与等于7。
给你一个正整数数组 candidates 。计算 candidates 中的数字每种组合下 按位与 的结果。
返回按位与结果大于 0 的 最长 组合的长度。
示例 1：
输入：candidates = [16,17,71,62,12,24,14]
输出：4
解释：组合 [16,17,62,24] 的按位与结果是 16 & 17 & 62 & 24 = 16 > 0 。
组合长度是 4 。
可以证明不存在按位与结果大于 0 且长度大于 4 的组合。
注意，符合长度最大的组合可能不止一种。
例如，组合 [62,12,24,14] 的按位与结果是 62 & 12 & 24 & 14 = 8 > 0 。
示例 2：
输入：candidates = [8,8]
输出：2
解释：最长组合是 [8,8] ，按位与结果 8 & 8 = 8 > 0 。
组合长度是 2 ，所以返回 2 。
提示：
1 <= candidates.length <= 1051 <= candidates[i] <= 107
我的解法
class Solution {
public:
int largestCombination(vector<int>& candidates) {
int ans = 0;
for(int i = 0; i < 24; i++){
int cnt = 0;
for(auto& a : candidates){
cnt += (a >> i) & 1;
}
ans = max(cnt, ans);
}
return ans;
}
};
官方解法
class Solution {
public:
int largestCombination(vector<int>& candidates) {
// 计算从低到高第 k 个二进制位数值为 1 的元素个数
auto maxlen = [&](int k) -> int {
int res = 0;
for (int num: candidates) {
if (num & (1 << k)) {
++res;
}
}
return res;
};
int res = 0;
for (int i = 0; i < 24; ++i) {
// 遍历二进制位
res = max(res, maxlen(i));
}
return res;
}
};
大佬解法
#include <ranges>
// 一行法
class Solution {
public:
int largestCombination(vector<int>& candidates) {
return ranges::max(views::iota(0, 24) | views::transform([&](int i) {
return ranges::count_if(candidates, [&](int x) {
return x & (1 << i);
});
}));
}
};
1. <ranges> 库
<ranges> 是C++20引入的一个新库，提供了对范围（ranges）的操作支持。它允许你以更简洁和声明式的方式处理容器和序列。
示例：
#include <iostream>
#include <vector>
#include <ranges>
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
// 使用 ranges 过滤偶数
auto even_numbers = numbers | std::views::filter([](int x) { return x % 2 == 0; });
for (int x : even_numbers) {
std::cout << x << " "; // 输出: 2 4
}
}
说明：
std::views::filter是一个视图适配器，用于过滤满足条件的元素。numbers | std::views::filter(...)表示对numbers进行过滤操作。
2. ranges::max
ranges::max 是 <ranges> 库中的一个算法，用于查找给定范围内的最大值。它类似于传统的 std::max，但可以直接作用于范围（range）而不需要显式的迭代器。
示例：
#include <iostream>
#include <vector>
#include <ranges>
int main() {
std::vector<int> numbers = {3, 1, 4, 1, 5, 9};
// 使用 ranges::max 查找最大值
int max_value = std::ranges::max(numbers);
std::cout << "Max value: " << max_value << std::endl; // 输出: Max value: 9
}
说明：
std::ranges::max直接作用于容器，返回容器中的最大值。
3. views::iota
views::iota 是一个视图生成器，用于生成一个连续的整数序列。它的用法类似于Python中的 range 函数。在这个代码中，views::iota(0, 24) 生成了一个从0到23的整数序列（包含0，不包含24）。
示例：
#include <iostream>
#include <ranges>
int main() {
// 生成从 0 到 4 的整数序列
auto numbers = std::views::iota(0, 5);
for (int x : numbers) {
std::cout << x << " "; // 输出: 0 1 2 3 4
}
}
说明：
std::views::iota(0, 5)生成一个从 0 开始到 4 结束的序列（包含起始值，不包含结束值）。
4. views::transform
views::transform 是一个视图适配器，用于对范围内的每个元素应用一个转换函数。它类似于 std::transform，但以惰性求值的方式工作，只有在需要时才会进行计算。
在这个代码中，views::transform 对 views::iota(0, 24) 生成的每个整数 i 应用了一个 lambda 函数。这个 lambda 函数的作用是统计 candidates 中有多少个元素的第 i 位是1。
示例：
#include <iostream>
#include <vector>
#include <ranges>
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
// 对每个元素乘以 2
auto doubled = numbers | std::views::transform([](int x) { return x * 2; });
for (int x : doubled) {
std::cout << x << " "; // 输出: 2 4 6 8 10
}
}
说明：
std::views::transform对每个元素应用 lambda 函数[](int x) { return x * 2; }，将其乘以 2。
5. ranges::count_if
ranges::count_if 是 <ranges> 库中的一个算法，用于统计范围内满足特定条件的元素个数。它类似于 std::count_if，但可以直接作用于范围。
在这个代码中，ranges::count_if 统计 candidates 中满足 x & (1 << i) 条件的元素个数，即统计有多少个元素的第 i 位是1。
示例：
#include <iostream>
#include <vector>
#include <ranges>
int main() {
std::vector<int> numbers = {1, 2, 3, 4, 5};
// 统计偶数个数
int even_count = std::ranges::count_if(numbers, [](int x) { return x % 2 == 0; });
std::cout << "Even count: " << even_count << std::endl; // 输出: Even count: 2
}
说明：
std::ranges::count_if统计numbers中满足x % 2 == 0的元素个数。
6. 整体逻辑
代码的整体逻辑是：
- 生成一个从0到23的整数序列（因为整数的二进制表示最多有24位）。
- 对每个整数
i，统计candidates中有多少个元素的第i位是1。 - 最后，找出这些统计结果中的最大值，即
candidates中所有元素的二进制表示中，某一位上1的最大出现次数。