LeetCode Top Interview Questions 387. First Unique Character in a String (Java版; Easy)

左手的ㄟ右手 2023-07-03 02:35 23阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 387. First Unique Character in a String (Java版; Easy) ##

#### 题目描述 ####

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.
    
    Examples:
    
    s = "leetcode"
    return 0.
    
    s = "loveleetcode",
    return 2.
    Note: You may assume the string contain only lowercase letters.

#### 第一次做;bit-map记录每个字符出现的次数, 位置信息在原始字符串中; 下面的那个做法在处理位置信息时愚蠢了… ####

class Solution { 
        public int firstUniqChar(String s) { 
            if(s==null||s.length()==0)
                return -1;
            //
            int[] arr = new int[26];
            for(int i=0; i<s.length(); i++){ 
                char ch = s.charAt(i);
                arr[ch-'a']++;
            }
            for(int i=0; i<s.length(); i++){ 
                char ch = s.charAt(i);
                if(arr[ch-'a']==1)
                    return i;
            }
            return -1;
        }
    }

#### 第一次做;bit-map记录出现次数; StringBuilder记录位置信息(这么做就麻烦了… 直接再遍历一次原始字符串即可); 时间复杂度O(N), 空间复杂度O(N) ####

/** 26个英文字母, 使用bit-map, 记录每个字符出现的次数, 再配合一个StringBuilder记录扫描过的字符从而保留位置信息 向面试官确认一下是否只有26个英文小写/大写字母 如果是全体ascii的话就需要一个更大一些的数组 */
    class Solution { 
        public int firstUniqChar(String s) { 
            if(s==null||s.length()==0)
                return -1;
            //
            int[] arr = new int[26];
            StringBuilder sb = new StringBuilder();
            for(int i=0; i<s.length(); i++){ 
                char ch = s.charAt(i);
                arr[ch-'a']++;
                sb.append(ch);
            }
            for(int i=0; i<sb.length(); i++){ 
                char ch = sb.charAt(i);
                if(arr[ch-'a']==1)
                    return i;
            }
            return -1;
            
        }
    }

#### leetcode题解中关于该问题的其它思考 ####

Good O(n) solution, but it still can be improved, since you read through the whole array twice. 
    Take an example of DNA sequence: there could be millions of letters long with just 4 alphabet 
    letter. What happened if the non-repeated letter is at the end of DNA sequence? This would 
    dramatically increase your running time since we need to scan it again.

可以使用两个哈希表解决上述问题, 一个哈希表记录出现次数, 另一个哈希表记录索引. 最后遍历第一个哈希表; 我对遍历哈希表的语法不熟

class Solution { 
        public int firstUniqChar(String s) { 
            Map<Character, Integer> feq = new HashMap<>();
            Map<Character, Integer> index = new HashMap<>();
            for (int i = 0; i < s.length(); i++) { 
                feq.put(s.charAt(i), feq.getOrDefault(s.charAt(i), 0) + 1);
                index.put(s.charAt(i), i);
            }
            
            int min = Integer.MAX_VALUE;     
            for (char c : feq.keySet()) { 
                if (feq.get(c) == 1) { 
                    min = Math.min(min, index.get(c));
                }
            }
            
            return min == Integer.MAX_VALUE ? -1 : min;
        }
    }

[welcome to my blog]: https://littlehaes.com