关于leetcode:每日一练23第一个只出现一次的字符

title: 每日一练（23）：第一个只呈现一次的字符

categories:[剑指 offer]

tags:[每日一练]

date: 2022/02/22

每日一练（23）：第一个只呈现一次的字符

在字符串 s 中找出第一个只呈现一次的字符。如果没有，返回一个单空格。s 只蕴含小写字母。

示例 1:

输出：s = “abaccdeff”

输入：’b’

示例 2:

输出：s = “”

输入：’ ‘

限度：

0 <= s 的长度 <= 50000

起源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl…

办法一：哈希表

思路

1. 对字符串进行两次遍历。

• 遍历字符串 s，应用哈希表统计“各字符数量是否 >1”。
• 再遍历字符串 s，在哈希表中找到首个“数量为 1 的字符”，并返回。

算法

1. 字符统计：遍历字符串 s 中的每个字符 c；

• 若 dic 中 不蕴含 键(key) c：则向 dic 中增加键值对 (c, True)，代表字符 c 的数量为 1；
• 若 dic 中 蕴含 键(key) c：则批改键 c 的键值对为 (c, False)，代表字符 c 的数量 >1。

2. 查找数量为 1 的字符：遍历字符串 s 中的每个字符 c；

• 若 dic 中键 c 对应的值为 True：，则返回 c。

3. 返回 ‘ ‘，代表字符串无数量为 1 的字符。

char firstUniqChar(string s) {if (s.empty()) {     // 留神边界状况的解决！特地是 s 为空字符串的状况
        return ' ';
    }
    unordered_map<int, bool> dic;
    for (char c : s) {dic = dic.find(c) == dic.end();}
    for (char c : s) {if (dic) {return c;}
    }
    return ' ';
}

办法二：巧用 string 容器的查找函数

思路和算法

• s.find(s[i]) : 返回字符串 s 中从左向右查找 s[i]第一次呈现的地位；
• s.rfind(s[i]) : 返回字符串 s 中从右向左查找 s[i]第一次呈现的地位；

此办法尽管看起来代码简洁，然而 工夫复杂度较高!

char firstUniqChar(string s) {if (s.empty()) {    // 留神边界状况的解决！特地是 s 为空字符串的状况
        return ' ';
    }
    int n = s.size();
    for(int i = 0; i < n; i++){if(s.find(s[i]) == s.rfind(s[i])){return s[i];
        }
    }
    return ' ';
}