Leetcode) First Unique Character in a String
Top Interview Questions
Easy Collection
Link of Problem
LEVEL : 🌕 🌕 🌑 🌑 🌑 (下)
Easy Collection Stringの3番目の問題
これはStringに一度しか現れないCharacterを検索し、そのCharacterのindexを返す問題です.
私は問題を見ると
3つでも出られます4 5...無限に登場できるので
しかし、私は他の方法を見つけました.
第1の方法は、
2つの
二つに分けた理由は
まず、最初のfor文で、sに含まれる文字がキー値としてリストに含まれているかどうかを確認します.
2番目のfor文ではindexsも同様に乱雑であるため,まずvalueを中心にsortを行い,それに応じてキー値とindex値を取り出す.
ポップアップキー値がlistから0を出力するとindexが返されます.
2番目のfor文から返されない場合は、すべての文字が重複していることを示しますので、-1を返します.
ご覧の通り、Runtimeは
時間を減らすために他の人が作ったコードを見て新鮮な方法だったので持ってきました
この方式は今Runtimeが一番速いので、見ましたが、斬新すぎます.
難しい方法ではないが、それでも解決できる方法を考えている.
私がc言語を習い始めたばかりの頃よく使っていた方法
これがUnicodeを使う方法です.
まず
そして各格子に0で初期化
たとえば、「c」と入力すると、「c」はUnicodeで99に相当するため、「c」-「a」と入力すると2が表示されます.counter[2]はCのセルですが、私たちが考えているインデックスに従って入っていることがわかりますよね?
各文字がインデックスに一致する場合、インデックスの数値は+1で増加します.
つまり、0なら何も入ってこない.1なら1個入り2個入りました
2番目のfor文でcounterの値が1の場合、対応する
最初とは異なる配列を使用しているので、既に入力順に並べられているので、個別に並べ替える必要はなく、Arrayが26箇所で作成されているので、より便利です.
Runtimeが一気に下がっているのが見えます
一番早いのはRuntime!2階建てのforゲートを使ったのに一番早かったのでびっくり
今回はArrayとSetを使いました
この問題はcharsの各文字を取り出し、自分のindexの後ろのすべての文字と1つずつ対照して解きます.
後ろに同じ文字がある場合、skipcharsというsetにその文字が配置され、次回その文字の番になるとwhere条件で選択され、再びfor文は許可されません.
後に自分と同じ文字がない場合は、isUniqueというBooleanタイプをtrueに設定し、インデックスを返します.
皆さんがご覧のように時間が経つのはとても速いです2階建てのドアですが、Runtimeが出るのが一番速い!!
含まれている子供たちを直接排除したのか、forゲートを回って戻ってきたからではなく、今の状態でUniqueだとインデックスを返す方式なので、スピードが速いのかもしれません.
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だとインデックスを返す方式なので、スピードが速いのかもしれません.
Reference
この問題について(Leetcode) First Unique Character in a String), 我々は、より多くの情報をここで見つけました https://velog.io/@yoonah-dev/Leetcode-First-Unique-Character-in-a-Stringテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol