第一个只出现一次的字符(剑指offer 50)Java 思路由浅入深
2022/2/22 14:54:55
本文主要是介绍第一个只出现一次的字符(剑指offer 50)Java 思路由浅入深,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、题目描述
在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。
示例 1:
输入:s = "abaccdeff"
输出:'b'
示例 2:
输入:s = ""
输出:' '
限制:
0 <= s 的长度 <= 50000
二、思路及Java代码
首先想到的是利用set集合,将字符串中所有字符插入set中,如果一个字符插入set集合失败,则说明他是重复字符,将它记录到list中,然后再遍历字符串,第一个不在list中的字符就是所求。
class Solution { public char firstUniqChar(String s) { Set<Character> set = new HashSet<>(); List<Character> list = new ArrayList<>(); for(Character c : s.toCharArray()){ boolean flag = set.add(c); if(!flag){ list.add(c); } } for(Character c : s.toCharArray()){ if(!list.contains(c)){ return c; } } return ' '; } }
上述思想可以直接用map实现,用hashmap记录下每个字符出现的次数,然后遍历字符串的每一个字符,在hash表中值为1的字符即为所求。
class Solution { public char firstUniqChar(String s) { Map<Character, Integer> map = new HashMap<>(); for(Character c : s.toCharArray()){ map.put(c, map.getOrDefault(c, 0)+1); } for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); if(map.get(ch) == 1){ return ch; } } return ' '; } }
由于题目要找的是出现一次的字符,那么我们可以理解为在字符串中是否重复的字符,即可以把哈希表中的键改为布尔类型,提高效率的同时,布尔值可以直接判断,简化了逻辑。
class Solution { public char firstUniqChar(String s) { Map<Character, Boolean> map = new HashMap<>(); for(Character c : s.toCharArray()){ map.put(c, map.containsKey(c)); } for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); if(!map.get(ch)){ return ch; } } return ' '; } }
时间复杂度: O(N)
空间复杂度: O(1)
此外,由于题目找的是第一个字符,可以用有序哈希表来实现。因为有序hash表的存储顺序是插入顺序,这样直接返回有序哈希表中的第一个值为false的键即可,更加简便。
这篇关于第一个只出现一次的字符(剑指offer 50)Java 思路由浅入深的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?