《剑指Offer》第3章笔记 高质量代码 P1

除了程序代码的正确性，经常我们还要关注它的鲁棒性。

1 面试官谈代码质量

“一般会考查应聘人员对代码的容错处理能力，对一些特别的输入会询问应聘人员是否考虑、如何处理。不能容忍代码只是针对一种假想的‘正常值’进行处理，不考虑异常状况，也不考虑资源的回收等问题。”

—— 殷焰（支付宝，高级安全测试工程师）

“如果是因为粗心犯错，则可以原谅，因为毕竟面试的时候会紧张；不能容忍的是，该掌握的知识点却没有掌握，而且提醒了还不知道。”

—— 马凌洲（Autodesk，软件开发经理）

“最不能容忍功能错误，忽略边界情况。”

—— 尹彦（英特尔，软件工程师）

“如果一个程序员连变量、函数命名都毫无章法，解决一个具体问题都找不到一个最合适的数据结构，那么这会让面试官对他的印象大打折扣，因为这只能说明他程序写得太少，不够熟悉。”

—— 吴斌（英伟达，图形设计师）

“我会从程序的正确性和鲁棒性两方面检验代码的质量。会关注对输入参数的检查、处理错误和异常的方式、命名方式等。对于没有工作经验的学生，程序正确性之外的错误基本都能容忍，但经过提示后希望能够很快解决。对于有工作经验的人，不能容忍考虑不周到，有明显的鲁棒性错误。”

—— 田超（微软，SDE ||）

---

2 代码的规范性

面试官会根据应聘者写出的代码来决定是否录用他，如果应聘者代码写的不够规范，影响面试官阅读代码的兴致，那么面试官就会默默地减去几分。书写、布局和命名都决定着代码的规范性。

首先，清晰的规范的代码书写。写的慢一点也可以，把字母、数字、符号写清楚。

其次，清晰的规范的代码布局。缩进、对齐的一些布局格式要注意统一。

最后，合理的规范的代码命名。建议在写代码时，用完整的英文单词组合命名变量和函数。比如函数传入一个二叉树的根节点作为参数，则可以把该参数命名为BinaryTreeNode* pRoot，不用觉得这样多写字母会麻烦，如果一眼能看出变量、函数的用途，应聘者就能避免搞混淆而犯一些低级错误（除了循环量i,j,k这种，其他都要注意），同时合理的命名也能让面试官一眼读懂代码的意图。

---

3 代码的完整性

面试官会通过检查代码是否完整来考查应聘者的思维是否全面，一般会检查代码是否完成了基本功能、输入边界值是否能得到正确地输出、是否对各种不合规范的非法输入做出了合理的错误处理。

3.1 3个方面确保完整性

咕咕待更。

3.2 3种错误处理的方法

咕咕待更。

3.3 面试题 16-21

面试题16：数值的整数次方。

实现函数double Power(double base, int exponent)，求base的exponent次方，不得使用库函数，不需要考虑大数问题（只考虑结果在double的表达范围）。

完整实现代码：

#include <iostream>

bool g_invalid_input = false;
double eps = 1e-8;

double equal(double lhs, double rhs) {
    double big = (lhs > rhs)?lhs:rhs;
    double small = (big != lhs)?lhs:rhs;
    return (big - small) <= eps;
}

double power_with_unsigned_exp(double base, unsigned int exp) {
    // exp只为正数，内部只关心几次方的计算
    if(exp == 0) {
        return 1;
    } else if(exp == 1) {
        return base;
    } else {
        // 考虑用递归数学公式来加速幂计算
        // exp >> 1，int右移1位，等价于除以2向下取整，优化计算速度
        double result = power_with_unsigned_exp(base, exp >> 1);
        result *= result;
        if(exp & 0x1 == 1) {
            // 判断是否为奇数，这种方式比 % 2 == 0，速度更快
            result *= base;
        }
        return result;
    }
}

double power(double base, int exp) {
    // 考虑exp 为正、为负、为0的情况

    g_invalid_input = false; // 初始化全局变量
    if(equal(base, 0.0) && exp < 0) {
        g_invalid_input = true; // 也可以考虑其他错误处理方式
        return 0.0;
    }

    unsigned int abs_exp = (unsigned int)((exp < 0)?-exp:exp);

    double result = power_with_unsigned_exp(base, abs_exp);

    return (exp < 0)?(1.0 / result):(result);
}

int main() {
    std::cout << power(2, 4) << std::endl; // 16
    std::cout << power(10, 5) << std::endl; // 100000
    std::cout << power(13, -2) << std::endl; // 0.00591716
    std::cout << power(0, 0) << std::endl; // 1
    return 0;
}

