いくつかの面接のテーマについて
1778 ワード
1つのアルゴリズムを実装し、1つの文字列のすべての文字が同じかどうかを決定します.
最も考えられる方法は,その文字列の各文字を比較することにより,アルゴリズムの時間的複雑度が0(n 2)回である.
もう1つの方法は、setに重複する文字が存在することが許されないため、setデータ構造を利用して実現することができる.興味深い点は、判断を行う前に文字列の長さを判断することができ、文字列の長さが256より大きい場合、その文字列に重複する文字があることを肯定することができる.
Pythonコードは以下のように実現される.
C++コード:
Javaコード:
最も考えられる方法は,その文字列の各文字を比較することにより,アルゴリズムの時間的複雑度が0(n 2)回である.
もう1つの方法は、setに重複する文字が存在することが許されないため、setデータ構造を利用して実現することができる.興味深い点は、判断を行う前に文字列の長さを判断することができ、文字列の長さが256より大きい場合、その文字列に重複する文字があることを肯定することができる.
Pythonコードは以下のように実現される.
a = "11fdwqdgf5hg56gfwdqwsdqwd";
# set
def judge():
t = set(a);
N = len(a);
if(t == N):
return ('TRUE');
else:
print(t);
return ('FALSE');
#
def judge2():
N = len(a);
for i in range(N):
s = a[i];
for j in range(i,N,1):
if(s == a[j]):
return ('FALSE');
return "true"
if __name__ == "__main__":
print(judge());
print(judge2());
C++コード:
bool judge(const string str){
vector<bool> char_set(256,false);
for (int i = 0;i<str.length();i++){
int val = str[i];
cout<<"val:"<<char_set[val]<<endl;
if(char_set[val]){
return false;
}else{
char_set[val] = true;
}
}
return true;
}
Javaコード:
public boolean judge(final String str){
if (str.length() > 256){
return false;
}else{
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;
}