华为OD机试

本人菜鸟一枚，不是科班出身，在西安一个小公司做java开发，工资很低，没有多少活，感觉学不到什么东西。boss直聘上有华为的人发消息，想试一试机试，5.13收到链接，5.15周六下午开始做了。

两道一星题：

1.停车问题

1,0,1,1,0,1,1,1表示停车位的情况，1表示有车，0表示空位，有三种车，分别占1,2,3个宽度的车位，求最少有几辆车，像上面这种情况，就是3辆车。

我是遍历一次，看连续有几个1，用1的个数除以3，累加到sum,如果有余数，sum++,感觉思路没有问题，不知道哪里不对，测试用例通过95.46%。

2.单词接龙

先给了k和n两个数字，表示接龙从第k个字符串开始，共有n个字符串，然后给了n个字符串，接龙就是后一个字符串的首字母和前一个字符串的尾字母要一样，如果有多个可以接上，选长度最长的，如果长度相同，按字典序，输出接好的字符串，每个字符串只能用一次。

这个我是用list存字符串，用过后从list中删除，每次把可以接上的也存到另一个list,我记作appendList,这个我用的是循环做的，stream api更方便，然后用Collections.sort排序，要自己写一个Comparator接口，

排在第一位的就是要接在后面的。这个一次就全部AC了。

一道二星题：

给了二叉树的中序和后序遍历，求层序遍历。输入CBEFDA CBAEDF，输出应该是ABDCEF

我前两道不到1小时就做完了，这道比前两道难一点，思路是用递归构建二叉树，然后用队列实现层序遍历。调试过程中脑子短路了，报错一直改不好，时间到了也没有做出来，200分没有了，很难受。休息了一会儿，重新调试，应该改好了

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while ((s=br.readLine())!=null){
            String[] str = s.split(" ");
            Node node = createTree(str[0],str[1]);
            Queue<Node> queue = new LinkedList<Node>();
            queue.offer(node);
            StringBuilder sb = new StringBuilder();
            while(!queue.isEmpty()){
                Node head = queue.poll();
                sb.append(head.ch);
                if(head.left!=null){
                    queue.offer(head.left);
                }
                if(head.right!=null){
                    queue.offer(head.right);
                }
            }
            System.out.println(sb);

        }
    }
    public static Node createTree(String a,String b){
        if(a==null){
            return null;
        }
        char ch = a.charAt(a.length()-1);
        Node root = new Node(ch);
        int i = 0;
        while(b.charAt(i)!=ch) {
            i++;
        }
        if(i-0>0){
            root.left = createTree(a.substring(0,i),b.substring(0,i));
        }else {
            root.left = null;
        }
        if(b.length()-1-i>0){
            root.right = createTree(a.substring(i,a.length()-1),b.substring(i+1));
        }else {
            root.right = null;
        }
        return root;
    }
    static class Node{
        char ch;
        Node left;
        Node right;
        Node(char ch){
            this.ch = ch;
        }
    }
}

#java工程师##笔经##华为#