网易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

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

大模型研发全揭秘:客服工单数据标注的完整攻略

在人工智能(AI)领域,数据标注是模型训练过程中至关重要的一步。无论你是新手还是有经验的从业者,掌握数据标注的技术细节和常见问题的解决方案都能为你的AI项目增添不少价值。在电信运营商的客服系统中,工单数据是客户问题和解决方案的重要记录。通过对这些工单数据进行有效标注,不仅能够帮助提升客服自动化系统的智能化水平,还能优化客户服务流程,提高客户满意度。本文将详细介绍如何在电信运营商客服工单的背景下进行

跨国公司撤出在华研发中心的启示:中国IT产业的挑战与机遇

近日,IBM中国宣布撤出在华的两大研发中心,这一决定在IT行业引发了广泛的讨论和关注。跨国公司在华研发中心的撤出,不仅对众多IT从业者的职业发展带来了直接的冲击,也引发了人们对全球化背景下中国IT产业竞争力和未来发展方向的深思。面对这一突如其来的变化,我们应如何看待跨国公司的决策?中国IT人才又该如何应对?中国IT产业将何去何从?本文将围绕这些问题展开探讨。 跨国公司撤出的背景与

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏,为了得到极品装备,xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感,但又不得不通过杀怪来升完这最后一级。现在的问题是,xhd升掉最后一级还需n的经验值,xhd还留有m的忍耐度,每杀一个怪xhd会得到相应的经验,并减掉相应的忍耐度。当忍耐度降到0或者0以下时,xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

【编程底层思考】垃圾收集机制,GC算法,垃圾收集器类型概述

Java的垃圾收集(Garbage Collection,GC)机制是Java语言的一大特色,它负责自动管理内存的回收,释放不再使用的对象所占用的内存。以下是对Java垃圾收集机制的详细介绍: 一、垃圾收集机制概述: 对象存活判断:垃圾收集器定期检查堆内存中的对象,判断哪些对象是“垃圾”,即不再被任何引用链直接或间接引用的对象。内存回收:将判断为垃圾的对象占用的内存进行回收,以便重新使用。

Go Playground 在线编程环境

For all examples in this and the next chapter, we will use Go Playground. Go Playground represents a web service that can run programs written in Go. It can be opened in a web browser using the follow