首页 > 华为OD机试
头像
牛客702857896号
发布于 2021-05-15 21:01
+ 关注

华为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;
        }
    }
}


全部评论

(11) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