---

面试题17：打印从1到最大的n位数。

输入数字n，按顺序打印出1到最大的n位十进制数。比如输入3，从1、2、3一直打印到最大的3位数999。

用字符串模拟大数加法进位的方式：

#include <iostream>
#include <cstring>

void print(char* number) {
    // 对于前面的空0，不再打印
    int len = strlen(number);
    bool begin = false;
    for(int i = 0; i < len; i++) {
        if(!begin && number[i] == '0') {
            continue;
        } else if(!begin && number[i] != '0') {
            begin = true;
        }
        printf("%c", number[i]);
    }
    printf("\n");
}

bool increment(char* number) {
    bool is_overflow = false;
    int carry = 0; // 进位量
    int len = strlen(number);
    // 模拟加法进位
    for(int i = len - 1; i >= 0; i--) {
        int sum = number[i] - '0' + carry;
        if(i == len - 1) {
            // 末位加1 increment
            sum++;
        }
        if(sum >= 10) {
            if(i == 0) {
                // 已经在最高位，进位就溢出了
                is_overflow = true;
            } else {
                carry = 1;
                sum -= 10;
                number[i] = '0' + sum;
            }
        } else {
            number[i] = '0' + sum;
            carry = 0;
            break;
        }
    }
    return is_overflow;
}

void print_1_to_n_max(int n) {
    if(n <= 0) {
        return;
    }

    char* number = new char[n + 1]; // 多一位给结尾符 \0
    memset(number, '0', n);
    number[n] = '\0';

    while(!increment(number)) {
        print(number);
    }

    delete[] number;
}

int main() {
    print_1_to_n_max(3);
    return 0;
}

还可以考虑用全排列的方式，就不用再考虑进位的问题，代码就简洁了很多：

#include <iostream>
#include <cstring>

void print(char* number) {
    // 对于前面的空0，不再打印
    int len = strlen(number);
    bool begin = false;
    for(int i = 0; i < len; i++) {
        if(!begin && number[i] == '0') {
            continue;
        } else if(!begin && number[i] != '0') {
            begin = true;
        }
        printf("%c", number[i]);
    }
    if(begin == true) {
        printf("\n"); // 修正部分，不打印全0的情况
    }
}

void print_1_to_n_max_rec(char* number, int len, int index) {
    if(index == len) {
        print(number);
        return;
    }
    for(int i = 0; i < 10; i++) {
        number[index] = i + '0';
        print_1_to_n_max_rec(number, len, index + 1);
    }
}

void print_1_to_n_max_permutation(int n) {
    if(n <= 0) {
        return;
    }
    char* number = new char[n + 1];
    memset(number, '0', n);
    number[n] = '\0';

    print_1_to_n_max_rec(number, n, 0);

    delete[] number;
}

int main() {
    print_1_to_n_max_permutation(3);
    return 0;
}

不过全排列的方法有一个容易忽略的漏洞，就算按照书上的代码运行，会出现一个多余的打印情况print("000")，这是因为这是全排列的起点，而想修改全排列的起点为001还稍微有点麻烦，这个时候你会发现其实print并不会把000打印出来，但是会多打印一个\n换行，所以只要简单修改一下print，让其只在非000的情况下才换行，这样看起来我们的输出起点就是1了。

---

面试题18：删除链表的节点。

题目一：在O(1)的时间内删除链表节点。

给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。链表节点与函数的定义如下：

struct node {
    int value;
    node* pnext;
};

void delete_node(node** phead, node* pdelete);

完整实现代码：

#include <iostream>

struct node {
    int value;
    node* pnext;
};

node* init_node(int value) {
    node* pnode = new node;
    pnode->value = value;
    pnode->pnext = nullptr;
    return pnode;
}

void insert_node(node** phead, node* pnode) {
    if(*phead == nullptr) {
        *phead = pnode;
        return;
    }
    node* temp = *phead;
    while(temp->pnext != nullptr) {
        temp = temp->pnext;
    }
    temp->pnext = pnode;
}

void delete_node(node** phead, node* pdelete) {
    if(!phead || !pdelete) {
        return;
    }
    if(pdelete->pnext != nullptr) {
        // 删除非尾节点，拷贝节点
        node* pnext = pdelete->pnext;
        pdelete->value = pnext->value;
        pdelete->pnext = pnext->pnext;
        // 删除节点
        delete pnext;
        pnext = nullptr;
    } else if(*phead == pdelete) {
        // 删除尾节点，并且链表只有一个节点
        delete pdelete;
        pdelete = nullptr;
        *phead = nullptr;
    } else {
        // 删除尾节点，只能从头找起
        node* pnode = *phead;
        while(pnode->pnext != pdelete) {
            pnode = pnode->pnext;
        }
        pnode->pnext = nullptr;
        delete pdelete;
        pdelete = nullptr;
    }
}

