すべての異なる文字
1623 ワード
タイトルの説明:
1つのアルゴリズムを実装し、1つの文字列のすべての文字が異なるかどうかを決定します.追加のデータ構造の使用が許可されていないとしたら、どうすればいいですか?
問題解決の考え方:
ここでは文字セットがASCIIであると仮定し,まず簡単な最適化を行い,文字列の長さがアルファベット表の文字個数より大きい場合falseを直接返す.次に、インデックス値iに対応するタグが文字列にアルファベットのi番目の文字が含まれているかどうかを示すブール値の配列を構築します.この文字が2回目に現れると、すぐにfalseに戻ります.
コード:
1つのアルゴリズムを実装し、1つの文字列のすべての文字が異なるかどうかを決定します.追加のデータ構造の使用が許可されていないとしたら、どうすればいいですか?
問題解決の考え方:
ここでは文字セットがASCIIであると仮定し,まず簡単な最適化を行い,文字列の長さがアルファベット表の文字個数より大きい場合falseを直接返す.次に、インデックス値iに対応するタグが文字列にアルファベットのi番目の文字が含まれているかどうかを示すブール値の配列を構築します.この文字が2回目に現れると、すぐにfalseに戻ります.
コード:
public static boolean isUniqueChar(String str){
if(str.length() > 256){
return false;
}
boolean[] char_set = new boolean[256];
for(int i = 0; i < str.length(); i++){
int val = str.charAt(i);
//
if(char_set[val]){
return false;
}
char_set[val] = true;
}
return true;
}