タイトル説明:剣指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;
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 ' ';
}
char firstUniqChar2(char* s)
{
cout<<s<<endl;
cout<<*s<<endl;
if(s == nullptr)
return ' ';
int hashTble[256];
for(int i=0;i<256;i++)
{
hashTble[i]=0;
}
char* c = s;
while(*c != '\0')
{
hashTble[*(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;
メモ:ハッシュテーブルの定義を復習する:ハッシュテーブル:所与のテーブルM、存在関数f(key)、任意の所与のキーワード値keyに対して、関数を代入した後、そのキーワードを含むテーブルに記録されたアドレスを得ることができれば、テーブルMをハッシュ(Hash)テーブル、関数f(key)をハッシュ(Hash)関数と呼ぶ.