【题50】第一个只出现一次的字符

阳光穿透心脏的1/2处 2022-03-07 18:09 293阅读 0赞

【题目】  
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.  
【思路】  
可以统计字符串中每个字符的出现次数，  
1.使用两个list记录出现过的字符  
【实现】

import java.util.ArrayList;
    import java.util.List;
    public class Solution {
        public int FirstNotRepeatingChar(String str) {
            if(str.length() == 0 ||str == null){
                return -1;
            }
            List<Character> lista = new ArrayList<>();
            List<Character> listb = new ArrayList<>();
            for(int i =0;i<str.length();i++){
                char ch = str.charAt(i);//获取索引i处的字符
                if(!lista.contains(ch) && !listb.contains(ch)){//如果a，b都不包含当前字符
                    lista.add(Character.valueOf(ch));//返回一个指定的char值的character实例，添加到a中
                }else{
                    lista.remove(Character.valueOf(ch));//删除a中的当前字符
                    listb.add(Character.valueOf(ch));//将该字符添加到b中
                }
            }
            if(lista.size()<=0){//删没了，说明没有只出现一次的字符
                return -1;
            }
            return str.indexOf(lista.get(0));
        }
    }

【例】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
2.使用哈希表，键值是字符，值是出现的次数。  
需要从头开始扫描字符串两次，第一次扫描字符串时，每扫到一个字符，就在哈希表的对应项中把次数加1，第二次扫描时，每扫描到一个字符，就能从哈希表中得到该字符出现的次数。  
【实现】

import java.util.LinkedHashMap;
    public class Solution {
        public int FirstNotRepeatingChar(String str) {
            LinkedHashMap<Character,Integer> map = new LinkedHashMap<Character,Integer>();
            for(int i = 0;i<str.length();i++){
                if(map.containsKey(str.charAt(i))){//如果哈希表包含键为当前字符
                    int time = map.get(str.charAt(i));//获取当前字符的值
                    map.put(str.charAt(i),++time);//将该字符添加到map，value+1
                }else{//如果哈希表中不包含当前字符，添加到哈希表中
                    map.put(str.charAt(i),1);
                }
            }
            for(int i =0;i<str.length();i++){
                char c = str.charAt(i);
                if(map.get(c)==1){
                    return i;
                }
            }
            return -1;
        }
    }

【例】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]  
参考：  
1.《剑指offer》  
2.[https://blog.csdn.net/hsj1213522415/article/details/72763786][https_blog.csdn.net_hsj1213522415_article_details_72763786]  
3.[https://www.nowcoder.com/profile/844008/codeBookDetail?submissionId=1515918][https_www.nowcoder.com_profile_844008_codeBookDetail_submissionId_1515918]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220307/e21b44b481c54c37bf4d61b34b0c3e7a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 1]: /images/20220307/29d67c4ec79b4aa7a084617dcba729c5.png
[https_blog.csdn.net_hsj1213522415_article_details_72763786]: https://blog.csdn.net/hsj1213522415/article/details/72763786
[https_www.nowcoder.com_profile_844008_codeBookDetail_submissionId_1515918]: https://www.nowcoder.com/profile/844008/codeBookDetail?submissionId=1515918
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70 2]: /images/20220307/7e39e02edd194140a4b28a5b10a2bcde.png