欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Go Java算法之字符串中第一個(gè)唯一字符詳解

 更新時(shí)間:2022年08月24日 10:11:43   作者:黃丫丫  
這篇文章主要為大家介紹了Go Java算法之字符串中第一個(gè)唯一字符詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

字符串中第一個(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)文章

  • Android圖片轉(zhuǎn)換器代碼分享

    Android圖片轉(zhuǎn)換器代碼分享

    本文給大家總結(jié)了下在安卓程序中進(jìn)行圖片轉(zhuǎn)換的方法,非常的實(shí)用,小伙伴們可以參考下。
    2015-10-10
  • Java中NIO的三大核心組件詳細(xì)解析

    Java中NIO的三大核心組件詳細(xì)解析

    這篇文章主要介紹了Java中NIO的三大核心組件詳細(xì)解析,NIO的Buffer類(lèi)是一個(gè)抽象類(lèi),位于java.nio包中,提供了一組更加有效的方法,用來(lái)進(jìn)行寫(xiě)入和讀取的交替訪問(wèn),本質(zhì)上是一個(gè)內(nèi)存塊,既可以寫(xiě)入數(shù)據(jù),也可以從中讀取數(shù)據(jù),需要的朋友可以參考下
    2023-12-12
  • java實(shí)現(xiàn)后臺(tái)處理base64圖片還原為文件

    java實(shí)現(xiàn)后臺(tái)處理base64圖片還原為文件

    這篇文章主要介紹了java實(shí)現(xiàn)后臺(tái)處理base64圖片還原為文件,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-02-02
  • Java利用for循環(huán)輸出空心菱形的實(shí)例代碼

    Java利用for循環(huán)輸出空心菱形的實(shí)例代碼

    這篇文章主要介紹了Java利用for循環(huán)輸出空心菱形的實(shí)例代碼,需要的朋友可以參考下
    2014-02-02
  • MyBatis接口綁定的實(shí)現(xiàn)方式和工作原理

    MyBatis接口綁定的實(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-03
  • java String的深入理解

    java String的深入理解

    這篇文章主要介紹了java String的深入理解的相關(guān)資料,希望通過(guò)本文大家能理解String的用法,需要的朋友可以參考下
    2017-09-09
  • Jax-rs規(guī)范下REST接口使用方法詳解

    Jax-rs規(guī)范下REST接口使用方法詳解

    這篇文章主要介紹了Jax-rs規(guī)范下REST接口使用方法詳解,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-09-09
  • Spring?Boot?DevTools?全局配置學(xué)習(xí)指南

    Spring?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)題

    這篇文章主要介紹了如何解決LocalDateTime傳值JSON格式化問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-08-08
  • Java字符流與字節(jié)流區(qū)別與用法分析

    Java字符流與字節(jié)流區(qū)別與用法分析

    這篇文章主要介紹了Java字符流與字節(jié)流區(qū)別與用法,較為詳細(xì)的分析了java字符流與字節(jié)流的概念、功能與使用方法,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
    2016-06-06

最新評(píng)論