字节跳动不讲武德，居然笔试的时候出这种题目……

大家好，我们今天继续字节跳动的笔试真题。

要说今天的题目，着实把我吓了一跳。它实在是太不按照常理出牌了，我还是第一次见过这样的题目，刚看到的时候觉得它有点不讲武德。但是仔细想想，这题的立意以及考点还是很不错的。用在笔试当中也非常合适，一样有区分度。

好了，我们废话不多说了，直接来看题吧。

题目链接：https://www.nowcoder.com/question/next?pid=8537283&qid=141064&tid=40455702

题意
给定一棵树的根节点, 在已知该树最大深度的情况下, 求节点数最多的那一层并返回具体的层数。

如果最后答案有多层, 输出最浅的那一层，树的深度不会超过100000。实现代码如下，请指出代码中的多处错误：

struct Node {    vector<Node*> sons;};void dfsFind(Node *node, int dep, int counter[]) {    counter[dep]++;    for(int i = 0; i < node.sons.size(); i++) {        dfsFind(node.sons[i], dep, counter);    }}int find(Node *root, int maxDep) {    int depCounter[100000];    dfsFind(root, 0, depCounter);    int max, maxDep;    for (int i = 1; i <= maxDep; i++) {        if (depCounter[i] > max) {            max = depCounter[i];            maxDep = i;        }    }    return maxDep;}

题解
怎么样，是不是有点没有想到？

为什么说这题出得好，就在这里。除了自己写代码debug之外，对于工程师而言，阅读并且理解其他人的代码和逻辑也非常重要。不仅如此，想要准确地找出代码当中的bug，也需要我们有丰富的编码经验。经验不足的话，一些隐藏比较深的问题是看不出来的。而且它只是给了我们代码，并没有给我们测试的环境以及数据，说白了所有的问题都需要我们通过肉眼发现，对于很多不习惯肉眼debug的同学来说还是有一定难度的。

所以这道题还是很考验同学们的水平的，真正有多少斤两，一下子就被试出来了。

结合这道题呢，我也会分享一些我个人的关于阅读代码的一些技巧和方法，希望可以帮助到大家。

整理逻辑
首先我们先来看这道题目，题意我们都很好理解，也就是计算树上每一层的元素个数，找到元素个数最多的那一层。那么很简单，我们把每一层的元素数量存储下来，最后遍历一下找到最大的。

整个题意和逻辑都算是比较清楚的，我们可以看到，题目给我们的代码一共包含两个函数以及一个结构体。结构体是定义的数据格式，和主体的运算逻辑关联不大，我们可以首先搞定。结构体当中只有一个Node指针的vector，这也是一个通过指针实现树的一个经典的写法。

struct Node {    vector<Node*> sons;};

排除了结构体的问题之后，我们接下来关注的重点就是两个函数了。

把握主次
我们剩下要搞定的两个函数分别是find函数以及dfsFind函数，简单略读一下代码就可以发现，这两个函数之间是存在一个调用的关系的。在find函数当中调用了dfsFind函数执行了递归，所以find函数就是dfsFind的上层。从逻辑上来说，dfsFind执行了是通过递归计算每一层元素个数的工作，而find函数则是通过遍历dfsFind得到的结果，最终进行返回。

所以这两个函数存在一个很明显的主次关系，当我们梳理出了代码的主次关系之后，不同的人有不同的习惯。有些人喜欢先细枝后主干，有些人喜欢先主干后细节。我个人比较倾向于后者，先阅读主干逻辑，再去细扣具体的实现细节。所以我们先把dfsFind放在一边，具体来看一下find函数当中的逻辑。

int find(Node *root, int maxDep) {    int depCounter[100000];    dfsFind(root, 0, depCounter);    int max, maxDep;    for (int i = 1; i <= maxDep; i++) {        if (depCounter[i] > max) {            max = depCounter[i];            maxDep = i;        }    }    return maxDep;}

这段代码也不长，一共只有几行，我们一行一行来看。第一行当中我们创建了一个depCounter的数组，数组的长度是1000000。看起来没有问题对吗，其实有一点问题。因为题目没有明说树深从1还是从0开始，如果从0开始，并且树深为1000000的话，需要1000001长度的数组才可以存储，我们这里创建了1000000会越界引发错误。

一般来说我们习惯申请数组的时候，额外多几个单位的长度可以防止极端情况下的越界。

