class Solution {
public:
int numberOfSpecialChars(string word) {
}
};
100291. 统计特殊字母的数量 II
给你一个字符串 word。如果 word 中同时出现某个字母 c 的小写形式和大写形式，并且 每个 小写形式的 c 都出现在第一个大写形式的 c 之前，则称字母 c 是一个 特殊字母 。
返回 word 中 特殊字母 的数量。
示例 1:
输入：word = "aaAbcBC"
输出：3
解释：
特殊字母是 'a'、'b' 和 'c'。
示例 2:
输入：word = "abc"
输出：0
解释：
word 中不存在特殊字母。
示例 3:
输入：word = "AbBCab"
输出：0
解释：
word 中不存在特殊字母。
提示：
1 <= word.length <= 2 * 105word 仅由小写和大写英文字母组成。原站题解
golang 解法, 执行用时: 15 ms, 内存消耗: 6.8 MB, 提交时间: 2024-04-21 23:53:20
func numberOfSpecialChars(word string) int {
var lower, upper, invalid uint
for _, c := range word {
bit := uint(1) << (c & 31)
if c&32 > 0 { // 小写字母
lower |= bit
if upper&bit > 0 { // c 也在 upper 中
invalid |= bit // 不合法
}
} else { // 大写字母
upper |= bit
}
}
// 从交集 lower & upper 中去掉不合法的字母 invalid
return bits.OnesCount(lower & upper &^ invalid)
}
func numberOfSpecialChars2(word string) (ans int) {
state := [27]int{}
for _, c := range word {
x := c & 31
if c&32 > 0 {
if state[x] == 0 {
state[x] = 1
} else if state[x] == 2 {
state[x] = -1
ans--
}
} else {
if state[x] == 0 {
state[x] = -1
} else if state[x] == 1 {
state[x] = 2
ans++
}
}
}
return
}
java 解法, 执行用时: 9 ms, 内存消耗: 44.6 MB, 提交时间: 2024-04-21 23:52:55
class Solution {
public int numberOfSpecialChars(String word) {
int ans = 0;
int[] state = new int[27];
for (char c : word.toCharArray()) {
int x = c & 31; // 转成数字 1~26
if ((c & 32) > 0) { // 小写字母
if (state[x] == 0) {
state[x] = 1;
} else if (state[x] == 2) {
state[x] = -1;
ans--;
}
} else { // 大写字母
if (state[x] == 0) {
state[x] = -1;
} else if (state[x] == 1) {
state[x] = 2;
ans++;
}
}
}
return ans;
}
public int numberOfSpecialChars2(String word) {
int lower = 0, upper = 0, invalid = 0;
for (char c : word.toCharArray()) {
int bit = 1 << (c & 31);
if ((c & 32) > 0) { // 小写字母
lower |= bit;
if ((upper & bit) > 0) { // c 也在 upper 中
invalid |= bit; // 不合法
}
} else { // 大写字母
upper |= bit;
}
}
// 从交集 lower & upper 中去掉不合法的字母 invalid
return Integer.bitCount(lower & upper & ~invalid);
}
}
cpp 解法, 执行用时: 59 ms, 内存消耗: 22 MB, 提交时间: 2024-04-21 23:52:26
class Solution {
public:
int numberOfSpecialChars(string word) {
int lower = 0, upper = 0, invalid = 0;
for (char c : word) {
int bit = 1 << (c & 31);
if (c & 32) { // 小写字母
lower |= bit;
if (upper & bit) { // c 也在 upper 中
invalid |= bit; // 不合法
}
} else { // 大写字母
upper |= bit;
}
}
// 从交集 lower & upper 中去掉不合法的字母 invalid
return __builtin_popcount(lower & upper & ~invalid);
}
int numberOfSpecialChars2(string word) {
int ans = 0;
int state[27]{};
for (char c : word) {
int x = c & 31; // 转成数字 1~26
if (c & 32) { // 小写字母
if (state[x] == 0) {
state[x] = 1;
} else if (state[x] == 2) {
state[x] = -1;
ans--;
}
} else { // 大写字母
if (state[x] == 0) {
state[x] = -1;
} else if (state[x] == 1) {
state[x] = 2;
ans++;
}
}
}
return ans;
}
};
python3 解法, 执行用时: 199 ms, 内存消耗: 17.5 MB, 提交时间: 2024-04-21 23:52:00
class Solution:
# 状态机
def numberOfSpecialChars(self, word: str) -> int:
ans = 0
state = [0] * 27
for c in map(ord, word):
x = c & 31 # 转成数字 1~26
if c & 32: # 小写字母
if state[x] == 0:
state[x] = 1
elif state[x] == 2:
state[x] = -1
ans -= 1
else: # 大写字母
if state[x] == 0:
state[x] = -1
elif state[x] == 1:
state[x] = 2
ans += 1
return ans
# 位运算
def numberOfSpecialChars2(self, word: str) -> int:
lower = upper = invalid = 0
for c in map(ord, word):
bit = 1 << (c & 31)
if c & 32: # 小写字母
lower |= bit
if upper & bit: # c 也在 upper 中
invalid |= bit # 不合法
else: # 大写字母
upper |= bit
# 从交集 lower & upper 中去掉不合法的字母 invalid
return (lower & upper & ~invalid).bit_count()