いくつかの面接のテーマについて

1778 ワード

1つのアルゴリズムを実装し、1つの文字列のすべての文字が同じかどうかを決定します.
最も考えられる方法は,その文字列の各文字を比較することにより,アルゴリズムの時間的複雑度が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;
		
	}