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[c] = dic.find(c) == dic.end();    }    for (char c : s) {        if (dic[c]) {            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 ' ';}