剑指 Offer 50. 第一个只出现一次的字符
2024-09-01 20:02:27
题目描述
我的题解
（方法三应用更广泛；方法一虽有限制，但很好用，此题中该方法效率也最高）
方法一：（适用于范围确定的）
思路分析
- 该字符串只包含小写字母，即字符种类最多26个
- 开一个数组yes[26]，分别存放字母a-z所出现的次数。
- 字符c对应的数组下标索引为为：c-97.
- 我的代码中，为了节约空间，取的是byte类型数组：
- 当某个字符出现次数<2，该字符对应的数组值+1；
- 否则（即出现次数>=2，不符合题目要找的），不处理该字符对应的数组值（即不再+1，因为byte类型最大值为127，而题目数据可能出现某个字符出现次数多达50000的情况）。
代码如下
public char firstUniqChar(String s) {
char[] chars = s.toCharArray();
byte[] yes = new byte[26];
for (char c : chars) {
if (yes[c-97]<2)yes[c-97]++;
}
char res = ' ';
for (char c : chars) {
if (yes[c-97]==1) {
res = c;
break;
}
}
return res;
}
方法二：哈希表
方法二的优化 是参考leetcode大佬的题解。大佬leetcode主页
思路分析
- 创建一个哈希表：HashMap<Character, Boolean> dic。
- 遍历字符串s 中的每个字符 c：
- 若字符c第一次出现，则向dic中添加键值对：dic.put(c, true)；
- 若前面已经出现过，则修改键c的键值对：dic.put(c, false) 【字符c数量大于1，不符合题目要找的】；
代码如下：
public char firstUniqChar(String s) {
Map<Character, Boolean> dic = new HashMap<>();
char[] chars = s.toCharArray();
for (char c : chars) { // 遍历字符串
dic.put(c, !dic.containsKey(c)); // 若dic中不包含键 c ：则向dic中添加键值对 (c, True) ；
// 若包含键 c ：则修改键c的键值对为 (c, False)。
}
char res = ' ';
// 再次遍历字符串s，查看哈希表中键 c对应的value值，找出第一个true
for (char c : chars) {
if (dic.get(c)) {
res = c;
break;
}
}
return res;
}
方法三：有序哈希表
方法三 是参考leetcode大佬的题解。大佬leetcode主页
思路分析
- 在哈希表的基础上，有序哈希表中的键值对是 按照插入顺序排序 的。
- 故在方法二的基础上， 对于数据量大的题目，方法三效率更高。
- 方法二中，第二个for循环，遍历的是字符串s；而方法三中第二个for循环只需遍历有序哈希表即可（因哈希表是去重的，故减少了循环的次数，增加了效率）
代码如下
public char firstUniqChar(String s) {
Map<Character, Boolean> dic = new LinkedHashMap<>();
char[] chars = s.toCharArray();
for (char c : chars) {
dic.put(c, !dic.containsKey(c)); // 若dic中不包含键 c ：则向dic中添加键值对 (c, True) ；
// 若包含键 c ：则修改键c的键值对为 (c, False)。
}
for (Map.Entry<Character, Boolean> entry : dic.entrySet()) {
if (entry.getValue()) return entry.getKey();
}
return ' ';
}
最新文章
- [Linux 维护]收集centos系统性能指标
- 按列 sort 排序 Linux 如何查看当前占用CPU或内存最多的K个进程
- python 核心编程第二版 课后习题 第11章
- Pacman主题下给Hexo增加简历类型
- poj 3126 Prime Path( bfs + 素数)
- php入门实现留言板
- 使用Struts1完成用户登录功能
- display:inline,display:inline-block,display:block 区别
- css3之3D翻牌效果
- dialog获取焦点
- golang json反序列化
- django-celery的配置及使用
- Zuul过滤器
- Django之Form进阶
- Docker(十四)-Docker四种网络模式
- java transient关键字作用，使用场景。
- PHP函数注释规范
- 安装与配置ironic
- MVC切片编程
- SUI使用经验