三国志之见龙卸甲票房:一步一步写算法（之 回数）

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】

回数的概念比较好玩，就是说有这么一个字符串str， 长度为n， 现在index开始从0->index/2遍历，那么str[index] = str[n-1-index]，那么这种数据就是我们通常说的回数。比如说a = “a”是回数， a = “aba”是回数， a = "strarts"也是回数。因为这道题目比较简单，所以很多公司都喜欢用它来检查程序员的基本编程能力。不光如此，它还能考察程序员考虑问题是否周密，是否从不同角度考虑问题。

比如说，现在我们要求字符串中的字符必须是小写字母或者大写字母，不能是其他字符，那该怎么写？朋友们可以试试。

view plaincopy to clipboardprint?

1. int isSymbolRight(const char* str, int length)
2. {
3. int index;
4. char symbol;
6. for(index = 0; index < length; index++){
7. symbol = str[index];
9. if(symbol >= 'a' && symbol <= 'z' || symbol >= 'A' && symbol <= 'Z')
10. continue;
12. return 0;
13. }
15. return 1;
16. }
18. int isAnagramOrNot(const char* str, int length)
19. {
20. int index;
22. if(NULL == str || 0 == length)
23. return 0;
25. if(!isSymbolRight(str, length))
26. return 0;
28. for(index = 0; index < (length >> 1); index ++){
29. if(str[index] != str[length -1 -index])
30. return 0;
31. }
33. return 1;
34. }

view plaincopy to clipboardprint?

1. int _isAnagramOrNot(const char* str, int length){
2. if(0 == length || 1 == length)
3. return 1;
5. return (str[0] == str[length -1]) ? _isAnagramOrNot(str +1, length-2) : 0;
6. }
8. int isAnagramOrNot(const char* str, int length)
9. {
10. if(NULL == str || 0 == length)
11. return 0;
13. if(!isSymbolRight(str, length))
14. return 0;
16. return _isAnagramOrNot(str, length);
17. }

view plaincopy to clipboardprint?

1. int _isAnagramOrNot(const char* str, int start, int end, int length)
2. {
3. int index;
4. char symbol;
6. for(index = 0; index < length; index ++){
7. if(str[start + index] != str[end -1 - index])
8. return 0;
10. symbol = str[start + index];
11. if(symbol >= 'a' && symbol <= 'z' ||
12. symbol >= 'A' && symbol <= 'Z')
13. continue;
15. return 0;
16. }
18. return 1;
19. }
21. int isAnagramOrNot(const char* str, int length)
22. {
23. int index;
24. int start[2];
25. int end[2];
26. int result[2] = {0};
28. if(NULL == str || 0 == length)
29. return 0;
31. start[0] = 0;
32. start[1] = length >> 2;
33. end[0] = length;
34. end[1] = length - (length >>2);
36. #pragma omp parallel for
37. for(index = 0; index < 2; index ++)
38. result[index] = _isAnagramOrNot(str, start[index], end[index], length >> 2);
40. return (result[0] && result[1]) ? 1 : 0;
41. }

总结：

（1）从上面的题目可以看出，即使很简单的题目，也可以考察应聘者的总和能力

（2）提高算法执行效率的途径很多，朋友们平时课可以多多留意、多多积累

（3）所有算法的执行都是以正确性和健壮性为前提的，必须建立在充分测试的基础之上