【LeetCode】第一个只出现一次的字符 Java 题解

关注

发布于: 3 小时前

题目描述

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

示例:
s = "abaccdeff"返回 "b"
s = "" 返回 " "
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

这个题目题意简单，难点是返回第一个只出现一次的字符。
首先，我们可以使用 hashMap 来存储每个字符出现的次数。然后在重新遍历字符串就可以得出答案。代码如下：

代码

    public char firstUniqChar(String s) {        Map<Character, Integer> map = new HashMap<>();        for (char ch : s.toCharArray()) {            map.put(ch, map.getOrDefault(ch, 0) + 1);        }        Set<Character> set = new HashSet<>();        for (Map.Entry<Character, Integer> entry : map.entrySet()) {            if (entry.getValue() == 1) {                set.add(entry.getKey());            }        }        char ans = ' ';        if (set.size() > 0) {            for (char ch : s.toCharArray()) {                if (set.contains(ch)) {                    ans = ch;                    break;                }            }        }        return ans;    }

复制代码

这个题目虽然不难，但是一不小心就容易写出冗余低效的代码。写出精简,高效的代码还是需要多练习。优化后的代码如下：

    public char firstUniqChar(String s) {        int[] cnt = new int[256];        char[] chars = s.toCharArray();        for (char ch : chars) {            cnt[ch]++;        }        char ans = ' ';        for (char ch : chars) {            if (cnt[ch] == 1) {                ans = ch;                break;            }        }
        return ans;    }

复制代码

总结

上述代码的时间复杂度是 O(n), 空间复杂度是 O(n)
上述优化的代码，主要使用 ASCII 码思想优化。
简单介绍一下 ASCII 码相关知识。在计算机中，所有的数据在存储和运算时都要使用二进制数表示（因为计算机用高电平和低电平分别表示 1 和 0）。而 ASCII 码就是存储的通用规范。ASCII 码使用指定的 7 位或 8 位二进制数组合来表示 128 或 256 种可能的字符。标准 ASCII 码也叫基础 ASCII 码，使用 7 位二进制数来表示所有的大写和小写字母，数字 0 到 9、标点符号，其中 32～126(共 95 个)是字符(32sp 是空格），其中 48～57 为 0 到 9 十个阿拉伯数字；65～90 为 26 个大写英文字母，97～122 号为 26 个小写英文字母，其余为一些标点符号、运算符号等。
坚持每日一题，加油！

发布于: 3 小时前阅读数: 3

原文链接:【http://xie.infoq.cn/article/ed35566691e71ebe7521e1df3】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】第一个只出现一次的字符 Java 题解

题目描述

思路分析

代码

总结

HQ数字卡

评论