leetcode.字符串中的第一个唯一字符

迈不过友情╰ 2022-12-30 03:40 163阅读 0赞

### 文章目录 ###

*  字符串中的第一个唯一字符
 *   *  官方的代码
     *  1.使用哈希表存储频数
     *  2.使用哈希表存储索引
     *  3.队列
     *  我的代码

# 字符串中的第一个唯一字符 #

## 官方的代码 ##

## 1.使用哈希表存储频数 ##

class Solution { 
    public:
        int firstUniqChar(string s) { 
            unordered_map<int, int> frequency;
            for (char ch: s) { 
                ++frequency[ch];
            }
            for (int i = 0; i < s.size(); ++i) { 
                if (frequency[s[i]] == 1) { 
                    return i;
                }
            }
            return -1;
        }
    };

## 2.使用哈希表存储索引 ##

class Solution { 
    public:
        int firstUniqChar(string s) { 
            unordered_map<int, int> position;
            int n = s.size();
            for (int i = 0; i < n; ++i) { 
                if (position.count(s[i])) { 
                    position[s[i]] = -1;
                }
                else { 
                    position[s[i]] = i;
                }
            }
            int first = n;
            for (auto [_, pos]: position) { 
                if (pos != -1 && pos < first) { 
                    first = pos;
                }
            }
            if (first == n) { 
                first = -1;
            }
            return first;
        }
    };

## 3.队列 ##

class Solution { 
        public int firstUniqChar(String s) { 
            Map<Character, Integer> position = new HashMap<Character, Integer>();
            Queue<Pair> queue = new LinkedList<Pair>();
            int n = s.length();
            for (int i = 0; i < n; ++i) { 
                char ch = s.charAt(i);
                if (!position.containsKey(ch)) { 
                    position.put(ch, i);
                    queue.offer(new Pair(ch, i));
                } else { 
                    position.put(ch, -1);
                    while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) { 
                        queue.poll();
                    }
                }
            }
            return queue.isEmpty() ? -1 : queue.poll().pos;
        }
    
        class Pair { 
            char ch;
            int pos;
    
            Pair(char ch, int pos) { 
                this.ch = ch;
                this.pos = pos;
            }
        }
    }

## 我的代码 ##

package first_unique_character_in_a_string;
    
    /** * 387. 字符串中的第一个唯一字符 * first-unique-character-in-a-string * 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。 * 如果不存在，则返回 -1。 * */
    public class Solution1 { 
    	
        public int firstUniqChar(String s) { 
        	int fuc = -1;
        	char[] arr = s.toCharArray();
        	int[] zimu = new int[26];
        	//统计字符在字母表出现的频率
        	for (int i = 0; i < arr.length; i++) { 
        		int c = arr[i]-97;
        		zimu[c] += 1;
    		}
        	//根据字符串中字符的下标遍历判断
        	for (int i = 0; i < arr.length; i++) { 
        		int c = arr[i]-97;
    			if(zimu[c]==1) { 
    				fuc = i;
    				break;
    			}
    		}
        	return fuc;
        }
        
        public static void main(String[] args) { 
    		System.out.println(new Solution1()
    				.firstUniqChar("leetcode"));
    	}
        
    }