leetcode 3035
题目
例子
思路
统计字符出现的频次，5个a(字符可以成为回文)。
将所有字符放在一起考虑，因为字符是可以任意移动。[“aabb”,“a”] => [“abba”, “a”]
只要奇数个字符的种类，不要超过字符数组的size就可以。
代码实现
class Solution {
public:
int maxPalindromesAfterOperations(vector<string>& words) {
int ans =0;
int total =0;
int mask =0;
for(auto & w:words){
total += w.length();
for(auto & ss: w){
//确认字符是否是奇数，通过异或运算
mask^=1<<(ss-'a');
}
}
// __builtin_popcount函数统计二进制(mask)有多少个bit是1
total -= __builtin_popcount(mask);
sort(words.begin(), words.end(), [](string &a, string& b){ return a.length() < b.length();});
for(auto & w:words){
//已经减去奇数的部分了, 1/2 =0， 考虑到存在"a" 也是回文，需要对words进行排序
total -= w.length()/2 *2;
if(total < 0){
break;
}
ans++;
}
return ans;
}
};
分析
排序时间复杂度平均是0(nlogn)
__builtin_popcount
__builtin_popcount是GCC编译器提供的内建函数，用于计算一个整数中二进制表示中1的个数（即统计整数中1的个数）。
语法：
int __builtin_popcount(unsigned int x);
参数：
x：要计算的整数值。
返回值：
- 返回整数
x中二进制表示中1的个数。
示例：
#include <iostream>
int main() {
unsigned int x = 15; // 二进制表示为 1111
int count = __builtin_popcount(x); // 计算x中1的个数
std::cout << "Number of set bits in " << x << ": " << count << std::endl;
return 0;
}
注意：
__builtin_popcount函数只能接受unsigned int类型的参数，如果传入其他类型的参数，可能会导致编译错误。- 该函数在GCC编译器中可用，可能不适用于其他编译器。
使用__builtin_popcount函数可以高效地计算一个整数中1的个数，特别适用于位操作相关的算法和问题。
遍历
在这两种循环语句中，for(string s : words)和for(auto &s : words)的区别在于变量s的类型和是否是引用类型。
-
for(string s : words)：- 这种写法会创建
words中每个元素的副本，并将副本赋值给变量s。这意味着在循环体内对s的修改不会影响到words中的元素。 - 这种写法适用于遍历容器中的元素，如果只需要访问元素而不修改它们，这种写法是合适的。
- 这种写法会创建
-
for(auto &s : words)：- 这种写法使用
auto关键字推导出words中元素的类型，并将s声明为对应类型的引用。这样s将直接引用words中的元素，而不是创建副本。 - 使用引用类型可以提高效率，避免不必要的内存拷贝操作。
- 如果需要在循环中修改
words中的元素，或者希望在循环外部访问修改后的元素，使用引用类型是更好的选择。
- 这种写法使用
综上所述，for(string s : words)会创建元素的副本，而for(auto &s : words)会直接引用。
统计整数x中二进制表示中1的个数
要统计一个整数 x 中二进制表示中 1 的个数，可以使用以下方法：
#include <iostream>
int countSetBits(int x) {
int count = 0;
while (x) {
count += x & 1;
x >>= 1;
}
return count;
}
int main() {
int x = 25; // 二进制表示为 11001
int numberOfOnes = countSetBits(x);
std::cout << "Number of ones in binary representation of " << x << ": " << numberOfOnes << std::endl;
return 0;
}
在上面的示例中，countSetBits 函数用于统计整数 x 中二进制表示中 1 的个数。该函数通过将 x 与 1 进行按位与操作，判断 x 的最低位是否为 1，然后将 x 右移一位，直到 x 变为 0。在每次循环中，如果 x 的最低位为 1，则 count 加一。最终返回 count 即为 x 二进制表示中 1 的个数。
在 main 函数中，我们给定一个整数 x 的值为 25（二进制表示为 11001），然后调用 countSetBits 函数统计其二进制表示中 1 的个数，并输出结果。
