学习记录
2025.3.28
题目:
思路:
哈希表。
解题步骤:
1.初始化位掩码 mask:
mask 是一个整数,用于记录字符串中出现过的字符。初始时,所有二进制位都是 0。
2.遍历字符串:
对于字符串 s 中的每一个字符 s[i],计算其对应的位位置:
s[i] - ‘a’:将字符映射到 0(‘a’)到 25(‘z’)的索引。
1 << (s[i] - ‘a’):生成一个只有该字符对应位为 1 的二进制数。
mask |= …:用按位或操作将该位标记到 mask 中,表示这个字符已经出现过。
3.统计不同字符的个数:
__builtin_popcount(mask):计算 mask 中 1 的个数,即不同字符的数量。
代码:
int minimizedStringLength(char* s) {int mask = 0;int n = strlen(s);for (int i = 0; i < n; i++) {mask |= 1 << (s[i] - 'a');}return __builtin_popcount(mask);
}
class Solution {public int minimizedStringLength(String s) {return (int) s.chars().distinct().count();}
}
复杂度:
N(N)
N(N)