2020.2.28 字节跳动笔试
2.27号下午收到了实习生笔试（部门：效率工程EE）通知，临时准备了一下，了解了笔试的流程，看了看之前字节跳动的笔试真题，本来准备晚上做的，但是感觉题看得差不多了，就提前到了下午做，没想到直接凉凉。。。
看的过往的面试题都是以情景题居多，但这次90min两道题，没有任何情境，完全是数据结构硬上，最后一道都没有ac，还是挺沮丧的。所以认真把笔试面试的内容记录一下，慢慢积累经验吧。
第一题（无向无环图的直径）：给定节点数量和边，求直径。
输入数据：
1
9
1 2
2 3
3 4
2 5
4 6
5 7
8 5
8 9
输出：
6
最远的边为节点6和9，距离为6.
说明：输入数据第一行为测试用例的个数N；第二行为该测试用例中的节点数M；剩下的表示节点间有边。
因为自己在数据结构方面比较薄弱，没有复习到，所以看到题的时候很懵逼，一路做下来也很懵逼，想了各种数据结构都没找到最好的进行处理的结构,感觉最合适的是用矩阵，但是没有找到规律。
总结一下什么是无向无环图的直径：
在无向还通图中，最长的通路称作其直径（diameter)
在网上找了一圈这道题的解法，没有找到真正有用的，我感觉可能可以从邻接表或者图的广度优先搜索出发？先在这里给自己抛个砖，这段时间补一下图论的相关知识，找到解法之后再来更新。
***
第二题（二叉树的左视图）：以数组形式输入一个二叉树，求二叉树的左视图。
最开始不知道二叉树的左视图是什么意思，题目说明里边给了一个链接，还不能复制，傻乎乎地手写进地址栏，结果打不开。。。只好根据说明自己推理了一下，大概觉得就是输出二叉树每一行的第一个非空节点（广度优先）。
到网上找了一张图，左视图的直观解释就是：“从二叉树左边看这棵树，你能看到的结点”。和我之前理解的应该差不多。
输入：数组形式的二叉树，“#”表示空节点，如果只输入“#”的话，代表输入了一个根节点为空的树。
1 2 3 # # 4 6 # # # # # # # 8
输出：[1 2 4 8]
这道题最开始没有什么思路，因为不是典型的TreeNode形式的输入，而是直接给了数组，所以也没想到怎么从队列及广度优先去入手。看着数组想了半天，没辙，只好尝试用暴力法去解了：
因为所有的空节点都用“#”代替了，不存在二叉树上的空节点在数组中不表示出来的情况，所以可以按层次，以2的n次幂来做：
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String line = sc.nextLine();
if(line.equals("#")){
System.out.print("#");
return ;
}
String[] nodes = line.split(" ");
//存储结果
ArrayList<String> result = new ArrayList<>();
//遍历数组
for(int i = 0;i<nodes.length;i++){
//每一层在数组中的开始下标
int sum = 0;
//第i层的节点个数为2的i次方。
int pow = (int)Math.pow(2,i);
//遍历一层，找到第一个非空节点
for(int j = sum;j<sum+pow;j++){
if(!nodes[j].equals("#")){
result.add(nodes[j]);
break;
}
}
sum+=pow;
//当sum等于数组长度时，遍历完毕，跳出循环。
if(sum==nodes.length){
break;
}
}
for(String num:result){
System.out.print(num+" ");
}
}
但是不知道为什么，题目提供的测试案例和我自己写的测试案例都能够自测通过，但是提交之后一个case都没有通过。我在想是不是第一个case是处理根节点为空的情况，但是题目没有说明根节点为空这种情况下的输出，所以我输出空字符串和“#”都不能通过。不知道是不是我的代码的确是有问题的？
参考链接里边给了用两个队列去实现左视图的方法，这应该是比较常规的解法，但是要求的是树是比较传统的构造，这样才能实现从队列取出后，将子节点再加到另一个队列中去。
参考链接：https://blog.csdn.net/weixin_43019282/article/details/88729731