Go Java算法之字符串中第一個(gè)唯一字符詳解
字符串中第一個(gè)唯一字符
給定一個(gè)字符串 s ,找到 它的第一個(gè)不重復(fù)的字符,并返回它的索引 。如果不存在,則返回 -1 。
- 示例 1:
輸入: s = "leetcode"
輸出: 0
- 示例 2:
輸入: s = "loveleetcode"
輸出: 2
- 示例 3:
輸入: s = "aabb"
輸出: -1
提示:
1 <= s.length <= 105
s 只包含小寫(xiě)字母
方法一:哈希表(Java)
在第一次遍歷時(shí),我們使用哈希映射統(tǒng)計(jì)出字符串中每個(gè)字符出現(xiàn)的次數(shù)。
在第二次遍歷時(shí),我們只要遍歷到了一個(gè)只出現(xiàn)一次的字符,那么就返回它的索引,否則在遍歷結(jié)束后返回 -1。
class Solution { public int firstUniqChar(String s) { Map<Character, Integer> frequency = new HashMap<Character, Integer>(); for (int i = 0; i < s.length(); ++i) { char ch = s.charAt(i); frequency.put(ch, frequency.getOrDefault(ch, 0) + 1); } for (int i = 0; i < s.length(); ++i) { if (frequency.get(s.charAt(i)) == 1) { return i; } } return -1; } }
n:字符串長(zhǎng)度
Σ:字符集
時(shí)間復(fù)雜度:O(n)
空間復(fù)雜度:O(∣Σ∣)
方法二:隊(duì)列(Go)
我們也可以借助隊(duì)列找到第一個(gè)不重復(fù)的字符。隊(duì)列具有「先進(jìn)先出」的性質(zhì),因此很適合用來(lái)找出第一個(gè)滿(mǎn)足某個(gè)條件的元素。
具體地,我們使用與方法二相同的哈希映射,并且使用一個(gè)額外的隊(duì)列,按照順序存儲(chǔ)每一個(gè)字符以及它們第一次出現(xiàn)的位置。
當(dāng)我們對(duì)字符串進(jìn)行遍歷時(shí),設(shè)當(dāng)前遍歷到的字符為 c,如果 c 不在哈希映射中,我們就將 c 與它的索引作為一個(gè)二元組放入隊(duì)尾
否則我們就需要檢查隊(duì)列中的元素是否都滿(mǎn)足「只出現(xiàn)一次」的要求,即我們不斷地根據(jù)哈希映射中存儲(chǔ)的值(是否為 -1)選擇彈出隊(duì)首的元素,直到隊(duì)首元素「真的」只出現(xiàn)了一次或者隊(duì)列為空。
type pair struct { ch byte pos int } func firstUniqChar(s string) int { n := len(s) pos := [26]int{} for i := range pos[:] { pos[i] = n } q := []pair{} for i := range s { ch := s[i] - 'a' if pos[ch] == n { pos[ch] = i q = append(q, pair{ch, i}) } else { pos[ch] = n + 1 for len(q) > 0 && pos[q[0].ch] == n+1 { q = q[1:] } } } if len(q) > 0 { return q[0].pos } return -1 }
n:字符串長(zhǎng)度
Σ:字符集
時(shí)間復(fù)雜度:O(n)
空間復(fù)雜度:O(∣Σ∣)
以上就是Go Java算法之字符串中第一個(gè)唯一字符詳解的詳細(xì)內(nèi)容,更多關(guān)于Go Java算法字符串唯一字符的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
java實(shí)現(xiàn)后臺(tái)處理base64圖片還原為文件
這篇文章主要介紹了java實(shí)現(xiàn)后臺(tái)處理base64圖片還原為文件,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-02-02Java利用for循環(huán)輸出空心菱形的實(shí)例代碼
這篇文章主要介紹了Java利用for循環(huán)輸出空心菱形的實(shí)例代碼,需要的朋友可以參考下2014-02-02MyBatis接口綁定的實(shí)現(xiàn)方式和工作原理
在日常開(kāi)發(fā)中,數(shù)據(jù)持久層是幾乎每個(gè)項(xiàng)目都會(huì)涉及的一個(gè)關(guān)鍵組成部分,MyBatis作為一個(gè)流行的持久層框架,其提供的接口綁定機(jī)制極大地簡(jiǎn)化了數(shù)據(jù)庫(kù)操作,本文將通過(guò)詳細(xì)的代碼示例和講解,帶你深入理解MyBatis接口綁定的工作原理和實(shí)踐方式,需要的朋友可以參考下2024-03-03Spring?Boot?DevTools?全局配置學(xué)習(xí)指南
這篇文章主要介紹了Spring?Boot?DevTools?全局配置,注意包括直接重啟項(xiàng)目與devtools重啟的區(qū)別,DevTools配置,DevTools全局配置及trigger-file控制重啟行為的相關(guān)知識(shí),需要的朋友可以參考下2022-03-03如何解決LocalDateTime傳值JSON格式化問(wèn)題
這篇文章主要介紹了如何解決LocalDateTime傳值JSON格式化問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2022-08-08