void print(node** phead) {
    if(*phead == nullptr) {
        return;
    }
    node* pnode = *phead;
    printf("%d ", pnode->value);
    while(pnode->pnext != nullptr) {
        pnode = pnode->pnext;
        printf("%d ", pnode->value);
    }
    printf("\n");
}

int main() {
    node** phead = new node*;
    *phead = nullptr;
    node** node_list = new node*[10];
    for(int i = 0; i < 10; i++) {
        node* new_node = init_node(i);
        node_list[i] = new_node;
        insert_node(phead, new_node);
    }
    print(phead); // 0 1 2 3 4 5 6 7 8 9
    // 删除头节点
    delete_node(phead, node_list[0]);
    // 删除尾节点
    delete_node(phead, node_list[9]);
    // 删除中间节点
    delete_node(phead, node_list[5]);
    print(phead); // 1 2 3 4 6 7 8
    return 0;
}

这段代码有三个需要讨论的地方：

1. 关于时间复杂度，如果是尾节点，则需要O(n)时间，如果是非尾节点，则需要O(1)时间，平均情况下[(n-1)*O(1) + O(n)]/n = O(1)，这也是书上说明的情况，但如果你真的要较真，你说：“我就是尾节点也想做到O(1)时间，可不可以？” 我说当然可以，再细想一下尾节点需要O(n)的原因，因为我们没有办法知道它的前一个节点是什么，那整个链表里面有没有什么地方是可以让我们保留一个额外的指针的地方呢？当然有，那就是尾节点没有利用起来的pnext，如果你将尾节点的pnext指向它的前一个节点，那自然删除也只需要O(1)时间了，当然这会影响到一些其他过程，例如判断达到尾节点的方式就和以往的pnode->pnext == nullptr不同了，但方法终归是可行的，尤其是如果面试官再进一步问是否还可以更优化时；
2. 上述代码仍然不是完美代码，主要是指的完整性上，因为它基于一个假设：要删除的节点的确在链表中，需要O(n)的时间才能判断链表中是否包含某一个节点（不借助其他数据结构情况下），受到题目的O(1)时间限制，所以这部分就没有再考虑了，可以和面试官进行说明；
3. 代码中用来删除节点的部分，用了一个保存节点的node_list数组，但这个数组中的节点情况并不会一直地和链表的节点情况保持一致，因为方法中涉及到了节点的拷贝，取决于删除的情况，数组i位置保存节点的value很有可能并不是i，也有可能链表中i值的节点还在，而node_list中i位置的指针已经被设置为nullptr。

题目二：删除链表中重复的节点。

在一个排序的链表中，如何删除重复的节点？

PS：这道题在书上的图3.4应该是打印出错了，初始链表的几个节点都没有打全，总之就是链表中重复的节只保留一个。另外，注意题目中的已排序条件。

struct node {
    int value;
    node* pnext;
};

void delete_duplication(node** phead);

完整实现代码：

#include <iostream>

struct node {
    int value;
    node* pnext;
};

node* init_node(int value) { ... }; // 和上面代码的相同
void insert_node(node** phead, node* pnode) { ... }; // 和上面代码的相同
void print(node** phead) { ... }; // 和上面代码的相同

void delete_duplication(node** phead) {
    if(phead == nullptr || *phead == nullptr) {
        return;
    }
    node* pprenode = nullptr;
    node* pnode = *phead;
    while(pnode != nullptr) {
        node* pnext = pnode->pnext;
        bool need_delete = false;
        if(pnext != nullptr && pnext->value == pnode->value) {
            need_delete = true;
        }
        pprenode = pnode; // 修改的代码
        if(!need_delete) {
            // pprenode = pnode; // 原代码
            pnode = pnode->pnext;
        } else {
            int value = pnode->value;
            node* ptobedel = pnext; // 修改的代码
            // node* ptobedel = pnode; // 原代码
            while(ptobedel != nullptr && ptobedel->value == value) {
                pnext = ptobedel->pnext;
                delete ptobedel;
                ptobedel = nullptr;
                ptobedel = pnext;
            }
            if(pprenode == nullptr) {
                *phead = pnext;
            } else {
                pprenode->pnext = pnext;
            }
            pnode = pnext;
        }
    }

}

