网易2016研发工程师编程题--完全解析

2024-09-04 01:58

本文主要是介绍网易2016研发工程师编程题--完全解析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

之前做公司的真题,碰到动态规划,还有一些数学性质的题目比较多一点。网易2016研发工程师编程题跟之前做的题目有很大的不同,不仅涉及到二叉树的编码,还涉及到图的广度遍历,最后还有一个快排。可以说这次的三个题目含金量非常的高,因此做了一下总结和分析。


1.比较重量

题目描述:小明陪小红去看钻石,他们从一堆钻石中随机抽取两颗并比较她们的重量。这些钻石的重量各不相同。在他们们比较了一段时间后,它们看中了两颗钻石g1和g2。现在请你根据之前比较的信息判断这两颗钻石的哪颗更重。

给定两颗钻石的编号g1,g2,编号从1开始,同时给定关系数组vector,其中元素为一些二元组,第一个元素为一次比较中较重的钻石的编号,第二个元素为较轻的钻石的编号。最后给定之前的比较次数n。请返回这两颗钻石的关系,若g1更重返回1,g2更重返回-1,无法判断返回0。输入数据保证合法,不会有矛盾情况出现。
测试样例:
2 , 3,[ [1 , 2 ] , [ 2 , 4 ] , [ 1 , 3 ] , [ 4 , 3 ] ] , 4
返回: 1

题目分析

其实这个题目就是有向图的问题,如果 g1 比 g2大那么有向图中从g1到g2一定有一条路径,反之如果g2比g1大那么有向图中g2到g1一定有一条路径。样例中的有向图如下:

这里写图片描述
上图中2到3存在有向边因此 编号2 比 编号3 重。题目给出的二维数组构成一个图,如果要比较a b的大小,可以从a开始遍历其子节点,如果能够找到从a到b的通路就证明 a比b大。下面就可以用广度优先遍历,来求图中两个节点之间是否存在通路。

 public static int cmp(int g1, int g2, int[][] records, int n) {HashMap<Integer, ArrayList<Integer>> map=new HashMap<Integer, ArrayList<Integer>>();//hashmap中key对应的是节点值,value里面存放该节点的所有相邻连通子节点。这样便于广度遍历。for(int i=0;i<n;i++){//对于每一个头节点加入所有相邻连通子节点if(map.containsKey(records[i][0])){map.get(records[i][0]).add(records[i][1]);}else {ArrayList<Integer> list=new ArrayList<Integer>();list.add(records[i][1]);map.put(records[i][0], list);                }}if(judge(map, g1, g2)){return 1;//judge函数用于判断是否存在连通路径。}else if(judge(map, g2, g1)){return -1;}return 0;}public static boolean judge(HashMap<Integer, ArrayList<Integer>> map,int head,int next){Queue<Integer> queue=new LinkedList<Integer>();ArrayList<Integer> list=new ArrayList<Integer>();//list用于去重,遍历过的节点不再遍历。queue.add(head);//广度遍历while(!queue.isEmpty()){int val=queue.poll();if(val==next)return true;//如果next是head连通路径中的,则可知next<head list.add(val);ArrayList<Integer> list2=map.get(val);//将val的所有子节点加入到queue中,广度遍历。if(list2!=null)//此处null判断的原因是有的节点没有指向其他节点的有向边。              for(int i=0;i<list2.size();i++){if(!list.contains(list2.get(i))){queue.add(list2.get(i));}}}       return false;}

2.二叉树

题目描述:有一棵二叉树,树上每个点标有权值,权值各不相同,请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为1,一个节点经过多少条边到达另一个节点为这两个节点之间的距离。给定二叉树的根节点root,请返回所求距离。

题目分析

看到这个题目,最直观的的感受是先求出最大叶节点,和最小叶节点,再求出它们共同最近的祖先节点,但是最近的祖先节点不好求,因为节点的指针是单向的。因此这种方法不行。一个比较巧妙的方法是对二叉树节点进行编码,然后对编码进行处理,如下图:
这里写图片描述
如上图max叶节点的编码为:1 1 1 1 。min叶节点的编码为1 1 0 0。max节点和min节点的距离为:max编码的长度-2+min编码的长度-2;其中2为min编码和max编码前面重叠部分的长度。了解了思路代码就比较好写了。

public class Main_2 {static int max=Integer.MIN_VALUE,min=Integer.MAX_VALUE;static String maxcode;static String mincode;public static void main(String[] args) {}public int getDis(TreeNode root) {if(root==null)return 0;preorder(root, "", '0');int i=0;while(i<maxcode.length()&&i<mincode.length()&&maxcode.charAt(i)==mincode.charAt(i))++i;return maxcode.length()+mincode.length()-2*i;}public static void preorder(TreeNode root,String codes,char code){codes=codes+code;if(root==null)return;if(root.left==null&&root.right==null){if(max<root.val){max=root.val;maxcode=codes;}if(min>root.val){min=root.val;mincode=codes;}return;}preorder(root.left, codes, '0');preorder(root.right, codes, '1');}
}class TreeNode {int val = 0;TreeNode left = null;TreeNode right = null;public TreeNode(int val) {this.val = val;}
}

3寻找第k大的数

题目描述:有一个整数数组,请你根据快速排序的思路,找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间),请返回第K大的数,保证答案存在。
测试样例:

