2024-12-04：统计特殊字母的数量Ⅱ。用go语言，给定一个字符串 word，统计其中存在特殊字母的数量。特殊字母指的是同时

福大大架构师每日一题

发布于 2024-12-05 16:08:06

6500

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2024-12-04：统计特殊字母的数量Ⅱ。用go语言，给定一个字符串 word，统计其中存在特殊字母的数量。特殊字母指的是同时出现某个字母 c 的小写形式和大写形式，且每个小写形式的 c 都出现在第一个大写形式的 c 之前的字母 c。

输入：word = "aaAbcBC"。

输出：3。

解释：

特殊字母是 'a'、'b' 和 'c'。

答案2024-12-04：

chatgpt[1]

题目来自leetcode3121。

大体步骤如下：

1.创建用于存储小写字母、大写字母和无效字母的三个变量：lower、upper 和 invalid。

2.对于给定的字符串 word，遍历每个字符 c。

3.对字符 c 进行位运算操作，计算该字符在字母表中的位置，以确定对应位的值。

4.根据字符 c 是小写字母还是大写字母来更新对应的位：

• 若为小写字母：将对应位置的位设置为 1，并检查是否在大写字母中已存在，若存在则标记为不合法字母。
• 若为大写字母：将对应位置的位设置为 1。

5.计算交集 lower & upper，并从中排除不合法字母，以获得包含特殊字母的位。

6.使用 bits.OnesCount() 函数计算特殊字母的数量。

7.在主函数中调用 numberOfSpecialChars 函数，并输出结果。

总的时间复杂度为 O(n)，其中 n 是输入字符串的长度，因为需要遍历整个字符串进行字符处理。

总的额外空间复杂度为 O(1)，因为只使用了常量级的额外存储空间来存储位图信息和临时变量。

Go完整代码如下：

package main

import(
"fmt"
"math/bits"
)

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 main(){
    word :="aaAbcBC"
    fmt.Println(numberOfSpecialChars(word))
}

Rust完整代码如下：

use std::collections::HashSet;

fnnumber_of_special_chars(word:&str)->usize{
letmut lower:HashSet<char>=HashSet::new();
letmut upper:HashSet<char>=HashSet::new();
letmut invalid:HashSet<char>=HashSet::new();

forcin word.chars(){
if c.is_ascii_lowercase(){
// 小写字母
if upper.contains(&c.to_ascii_uppercase()){
                invalid.insert(c);// 不合法的字符
}
            lower.insert(c);
}elseif c.is_ascii_uppercase(){
// 大写字母
            upper.insert(c);
}
}

// 从交集 lower & upper 中去掉不合法的字符 invalid
    lower.intersection(&upper.iter().map(|&c| c.to_ascii_lowercase()).collect()).filter(|&&c|!invalid.contains(&c)).count()
}

fnmain(){
letword="aaAbcBC";
println!("{}",number_of_special_chars(word));
}