int main() {
    node** phead = new node*;
    *phead = nullptr;
    for(int i = 0; i < 10; i++) {
        node* new_node = init_node(i / 2);
        insert_node(phead, new_node);
    }
    print(phead); // 0 0 1 1 2 2 3 3 4 4
    delete_duplication(phead);
    print(phead); // 0 1 2 3 4
    return 0;
}

init_node、insert_node以及print函数均和18题题目一的代码相同，不再赘述。

PS：需要说明的一点是，书上的delete_duplication代码和我这里所写的代码有细微差别，原因是对原题目的理解偏差问题，如果原题目所说的删除重复的节点不需要留下一个被重复的节点（即一个都不留），则看上面代码的原代码部分，如果是需要保留一个节点，就看修改后的部分。

---

面试题19：正则表达式匹配

题目：请实现一个函数用来匹配包含 . 和 * 的正则表达式。模式中的字符 . 表示任意一个字符，而 * 表示它前面的字符可以出现任意次（含0次），匹配是指字符串的所有字符匹配整个模式，例如，字符串 "aaa" 与模式 a.a 和 ab*ac*a 匹配，但与 aa.a 和 ab*a 均不匹配。

遇到字符时，和模式串的对应字符进行比较：

• 如果是普通字符，则直接比较匹配，后移指针；
• 如果是 .，匹配任意字符，后移指针；
• 如果发现字符的下一位是 *，就有两种情况了：
  • 如果是再匹配一次的情况，先检验是否匹配，如果匹配，则字符串指针后移，匹配串指针不后移；如果不匹配，则只能考虑将匹配串指针后移两位(跳过*)；
  • 如果是不再匹配一次的情况，匹配串指针后移两位（跳过*）；
  • 两种情况都要考虑到，所以需要用到递归来判断其中一个分支是否可行。

完整实现代码：

#include <iostream>

bool match_core(char* str, char* pattern) {
    printf("%c %c \n", *str, *pattern);
    if(*str == '\0' && *pattern == '\0') {
        return true;
    }
    if(*str != '\0' && *pattern == '\0') {
        return false;
    }
    if(*(pattern + 1) == '*') {
        if((*pattern == '.' && *str != '\0') || *str == *pattern) {
            return match_core(str + 1, pattern) || match_core(str, pattern + 2);
        } else {
            return match_core(str, pattern + 2);
        }
    } else if((*pattern == '.' && *str != '\0') || *str == *pattern) {
        return match_core(str + 1, pattern + 1);
    } else {
        return false;
    }

}

bool match(char* str, char* pattern) {
    if(str == nullptr || pattern == nullptr) {
        return false;
    }
    return match_core(str, pattern);
}

int main() {
    char str[100] = "aaa";
    char pattern[100] = "ab*ac*a";
    printf("Match? %s \n", match(str, pattern) ? "true" : "false");
    return 0;
}

上面代码中，需要注意的一个点是，对于匹配串的字符是.时，不能只是简单的只看匹配串，还要看被匹配串是否有字符可以匹配，所以不能只是简单地写为if(*pattern == '.' || ...)，应该写为if((*pattern == '.' && *str != '\0') || ...)，如果忽略这个细节，你不会在题目提供的几个输入输出上发现问题，但如果你多尝试其他的输入输出，尤其是当匹配串为.*(匹配任意字符)，你会发现结果是错误的。

---

面试题20：表示数值的字符串

实现一个函数用来判断字符串是否表示数值（包括整数和小数），例如字符串"+100"、"5e2"、"-123"、"3.1416"及"-1E-16"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。

表示数值的字符串遵循模式 A[.[B]][e|EC] 或者 .B[e|EC]，其中A为数值的整数部分，B紧跟小数点为数值的小数部分，C紧跟着e或者E为数值的指数部分。A和C都是可能以+或者-开头的0~9的数位串，B也是0~9的数位串，但前面不能有正负号。

完整实现代码：

#include <iostream>

bool scan_unsigned_inter(const char** str) {
    const char* before = *str;
    while(**str != '\0' && **str >= '0' && **str <= '9') {
        (*str)++;
    }
    return *str > before;
}

bool scan_integer(const char** str) {
    if(**str == '+' || **str == '-') {
        (*str)++;
    }
    return scan_unsigned_inter(str);
}

