每日一练(23):第一个只出现一次的字符

简介: 在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。

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


示例 1:


输入:s = "abaccdeff"

输出:'b'


示例 2:


输入:s = ""

输出:' '


限制:

0 <= s 的长度 <= 50000


来源:力扣(LeetCode)


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


方法一:哈希表


思路


对字符串进行两次遍历。


  • 遍历字符串 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 ' ';
}
目录
相关文章
|
算法 程序员
【Leetcode】NC31 第一个只出现一次的字符(牛客网)、面试题 01.01. 判定字符是否唯一
题目描述: 描述 在一个长为n字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).(从0开始计数)
66 0
|
6月前
|
存储 算法 索引
刷题专栏(二十六):字符串中的第一个唯一字符
刷题专栏(二十六):字符串中的第一个唯一字符
98 1
刷题专栏(二十六):字符串中的第一个唯一字符
|
6月前
|
机器人 Java
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
70 0
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
|
6月前
|
Java Go
每日一题《剑指offer》字符串篇之字符流中第一个不重复的字符
每日一题《剑指offer》字符串篇之字符流中第一个不重复的字符
61 0
每日一题《剑指offer》字符串篇之字符流中第一个不重复的字符
|
6月前
|
算法
六六力扣刷题字符串之找出字符串中第一个匹配项的下标
六六力扣刷题字符串之找出字符串中第一个匹配项的下标
59 0
剑指offer 51. 字符串中第一个只出现一次的字符
剑指offer 51. 字符串中第一个只出现一次的字符
66 0
华为机试每日一练--第四题:字符串最后一个单词的长度
计算字符串最后一个单词的长度,单词以空格隔开,字符串长度小于5000。(注:字符串末尾不以空格为结尾)
华为机试每日一练--第四题:字符串最后一个单词的长度
|
Java
java学习第十一天笔记-字符串205-生成字符串四位字母 数字位置随机
java学习第十一天笔记-字符串205-生成字符串四位字母 数字位置随机
85 0
java学习第十一天笔记-字符串205-生成字符串四位字母 数字位置随机
|
算法
算法题每日一练---第50天:判断字符是否唯一
实现一个算法,确定一个字符串 s 的所有字符是否全都不同。
128 2
算法题每日一练---第50天:判断字符是否唯一
|
算法 C++
算法题每日一练---第67天:无重复字符的最长子串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
127 0
算法题每日一练---第67天:无重复字符的最长子串