1つの文字列で最初の重複しない文字を検索
2474 ワード
問題の説明:パラメータとして文字列を受け入れ、最初の重複しない文字を返す関数を作成します.たとえば、文字列「abbcda」、cは最初の重複しない文字です.
解決方法:
方法1:LinkedHashMapを使用して文字の個数を記録します.LinkedHashMapは挿入要素の順序を維持しているので、文字列をスキャンするときは、LinkedHashMapを反復して1の要素を返すだけです.
実装コードは次のとおりです.
方法2:時間と空間の上で平衡して、一回の遍歴の中で重複しない文字を探し出して、1つのSetと1つのListを使ってそれぞれ重複しない文字と重複しない文字を保存して、私達が1つの時間の複雑度O(n)の文字列のスキャンを完成した後に、Listにアクセスすることによってこの重複しない文字を得ることができて、この時間の複雑度はO(1)で、Listは秩序があるため、get(0)によって最初の要素を得ることができます.
実装コードは次のとおりです.
方法3:方法2の考え方と同様に、HashMapを使用して、第1スキャンで各文字の現回数を計算した後、スキャン文字列を出して最初の重複しない文字を見つけます.
実装コードは次のとおりです.
コード:クリック
解決方法:
方法1:LinkedHashMapを使用して文字の個数を記録します.LinkedHashMapは挿入要素の順序を維持しているので、文字列をスキャンするときは、LinkedHashMapを反復して1の要素を返すだけです.
実装コードは次のとおりです.
public static char getNonRepeatCharacter(String str)
throws Exception {
Map counts = new LinkedHashMap<>();
for (char c : str.toCharArray()) {
counts.put(c, counts.containsKey(c) ? counts.get(c) + 1 : 1);
}
for (Map.Entry entry : counts.entrySet()) {
if (entry.getValue() == 1)
return entry.getKey();
}
throw new Exception("don't find any non repeated character!");
}
方法2:時間と空間の上で平衡して、一回の遍歴の中で重複しない文字を探し出して、1つのSetと1つのListを使ってそれぞれ重複しない文字と重複しない文字を保存して、私達が1つの時間の複雑度O(n)の文字列のスキャンを完成した後に、Listにアクセスすることによってこの重複しない文字を得ることができて、この時間の複雑度はO(1)で、Listは秩序があるため、get(0)によって最初の要素を得ることができます.
実装コードは次のとおりです.
public static char getNonRepeatCharacter(String str)
throws Exception {
Set repeated = new HashSet<>();
List nonRepeated = new LinkedList<>();
for (char c : str.toCharArray()) {
if (repeated.contains(c))
continue;
if (nonRepeated.contains(c)) {
nonRepeated.remove((Character)c);
repeated.add(c);
} else {
nonRepeated.add(c);
}
}
if (nonRepeated.size() > 0) {
return nonRepeated.get(0);
}
throw new Exception("don't find any non repeated character!");
}
方法3:方法2の考え方と同様に、HashMapを使用して、第1スキャンで各文字の現回数を計算した後、スキャン文字列を出して最初の重複しない文字を見つけます.
実装コードは次のとおりです.
public static char getNonRepeatCharacter(String str)
throws Exception {
HashMap map = new HashMap<>();
for (char c : str.toCharArray()) {
map.put(c, map.containsKey(c) ? map.get(c) + 1 : 1);
}
for (Map.Entry entry : map.entrySet()) {
if (entry.getValue() == 1) {
return entry.getKey();
}
}
throw new Exception("don't find any non repeated character!");
}
コード:クリック