死磕算法系列文章
- 干货 | 手撕十大经典排序算法
- 剑指offer | 认识面试
- 剑指offer | 面试题2：实现Singleton模式
- 剑指offer | 面试题3：二维数组的查找
- 剑指offer | 面试题4：替换空格
- 剑指offer | 面试题5：从尾到头打印链表
- 剑指offer | 面试题6：重建二叉树
- 剑指offer | 面试题7：用两个栈实现队列
- 剑指offer | 面试题8：旋转数组的最小数字
- 剑指offer | 面试题9：斐波那契数列
- 剑指offer | 面试题10：青蛙跳台阶问题
- 剑指offer | 面试题11：矩阵覆盖
- 剑指offer | 面试题12：二进制中1的个数
- 剑指offer | 面试题13：数值的整数次方
- 剑指offer | 面试题14：打印从1到最大的n位数
- 剑指offer | 面试题15：删除链表的节点
- 剑指offer | 面试题16：将数组中的奇数放在偶数前
- 剑指offer | 面试题17：链表中倒数第k个节点
- 剑指offer | 面试题18：反转链表
- 剑指offer | 面试题19：合并两个有序链表
- 剑指offer | 面试题20：判断二叉树A中是否包含子树B
- 剑指offer | 面试题21：二叉树的镜像
- 剑指offer | 面试题22：顺时针打印矩阵
- 剑指offer | 面试题23：包含min函数的栈
- 剑指offer | 面试题24：栈的压入、弹出序列
- 剑指offer | 面试题25：从上到下打印二叉树
- 剑指offer | 面试题26：二叉搜索树的后序遍历序列
- 剑指offer | 面试题27：二叉树中和为某一值的路径
- 剑指offer | 面试题28：复杂链表的复制
- 剑指offer | 面试题29：二叉搜索树转换为双向链表
- 剑指offer | 面试题30：字符串的排列
- 剑指offer | 面试题31：数组中出现次数超过一半的数字
- 剑指offer | 面试题32：最小的k个数
- 剑指offer | 面试题33：连续子数组的最大和
- 剑指offer | 面试题34：1～n 整数中 1 出现的次数
- 剑指offer | 面试题35：把数组排成最小的数
- 剑指offer | 面试题36：丑数
“Leetcode : https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof
“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_37_firstUniqChar/Solution.java
第一个只出现一次的字符
题目描述 ：在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。s 只包含小写字母。
难度：简单
示例 1:
代码语言：javascript复制输入：s = "abaccdeff"
输出：'b'
示例 2:
代码语言：javascript复制输入：s = ""
输出：' '
方法一：哈希表
- 遍历字符串
s，使用哈希表统计 “各字符数量是否 > 1 ”。 - 再遍历字符串
s，在哈希表中找到首个 “数量为 1 的字符”，并返回。
算法流程:
- 初始化：HashMap 记为dic ;
- 字符统计：遍历字符串s中的每个字符c ;
- 若
dic中不包含键(key)c：则向dic中添加键值对(c, True)，代表字符c的数量为1 - 若
dic中包含键(key)c：则修改键c的键值对为(c, False)，代表字符c的数量>1
- 若
- 查找数量为 1 的字符：遍历字符串
s中的每个字符c；- 若
dic中键c对应的值为True：，则返回c。
- 若
- 返回
' '，代表字符串无数量为 1 的字符。
复杂度分析：
- 时间复杂度 O(N) ： N 为字符串
s的长度；需遍历s两轮，使用 O(N) ；HashMap 查找操作的复杂度为 O(1) ； - 空间复杂度 O(1)： 由于题目指出
s只包含小写字母，因此最多有 26 个不同字符，HashMap 存储需占用 O(26) = O(1) 的额外空间。
方法二:有序哈希表
在哈希表的基础上,有序哈希表中的键值对是按照插入顺序排序的。基于此，可通过遍历有序哈希表，实现搜索首个“数量为1的字符”。
哈希表是去重的，即哈希表中键值对数量 ≤ 字符串s的长度。因此,相比于方法一,方法二减少了第二 轮遍历的循环次数。当字符串很长(重复字符很多)时，方法二则效率更高。
复杂度分析: 时间和空间复杂度均与“方法一” 相同，而具体分析：方法一需遍历s两轮；方法二遍历s - -轮，遍历dic一轮(dic的长度不大于26)。
代码语言：javascript复制package com.nateshao.sword_offer.topic_37_firstUniqChar;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
/**
* @date Created by 邵桐杰 on 2021/12/14 18:15
* @微信公众号 程序员千羽
* @个人网站 www.nateshao.cn
* @博客 https://nateshao.gitee.io
* @GitHub https://github.com/nateshao
* @Gitee https://gitee.com/nateshao
* Description:在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。s 只包含小写字母。
* 示例 1: 输入：s = "abaccdeff" 输出：'b'
* https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
*/
public class Solution {
public static void main(String[] args) {
String s = "abaccdeff";
String s2 = "";
System.out.println("firstUniqChar(s) = " firstUniqChar(s));//firstUniqChar(s) = b
System.out.println("firstUniqChar(s2) = " firstUniqChar(s2));
System.out.println("firstUniqChar2(s) = " firstUniqChar2(s));//firstUniqChar2(s) = b
}
/**
* 利用 HashMap 和 LinkedHashMap（效率更高） 保存字符和出现次数。
* @param s
* @return
*/
public static char firstUniqChar(String s) {
if (s == null || s.length() == 0) return ' ';
char[] chars = s.toCharArray();
Map<Character, Boolean> hashMap = new HashMap<>();
// LinkedHashMap<Character, Boolean> linkedHashMap = new LinkedHashMap<>();
for (char c : chars) {
hashMap.put(c, !hashMap.containsKey(c));
}
for (char c : chars) {
if (hashMap.get(c)) return c;
}
return ' ';
}
public static char firstUniqChar2(String s) {
Map<Character, Boolean> dic = new LinkedHashMap<>();
char[] sc = s.toCharArray();
for(char c : sc)
dic.put(c, !dic.containsKey(c));
for(Map.Entry<Character, Boolean> d : dic.entrySet()){
if(d.getValue()) return d.getKey();
}
return ' ';
}
}
参考链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/solution/mian-shi-ti-50-di-yi-ge-zhi-chu-xian-yi-ci-de-zi-3/