bool is_numberic(const char* str) {
    if(str == nullptr) {
        return false;
    }
    // A[.[B]][e|EC] 或者 .B[e|EC]

    // 检查A部分
    bool a_is_numeric = scan_integer(&str);

    bool b_is_numeric = true;
    // 如果碰到小数点，检查B部分
    if(*str == '.') {
        str++;
        b_is_numeric = scan_unsigned_inter(&str);
    }

    bool c_is_numeric = true;
    // 如果碰到e或E，检查C部分
    if(*str == 'e' || *str == 'E') {
        str++;
        c_is_numeric = scan_integer(&str);
    }

    bool all_scan = (*str == '\0');

    // (A || B) && C && End
    return (a_is_numeric || b_is_numeric) && c_is_numeric && all_scan;
}

void print_is_numberic(const char* str) {
    printf("%s %s\n", str, is_numberic(str)?"yes":"no");
}

int main() {
    print_is_numberic("+100"); // +100 yes
    print_is_numberic("5e2"); // 5e2 yes
    print_is_numberic("-123"); // -123 yes
    print_is_numberic("3.1416"); // 3.1416 yes
    print_is_numberic("-1E-16"); // -1E-16 yes
    print_is_numberic("12e"); // 12e no
    print_is_numberic("1a3.14"); // 1a3.14 no
    print_is_numberic("1.2.3"); // 1.2.3 no
    print_is_numberic("+-5"); // +-5 no
    print_is_numberic("12e+5.4"); // 12e+5.4 no
    return 0;
}

上面代码中需要注意的一个点是，书上原代码中是把各部分判断拆开计算逻辑合并的，但是我为了更加直观地写出其中逻辑思路，将各部分的判断都留到了最后，最后我们如果稍微一疏忽，容易就写成A || B && C && End，在C++中，逻辑运算符的结合反向是从左到右的，所以有可能你会把这种写法理解成(A || B) && C && End，但是，逻辑运算符之间的优先级顺序是，! > && > ||，这会导致计算结果等价于A || (B && C && End)，即只要A==true就会判定为数字，这当然不正确的，所以要得到正确的结果，应该显式的写为(A || B) && C && End，避免计算错误。

---

面试题21：调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

针对这道题的最优解法，在数组头尾设置两个指针，依次开始向中间扫描，如果左指针遇到偶数则停下，右指针遇到奇数则停下，然后交换两个指针指向的内容，直到两个指针相遇，算法停止，最后结果满足题目要求。

完整实现代码：

#include <iostream>

void reorder_odd_even(int* array, unsigned int len) {
    if(array == nullptr || len == 0) {
        return;
    }

    int* pleft = array;
    int* pright = array + len - 1;

    while(pleft < pright) {
        // 左指针遇到偶数停
        while(pleft < pright && (*pleft & 0x1) != 0) {
            pleft++;
        }

        // 右指针遇到奇数停
        while(pleft < pright && (*pright & 0x1) == 0) {
            pright--;
        }

        int temp = *pleft;
        *pleft = *pright;
        *pright = temp;
    }
}

int main() {
    int array[10] = {0, 2, 9, 1, 6, 5, 8, 7, 3, 4};
    reorder_odd_even(array, 10);
    for(int i = 0; i < 10; i++) {
        printf("%d ", array[i]);
    }
    // 3 7 9 1 5 6 8 2 0 4
    return 0;
}

可扩展的解法，不固定其中的判别逻辑，可以将任意两类定义的数据进行这样的前后分离：

#include <iostream>

// 这里用到的是一个函数指针，将一个函数传给另一个函数内部使用
void reorder(int* array, unsigned int len, bool (*func)(int)) {
    if(array == nullptr || len == 0) {
        return;
    }

    int* pleft = array;
    int* pright = array + len - 1;

    while(pleft < pright) {
        // 左指针遇到偶数停
        while(pleft < pright && !func(*pleft)) {
            pleft++;
        }

        // 右指针遇到奇数停
        while(pleft < pright && func(*pright)) {
            pright--;
        }

        int temp = *pleft;
        *pleft = *pright;
        *pright = temp;
    }
}

bool is_even(int n) {
    return (n & 0x1) == 0;
}

bool is_odd(int n) {
    return (n & 0x1) != 0;
}

int main() {
    int array[10] = {0, 2, 9, 1, 6, 5, 8, 7, 3, 4};
    reorder(array, 10, is_even);
    for(int i = 0; i < 10; i++) {
        printf("%d ", array[i]);
    }
    // 3 7 9 1 5 6 8 2 0 4
    printf("\n");
    reorder(array, 10, is_odd);
    for(int i = 0; i < 10; i++) {
        printf("%d ", array[i]);
    }
    // 4 0 2 8 6 5 1 9 7 3
    return 0;
}

---

4 代码的鲁棒性

请到《第3章笔记 高质量代码 P2》阅读这部分内容。