C++算法原理与实践(面试中的算法和准备过程)

第0部分 简介

1. 举个例子:面试的时候,可能会出一道算法考试题,比如写一个 strstr 函数——字符串匹配。

可能会想到用KMP算法来解题,但是该算法很复杂,不适宜在面试中使用。

1.1 C++利用char*的例子。该方法的复杂度是O(n)。注意代码中的注释,每一对括号的后面都给出了注释说明,用于匹配括号。

/**
strstr
return the position of the first occurence of string target
in string source, or -1 if target is not part of source
*/
int strstr(char *src, char *dest)
{
int len = ;
for (int i = ; dest[i] != '\0'; i++)
len++; int i = , j = ;
while (src[i] != '\0')
{
if (src[i] == dest[j])
{
j++;
if (j == len)
{
return i - j + ;
} // if j == len
} // if src[i] == dest[j]
else
{
j = ;
} // else i++;
} // while src[i] != '\0'
return -;
} // strstr int main()
{
char *src = "i am a chinese ";
char *dest = "a "; printf("%d\n", strstr(src, dest)); return ;
}

这一种是非常普通的解法。

1.2. 注意编码规范问题,比如加入空格、适当的缩进。

1.3. strlen() 函数的时间复杂度是 O(n),要尽量减少使用次数。

2. IT技术人员应该具备“翻越长城墙”这一基本技能。

3. 编码风格应该参照《google coding style》

  编码风格:缩进、拓号、变量名。

  编码习惯:异常检查、边界处理。

4. 面试的过程中要注意自己沟通能力的展现,让面试官时刻明白你的意图。

 面试被要求写代码时,应该主动写出合理的测试用例(Testcase)。

5. 如何练习算法

  资源:leetcode 、 cc150 等刷题网站。

上一篇:Java高并发秒杀API之web层


下一篇:EF 1