剣はOffer 50を指します——第1個は一回の文字だけ現れます


  • タイトル説明:剣指Offer 50.1番目に1回しか現れない文字は、文字列sにおいて1番目に1回しか現れない文字を探し出す.ない場合は、単一のスペースを返します.sは小文字のみを含む.例:s=「abaccdeff」は「b」s=「」は「」の制限を返す:0<=sの長さ<=50000
  • 分析:ハッシュ配列として新しい配列を作成し、与えられた文字列の各文字の出現回数を格納し、キー値keyは文字を格納し、値valueはその文字の出現回数を格納することを構想している.ここで、文字(char)は1バイトを占め、長さは8、すなわち1(byte)=8(bit)であるため、256種類の可能性があり、新規hashテーブルの長さは256であり、すべての値を0に初期化する必要がある.
  • コード:ここでは2種類使用しています.1つは自分で書いたC+、1つは剣指書のCです.その中でCの中で理解しにくい部分はポインタの使用です.普段はC++で練習して使い慣れています.Cポインタはここでは慣れていませんが、把握する必要があります.
  • #include
    #include
    #include
    using namespace std;
    
    //C++
    char firstUniqChar(string s) 
    {
         
        if(s.empty())
            return ' ';
        int len = s.size();
        vector<int> hashTable(256);
        for(int i=0;i<256;i++)
        {
         
            hashTable[i] = 0;
        }
            
        int i=0;
        for(int i=0;i<len;i++)
        {
         
            hashTable[s[i]]++;
        }
        for(int i=0;i<len;i++)
        {
         
            if(hashTable[s[i]] == 1)
                return s[i];
        }
        return ' ';
    
    }
    
    //c
    char firstUniqChar2(char* s)
    {
         
    	cout<<s<<endl;//  “abc”
    	cout<<*s<<endl;//  “a”
        if(s == nullptr)
            return ' ';
    
        int hashTble[256];
        for(int i=0;i<256;i++)
        {
         
            hashTble[i]=0;
        }
        char* c = s;//     char*   , c=s    
        while(*c != '\0')
        {
         
            hashTble[*(c++)]++;//   *(c++),   c       ,  *c       
        }
        c = s;
        while(*c != '\0')
        {
         
            if(hashTble[*c] == 1)
                return *c;
            c++;
        }
        return ' ';
    }
    
    
    int main()
    {
         
    	char* s = (char*)malloc(sizeof(char)*3);
    	cin>>s;
    	//cout<
    	
    	cout<<firstUniqChar2(s);
    	
    	free(s);
    	return 0;
    }
    
  • メモ:ハッシュテーブルの定義を復習する:ハッシュテーブル:所与のテーブルM、存在関数f(key)、任意の所与のキーワード値keyに対して、関数を代入した後、そのキーワードを含むテーブルに記録されたアドレスを得ることができれば、テーブルMをハッシュ(Hash)テーブル、関数f(key)をハッシュ(Hash)関数と呼ぶ.