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 等刷题网站。

巴特西

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

最新文章

热门文章