[ 1 , 3 , 5 , 2 2 ] , 5 , 3

返回: 2

题目分析

这个题目就是快排的思想,快速排序以某个数为基点,比其小的数放在其左边,比其大的数放在其右边,一趟排序完成后,如果这个数恰好放在第k个位置,则左边的k个数是最小的k个数。如果把比其大的数放在其左边,比其小的数放在其右边,一趟排序完后,如果这个数恰好放在第k个位置,则左边的k个数是最大的k个数。
关于快排可以看看这篇博客:http://blog.csdn.net/u013309870/article/details/68921848

package 网易2016研发工程师编程题;import java.util.Scanner;public class Main_3 {public static void main(String[] args) {Scanner sc=new Scanner(System.in);while(sc.hasNext()){int n=sc.nextInt();int k=sc.nextInt();int []a=new int[n];for(int i=0;i<n;i++)a[i]=sc.nextInt();findKth(a, n, k);}sc.close();}public static  void findKth(int[] a, int n, int K) {         System.out.println(findKth(a, 0, n, K));       }public static int findKth(int[] a, int left,int right, int K) {if(left>=right)return 0;int val=a[left];int i=left,j=right-1;while(i<j){while(i<j&&a[j]<val)j--;a[i]=a[j];while(i<j&&a[i]>=val)i++;a[j]=a[i];          }a[i]=val;if(i==K-1){return a[i];}return findKth(a, left,i, K)+findKth(a, i+1,right, K);}
}

总结

网易2016研发工程师编程题中的这三道题目的含金量还是比较高的,特别是前面两道题目的那种思维也是之前刷题的时候没有碰到的,对于这种解法比较新颖的题目,有必要完全弄懂,并做记录。

这篇关于网易2016研发工程师编程题--完全解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1134676

相关文章

Java的IO模型、Netty原理解析

《Java的IO模型、Netty原理解析》Java的I/O是以流的方式进行数据输入输出的,Java的类库涉及很多领域的IO内容:标准的输入输出,文件的操作、网络上的数据传输流、字符串流、对象流等,这篇... 目录1.什么是IO2.同步与异步、阻塞与非阻塞3.三种IO模型BIO(blocking I/O)NI

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

Spring MVC使用视图解析的问题解读

《SpringMVC使用视图解析的问题解读》:本文主要介绍SpringMVC使用视图解析的问题解读,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC使用视图解析1. 会使用视图解析的情况2. 不会使用视图解析的情况总结Spring MVC使用视图

利用Python和C++解析gltf文件的示例详解

《利用Python和C++解析gltf文件的示例详解》gltf,全称是GLTransmissionFormat,是一种开放的3D文件格式,Python和C++是两个非常强大的工具,下面我们就来看看如何... 目录什么是gltf文件选择语言的原因安装必要的库解析gltf文件的步骤1. 读取gltf文件2. 提

Linux find 命令完全指南及核心用法

《Linuxfind命令完全指南及核心用法》find是Linux系统最强大的文件搜索工具,支持嵌套遍历、条件筛选、执行动作,下面给大家介绍Linuxfind命令完全指南,感兴趣的朋友一起看看吧... 目录一、基础搜索模式1. 按文件名搜索(精确/模糊匹配)2. 排除指定目录/文件二、根据文件类型筛选三、时间

Java中的runnable 和 callable 区别解析

《Java中的runnable和callable区别解析》Runnable接口用于定义不需要返回结果的任务,而Callable接口可以返回结果并抛出异常,通常与Future结合使用,Runnab... 目录1. Runnable接口1.1 Runnable的定义1.2 Runnable的特点1.3 使用Ru

使用EasyExcel实现简单的Excel表格解析操作

《使用EasyExcel实现简单的Excel表格解析操作》:本文主要介绍如何使用EasyExcel完成简单的表格解析操作,同时实现了大量数据情况下数据的分次批量入库,并记录每条数据入库的状态,感兴... 目录前言固定模板及表数据格式的解析实现Excel模板内容对应的实体类实现AnalysisEventLis

Java的volatile和sychronized底层实现原理解析

《Java的volatile和sychronized底层实现原理解析》文章详细介绍了Java中的synchronized和volatile关键字的底层实现原理,包括字节码层面、JVM层面的实现细节,以... 目录1. 概览2. Synchronized2.1 字节码层面2.2 JVM层面2.2.1 ente