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

Go Java算法之字符串中第一個唯一字符詳解

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

字符串中第一個唯一字符

給定一個字符串 s ,找到 它的第一個不重復的字符,并返回它的索引 。如果不存在,則返回 -1 。

  • 示例 1:

輸入: s = "leetcode"

輸出: 0

  • 示例 2:

輸入: s = "loveleetcode"

輸出: 2

  • 示例 3:

輸入: s = "aabb"

輸出: -1  

提示:

1 <= s.length <= 105

s 只包含小寫字母

方法一:哈希表(Java)

在第一次遍歷時,我們使用哈希映射統(tǒng)計出字符串中每個字符出現(xiàn)的次數(shù)。

在第二次遍歷時,我們只要遍歷到了一個只出現(xiàn)一次的字符,那么就返回它的索引,否則在遍歷結束后返回 -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:字符串長度

Σ:字符集

時間復雜度:O(n)

空間復雜度:O(∣Σ∣)

方法二:隊列(Go)

我們也可以借助隊列找到第一個不重復的字符。隊列具有「先進先出」的性質(zhì),因此很適合用來找出第一個滿足某個條件的元素。

具體地,我們使用與方法二相同的哈希映射,并且使用一個額外的隊列,按照順序存儲每一個字符以及它們第一次出現(xiàn)的位置。

當我們對字符串進行遍歷時,設當前遍歷到的字符為 c,如果 c 不在哈希映射中,我們就將 c 與它的索引作為一個二元組放入隊尾

否則我們就需要檢查隊列中的元素是否都滿足「只出現(xiàn)一次」的要求,即我們不斷地根據(jù)哈希映射中存儲的值(是否為 -1)選擇彈出隊首的元素,直到隊首元素「真的」只出現(xiàn)了一次或者隊列為空。

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:字符串長度

Σ:字符集

時間復雜度:O(n)

空間復雜度:O(∣Σ∣)

以上就是Go Java算法之字符串中第一個唯一字符詳解的詳細內(nèi)容,更多關于Go Java算法字符串唯一字符的資料請關注腳本之家其它相關文章!

相關文章

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

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

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

    Java中NIO的三大核心組件詳細解析

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

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

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

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

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

    MyBatis接口綁定的實現(xiàn)方式和工作原理

    在日常開發(fā)中,數(shù)據(jù)持久層是幾乎每個項目都會涉及的一個關鍵組成部分,MyBatis作為一個流行的持久層框架,其提供的接口綁定機制極大地簡化了數(shù)據(jù)庫操作,本文將通過詳細的代碼示例和講解,帶你深入理解MyBatis接口綁定的工作原理和實踐方式,需要的朋友可以參考下
    2024-03-03
  • java String的深入理解

    java String的深入理解

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

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

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

    Spring?Boot?DevTools?全局配置學習指南

    這篇文章主要介紹了Spring?Boot?DevTools?全局配置,注意包括直接重啟項目與devtools重啟的區(qū)別,DevTools配置,DevTools全局配置及trigger-file控制重啟行為的相關知識,需要的朋友可以參考下
    2022-03-03
  • 如何解決LocalDateTime傳值JSON格式化問題

    如何解決LocalDateTime傳值JSON格式化問題

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

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

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

最新評論