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 ' ';
}