第二行是一个递归调用，目前看起来没有问题，因为我们还没有具体查看递归函数内部的实现逻辑。第三行是声明了两个变量，变量的声明部分大家很容易一眼扫过，但其实变量声明的地方因此反而变得隐蔽，经常有bug很难发现。这里的变量声明就是错误的，这里声明了两个变量，两个变量都错了。

第一个是max是C++中的保留关键词，我们一般不用这种关键字为变量取名，第二个maxDep和find函数传入的参数maxDep重名了。这样是无法通过编译的，因为编译器无法区分两者。所以我们需要对这两个变量更换名字，比如一个更换成maxi，另外一个更换成maxIdx。

接下来是一个循环，通过循环找到数组中的最大元素的下标。这段逻辑非常简单，以至于很多人看不出来这里埋了雷。埋的雷在maxi上，maxi是在函数find当中创建的局部变量，在C++当中系统是不会为局部变量初始化的。所以这里的maxi被声明的时候到底默认值是多少是无法得知的。因为我们需要通过maxi找到最大值，所以我们一开始的时候需要为它初始化。

改完之后的代码应该是这样的：

int find(Node *root, int maxDep) {    int depCounter[100000];    dfsFind(root, 0, depCounter);    int maxi=0, maxIdx=0;    for (int i = 1; i <= maxDep; i++) {        if (depCounter[i] > maxi) {            maxi = depCounter[i];            maxIdx = i;        }    }    return maxDep;}

仔细谨慎
最后我们阅读一下dfsFind函数，这个函数也简单，只有三行，实现了一个递归统计的功能。很多人一样会匆匆一眼扫过去会发现好像没什么问题。但魔鬼都藏在细节里，越是看起来没问题的地方越可能有问题，一定要仔细谨慎，千万不可以想当然。

void dfsFind(Node *node, int dep, int counter[]) {    counter[dep]++;    for(int i = 0; i < node.sons.size(); i++) {        dfsFind(node.sons[i], dep, counter);    }}

这一段代码当中有两个问题，我先说其中比较明显的，这里比较明显的问题是我们递归的时候传入的不应该是dep而应该是dep+1。这里的dep表示树深，我们处理完当前深度的节点之后，再往下显然处理的应该是下一层节点，既然是下一层节点，那么它的深度显然应该需要+1。

第二个问题比较隐蔽，需要非常仔细才能发现，关于变量node。这里的node类型是Node的指针，对于指针类型的变量，我们是不可以通过.操作去访问它指向的结构体当中的成员变量的，想要访问只能通过->符号来访问，下面递归的时候的传参同样有这个问题。由于我们是眼睛来阅读代码，而不是编译器编译，所以很容易忽略这个细节。而且还有些同学可能对于C++的指针本身就不是很熟悉，这样一来就更难发现了。

最后，我们来贴一下所有找到的bug。

void dfsFind(Node *node, int dep, int counter[]) {    counter[dep]++;    for(int i = 0; i < node->sons.size(); i++) {   // node需要需要->符号        dfsFind(node->sons[i], dep+1, counter);    // node需要用->符号，dep+1替换dep    }}int find(Node *root, int maxDep) {    int depCounter[100005];  // 数组长度增加5    dfsFind(root, 0, depCounter);     int maxi = 0, maxIdx = 0; // 变量重新命名，并且初始化    for (int i = 1; i <= maxDep; i++) {        if (depCounter[i] > maxi) {            maxi = depCounter[i];            maxIdx = i;        }    }    return maxIdx;}

结尾
这一段短短的逻辑当中，我们一共找到了大大小小七八个bug。这些bug当中有些很明显，有些则相对隐蔽，想要全部找齐的确不是一件容易的事情，一不小心就遗漏了。

不仅是笔试做题，我们在日常的编码过程当中也是一样的，对于我们编写的代码一定要小心谨慎，抱有精益求精不断追求卓越的心思，才可以让写出来的代码质量越来越好。另外我们也要养成肉眼debug的习惯，不是所有情况下我们都可以有调试工具可以使用的，有的时候逼自己一把，不妨也是一种进步的途径。

今天的文章就到这里，衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话，请来一个三连支持吧~（点赞、在看、转发）

好知识，才能预见未来

赞赏

0人进行了赞赏支持

好知识，才能预见未来

更多相关文章

随机推荐