【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
回數的概念比較好玩，就是說有這麼一個字符串str， 長度為n， 現在index開始從0->index/2遍歷，那麼str[index] = str[n-1-index]，那麼這種數據就是我們通常說的回數。比如說a = “a”是回數，a = “aba”是回數，a = "strarts"也是回數。因為這道題目比較簡單，所以很多公司都喜歡用它來檢查程序員的基本編程能力。不光如此，它還能考察程序員考慮問題是否周密，是否從不同角度考慮問題。
比如說，現在我們要求字符串中的字符必須是小寫字母或者大寫字母，不能是其他字符，那該怎麼寫？朋友們可以試試。
int isSymbolRight(const char* str, int length)
{
int index;
char symbol;
for(index = 0; index < length; index++){
symbol = str[index];
if(symbol >= 'a' && symbol <= 'z' || symbol >= 'A' && symbol <= 'Z')
continue;
return 0;
}
return 1;
}
int isAnagramOrNot(const char* str, int length)
{
int index;
if(NULL == str || 0 == length)
return 0;
if(!isSymbolRight(str, length))
return 0;
for(index = 0; index < (length >> 1); index ++){
if(str[index] != str[length -1 -index])
return 0;
}
return 1;
}
int isSymbolRight(const char* str, int length)
{
int index;
char symbol;
for(index = 0; index < length; index++){
symbol = str[index];
if(symbol >= 'a' && symbol <= 'z' || symbol >= 'A' && symbol <= 'Z')
continue;
return 0;
}
return 1;
}
int isAnagramOrNot(const char* str, int length)
{
int index;
if(NULL == str || 0 == length)
return 0;
if(!isSymbolRight(str, length))
return 0;
for(index = 0; index < (length >> 1); index ++){
if(str[index] != str[length -1 -index])
return 0;
}
return 1;
} 上面的方法只是傳統上的比較方法，如果面試的考官說用遞歸的方法怎麼計算呢？朋友們可以再試一下。
int _isAnagramOrNot(const char* str, int length){
if(0 == length || 1 == length)
return 1;
return (str[0] == str[length -1]) ? _isAnagramOrNot(str +1, length-2) : 0;
}
int isAnagramOrNot(const char* str, int length)
{
if(NULL == str || 0 == length)
return 0;
if(!isSymbolRight(str, length))
return 0;
return _isAnagramOrNot(str, length);
}
int _isAnagramOrNot(const char* str, int length){
if(0 == length || 1 == length)
return 1;
return (str[0] == str[length -1]) ? _isAnagramOrNot(str +1, length-2) : 0;
}
int isAnagramOrNot(const char* str, int length)
{
if(NULL == str || 0 == length)
return 0;
if(!isSymbolRight(str, length))
return 0;
return _isAnagramOrNot(str, length);
} 那麼，我們把難度再提高一些，如果比較的數據很多，有1000萬個，那麼怎麼利用多核編程提高數據的處理速度呢？
int _isAnagramOrNot(const char* str, int start, int end, int length)
{
int index;
char symbol;
for(index = 0; index < length; index ++){
if(str[start + index] != str[end -1 - index])
return 0;
symbol = str[start + index];
if(symbol >= 'a' && symbol <= 'z' ||
symbol >= 'A' && symbol <= 'Z')
continue;
return 0;
}
return 1;
}
int isAnagramOrNot(const char* str, int length)
{
int index;
int start[2];
int end[2];
int result[2] = {0};
if(NULL == str || 0 == length)
return 0;
start[0] = 0;
start[1] = length >> 2;
end[0] = length;
end[1] = length - (length >>2);
#pragma omp parallel for
for(index = 0; index < 2; index ++)
result[index] = _isAnagramOrNot(str, start[index], end[index], length >> 2);
return (result[0] && result[1]) ? 1 : 0;
}
int _isAnagramOrNot(const char* str, int start, int end, int length)
{
int index;
char symbol;
for(index = 0; index < length; index ++){
if(str[start + index] != str[end -1 - index])
return 0;
symbol = str[start + index];
if(symbol >= 'a' && symbol <= 'z' ||
symbol >= 'A' && symbol <= 'Z')
continue;
return 0;
}
return 1;
}
int isAnagramOrNot(const char* str, int length)
{
int index;
int start[2];
int end[2];
int result[2] = {0};
if(NULL == str || 0 == length)
return 0;
start[0] = 0;
start[1] = length >> 2;
end[0] = length;
end[1] = length - (length >>2);
#pragma omp parallel for
for(index = 0; index < 2; index ++)
result[index] = _isAnagramOrNot(str, start[index], end[index], length >> 2);
return (result[0] && result[1]) ? 1 : 0;
}
總結：
（1）從上面的題目可以看出，即使很簡單的題目，也可以考察應聘者的總和能力
（2）提高算法執行效率的途徑很多，朋友們平時課可以多多留意、多多積累
（3）所有算法的執行都是以正確性和健壯性為前提的，必須建立在充分測試的基礎之上
