剑指 Offer 50. 第一个只出现一次的字符【9】

￡神魔★判官ぃ 2023-09-26 11:09 18阅读 0赞

> **难度等级：简单**

> **上一篇算法：**
> 
> [剑指 Offer 58 - II. 左旋转字符串【字符串】][Offer 58 - II.]

> **力扣此题地址：**
> 
> [剑指 Offer 50. 第一个只出现一次的字符 - 力扣（LeetCode）][Offer 50. _ - _LeetCode]

## 1.题目： 第一个只出现一次的字符 ##

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

**示例 1:**

>     输入：s = "abaccdeff"
>     输出：'b'

## 2.解题思路： ##

> **（1）用HashMap集合：** 
> 
> 用 HashMap 添加每个字符与其出现的值，出现一次为true，出现两次及两次以上为false，然后再依次遍历字符串时，找到第一个出现值为true的字符，返回即可。
> 
> **（2）用字符数组：**
> 
> 因为该字符串全部是字母，所以可以用一个字符数组代替哈希表，数组下标就代表该字母。然后遍历字符串，在数组对应下标的地方为值加1，最后返回第一个值为1的下标。

## 3.代码实现： ##

**（1）用HashMap集合：**

class Solution {
        public char firstUniqChar(String s) {
    
            // 设置哈希表用来记录字符串中每个字符是否只出现过一次
            // key 为字符
            // value 为 boolean 类型
            // true 代表当前遍历的字符中，该字符出现了一次
            // false 代表当前遍历的字符中，该字符出现了两次或两次以上
            HashMap<Character, Boolean> dic = new HashMap<>();
    
            // 首先将字符串转换为字符数组的形式，方便遍历
            char[] charArray = s.toCharArray();
    
            // 遍历字符数组中的每个字符
            for(char c : charArray){
    
                // 1、首先以该字符作为 key ，在字典中进行查找是否存在
                Boolean result = dic.containsKey(c);
    
                // 2、如果该字符在字典中已经存在
                // 那么说明当前遍历的字符中，该字符出现了两次或两次以上
                if(result){
    
                    // 所以将 value 更新为 false
                    dic.put(c,false);
    
                // 3、如果该字符在字典中不存在
                // 那么说明当前遍历的字符中，该字符目前只出现了一次
                }else{
    
                    // 将 value 更新为 true
                    dic.put(c,true);
                }
    
            }
    
            // 再一次从头到尾遍历字符数组
            for(char c : charArray){
    
                // 以该字符作为 key ，在字典中进行查找对应的 value
                Boolean result = dic.get(c);
    
                // 如果发现 value 值为 true
                // 那么说明找到了第一个只出现一次的字符
                if(result){
    
                    // 返回这个字符
                    return c;
    
                }
            }
    
            // 否则说明所有字符都出现了两次或两次以上，或者字符串为空
            // 那么返回 ' '
            return ' ';
        }
    }

**（2）用字符数组：**

//方法二：数组代替哈希表
        public int FirstNotRepeatingChar(String str) {
            if(str==null || str.length()==0)
                return -1;
            // A-Z对应的ASCII码为65-90，a-z对应的ASCII码值为97-122
            int len=str.length();
            int[] count=new int[58]; //122-65+1
            for(int i=0;i<len;i++){
                char c=str.charAt(i);
                count[c-'A']++;
            }
            for(int i=0;i<len;i++){
                char c=str.charAt(i);
                if(count[c-'A']==1)
                    return i;
            }
            return -1;
        }

## 4.知识点补充: ##

> ### a\[0\]++是什么意思？ ###
> 
> a\[0\]表示数组中的第一个值，可以把它看成一个变量x,  
> a\[0\]++也就是数组中第一个值+1再存放到原位。  
> 比如 int a\[2\]; 其中a\[0\]=1; a\[1\]=5; a\[0\]++以后，a\[0\]的值变为2；

[Offer 58 - II.]: https://blog.csdn.net/m0_51697147/article/details/127267162
[Offer 50. _ - _LeetCode]: https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/