Leetcode) First Unique Character in a String


Top Interview Questions
Easy Collection
Link of Problem
LEVEL : 🌕 🌕 🌑 🌑 🌑 (下)
Easy Collection Stringの3番目の問題First Unique Character in a Stringを解いた.
これはStringに一度しか現れないCharacterを検索し、そのCharacterのindexを返す問題です.
私は問題を見るとStackでいいです!やったことがありますが、繰り返しは2つだけではなく、安易に2つだと思っています.
3つでも出られます4 5...無限に登場できるのでStackは絶対似合わない
しかし、私は他の方法を見つけました.

1𗞚𗞚第1の方法


第1の方法は、Dictionaryを使用することである.
2つのDictionaryが作成され、1つ目はCharacterが現れるCountを計算し、2つ目はCharacterを格納するindexである.
二つに分けた理由はDictionaryに順番がないため、一つずつ入れてもごちゃごちゃ...😂
まず、最初のfor文で、sに含まれる文字がキー値としてリストに含まれているかどうかを確認します.없으면対応するキー値を入力し、0をvalueとします.indexsに値が入力されていない場合は、index値がvalueとして使用されます.있으면値は+1で、対応するcharがあります.
2番目のfor文ではindexsも同様に乱雑であるため,まずvalueを中心にsortを行い,それに応じてキー値とindex値を取り出す.
ポップアップキー値がlistから0を出力するとindexが返されます.
2番目のfor文から返されない場合は、すべての文字が重複していることを示しますので、-1を返します.
func firstUniqChar(_ s: String) -> Int {
    var lists: [Character: Int] = [:]
    var indexs: [Character: Int] = [:]
    
    for (index, char) in s.enumerated() {
        if lists.keys.contains(char) {
            if let num = lists[char] {
                lists.updateValue(num+1, forKey: char)
            }
        } else {
            lists[char] = 0
            if !indexs.keys.contains(char) {
                indexs[char] = index
            }
        }
    }
    
    for (key, index) in indexs.sorted(by: { $0.1 < $1.1 }) {
        if lists[key] == 0 {
            return index
        }
    }
    
    return -1
}

ご覧の通り、Runtimeは276msを費やしました.全体の稼働時間は中程度です.
時間を減らすために他の人が作ったコードを見て新鮮な方法だったので持ってきました

2▼▼▼第1の方法


この方式は今Runtimeが一番速いので、見ましたが、斬新すぎます.
難しい方法ではないが、それでも解決できる方法を考えている.
私がc言語を習い始めたばかりの頃よく使っていた方法
これがUnicodeを使う方法です.
まずArrayを作成し26マスを生成小文字の個数を考えればいい
そして各格子に0で初期化'a'의 유니코드に基づいて、各文字にインデックスを付与します.
たとえば、「c」と入力すると、「c」はUnicodeで99に相当するため、「c」-「a」と入力すると2が表示されます.counter[2]はCのセルですが、私たちが考えているインデックスに従って入っていることがわかりますよね?
各文字がインデックスに一致する場合、インデックスの数値は+1で増加します.
つまり、0なら何も入ってこない.1なら1個入り2個入りました
2番目のfor文でcounterの値が1の場合、対応するindex(i)が返されます.
最初とは異なる配列を使用しているので、既に入力順に並べられているので、個別に並べ替える必要はなく、Arrayが26箇所で作成されているので、より便利です.
extension UnicodeScalar {
    var intValue: Int {
        return Int(value)
    }
}

func firstUniqChar(_ s: String) -> Int {
    var counter = Array(repeating: 0, count: 26)
    let a_unicode = UnicodeScalar("a").intValue
    
    for c in s.unicodeScalars {
        counter[c.intValue - a_unicode] += 1
    }
    
    var i = 0
    for c in s.unicodeScalars {
        if counter[c.intValue - a_unicode] == 1 {
            return i
        }
        
        i += 1
    }
    
    return -1
}

Runtimeが一気に下がっているのが見えます

3ππ第1の方法


一番早いのはRuntime!2階建てのforゲートを使ったのに一番早かったのでびっくり
今回はArrayとSetを使いました
この問題はcharsの各文字を取り出し、自分のindexの後ろのすべての文字と1つずつ対照して解きます.
後ろに同じ文字がある場合、skipcharsというsetにその文字が配置され、次回その文字の番になるとwhere条件で選択され、再びfor文は許可されません.
後に自分と同じ文字がない場合は、isUniqueというBooleanタイプをtrueに設定し、インデックスを返します.
func firstUniqChar(_ s: String) -> Int {
    let chars: [Character] = [Character](s)
    var skipChars: Set<Character> = []
    
    for i in 0 ..< chars.count where !skipChars.contains(chars[i]) {
        var isUnique: Bool = true
        
        for j in i + 1 ..< chars.count {
            guard isUnique else { break }
            if chars[i] == chars[j] {
                isUnique = false
                skipChars.insert(chars[i])
                break
            }
        }
        
        if isUnique { return i }
    }
    
    return -1
}


皆さんがご覧のように時間が経つのはとても速いです2階建てのドアですが、Runtimeが出るのが一番速い!!
含まれている子供たちを直接排除したのか、forゲートを回って戻ってきたからではなく、今の状態でUniqueだとインデックスを返す方式なので、スピードが速いのかもしれません.