- 浏览: 53601 次
- 性别:
- 来自: 上海
最新评论
-
sebatinsky:
菜鸟从中飞过,,,。心慌慌。
某互联网公司面试题(二) -
marshaldong:
两层循环,如果内层循环的节点有等于外层循环的节点的,说明有环, ...
某互联网公司面试题(二) -
enefry:
支持hashMap说法.遍历是必须的.只是需要多余空间的支持. ...
某互联网公司面试题(二) -
fivestarwy:
Durian 写道这样的题没啥意义。
除非你喜欢信息奥林匹克竞 ...
某互联网公司面试题(二) -
antonia:
这些题目看着好难。。。。
某互联网公司面试题(二)
接上贴http://lgsun592.iteye.com/admin/blogs/1066179
,这也是其中的一道面试题
问题:一个链表可能包含环,如何检测并确定环的位置,如图:
方法有2:
1.记录法,通过某种方式把访问过的记录记录下来,然后访问下一个节点的时候查询下访问记录(我当时只想到了此方法,唉);
如果是外部标记的话,需要遍历1+2+...+(P+L-1)+P+(P+L)个节点,约O((max(P,L))^2),程序实现的就是此种方法
如果是内部标记的话,只需要遍历P+L个节点,速度最快的了
2.追赶法,类似在操场跑圈,两人同时起步,快的人和慢的人第一次相遇的时候,快的肯定比慢的多跑一圈,以此进行推算
第一次跑:两人同时从起点出发,第一个人P1速度为1,第二个人P2速度为2,相遇的时候P1跑的路程N=P+C,P2的路程=2N,可以推出此园的周长KL=P+C=N(K=1,2...)
第二次跑:P1的接上次位置,速度为1,P2从起点出发,速度为1,这次经过距离P后2人相遇,即在圆的起点相遇
推理: KL = P + C => KL - C = P
第二次相遇后,可以获得P的值,那么就可以确定此环形的起止位置了(程序实现的是K=1的情况)
废话不多说了,看代码吧
/** * Class @CircleLinklist.java * 环形链表检测 * @author lgsun * Date: 2011-6-2 */ package org.lgsun.linklist; import java.text.MessageFormat; import java.util.LinkedList; import java.util.List; import java.util.Random; @SuppressWarnings("all") public class CircleLinklist<E> { private static final int LENGTH = 16; private Entry<E> header; public static void main(String[] args) { CircleLinklist<String> circle = new CircleLinklist<String>(); circle.createLinkList(); circle.print(); circle.method1(); circle.method2(); } /** * 方法1 * 1.遍历链表 * 2.将访问过的节点的hashcode值保存起来 * 3.如果某节点的hashcode值已经存在,那么存在环 */ public void method1() { int start = -1; int curNum = 0; Entry<E> curEntry = header; List<Integer> codeList = new LinkedList<Integer>(); //遍历链表 while (curEntry.next != null) { if (codeList.size() == 0) { codeList.add(curEntry.hashCode()); } else { //如果存在,则包含环 if (codeList.contains(curEntry.hashCode())) { start = codeList.indexOf(curEntry.hashCode()); break; } } codeList.add(curEntry.hashCode()); curEntry = curEntry.next; curNum++; } if (start != -1) { System.out.println(MessageFormat.format( "方法1:此链表中包含环,从第{0}个节点到第{1}个节点。", start, curNum)); } else { System.out.println("方法1:此链表中不包含环!"); } } /** * 方法2 * 追赶法,数学啊,数学 */ public void method2() { int start = 0; int length = 0; boolean isCircle = false; Entry<E> firstEntry = header; Entry<E> secondEntry = header; //第一次,p1 速度为1,p2速度为2 while (secondEntry != null) { length++; if (length > 1) { // 直接比较内存地址 if (firstEntry == secondEntry) { isCircle = true; break; } } if (firstEntry.next != null) { firstEntry = firstEntry.next; } else { break; } if (secondEntry.next != null) { secondEntry = secondEntry.next.next; } else { break; } } if (isCircle) { secondEntry = header; //第二次,p1速度为1,p2速度为1 for (int i = 0; i < length; i++) { start++; // 直接比较内存地址 if (firstEntry == secondEntry) { // 从头到尾,交点总共算了3次,所以减2 length = length + start - 2; break; } if (firstEntry.next != null) { firstEntry = firstEntry.next; } else { break; } if (secondEntry.next != null) { secondEntry = secondEntry.next; } else { break; } } } else { System.out.println("方法2:此链表中不包含环!"); } System.out.println(MessageFormat.format( "方法2:此链表中包含环,从第{0}个节点到第{1}个节点。", start, length)); } /** * 向链表中增加节点 */ public void add(Entry<E> entry) { if (header == null) { header = entry; } else { entry.next = header; header = entry; } } /** * 创建一个带环的链表 */ public void createLinkList() { String disturb = "disturb"; Entry footer = null; Entry node = new Entry<String>("node"); Random random = new Random(); for (int i = 0; i < LENGTH; i++) { // 在长度1/2处加入指定节点 if (i == (LENGTH / 2)) { add(node); } else if (i == (LENGTH / 4) || i == (LENGTH * 3 / 4)) { // 加入干扰节点 add(new Entry(disturb)); } else { // 加入随机节点 String e = String.valueOf(random.nextInt(9999)); add(new Entry(e)); } // 获取尾节点 if (i == 0) { footer = header; } } // 给尾节点赋值为确定节点,产生环 footer.next = node; } /** * 输出此链表 */ public void print() { Entry<E> flag = header; System.out.print("header:"); for (int i = 1; i < LENGTH + 4; i++) { if (i != 0) { System.out.print("=>"); } System.out.print("["+i+"]"+flag.element.toString()); flag = flag.next; } System.out.println(); flag = header; } } class Entry<E> { E element; Entry<E> next; Entry(E element) { this.element = element; this.next = null; } }
不知道发此帖是对是错,发完上一帖已经有朋友M我说,他面试的时候也碰到的同样的题了,可见此公司的题库更新很慢吗
,希望大家早日找到自己喜欢的工作哦。
我是在洗澡的时候完成的此题的编码构思,所以一不小心和地板来了个亲密接触
参考资料:http://blogold.chinaunix.net/u1/41845/showart_2019391.html
评论
17 楼
sebatinsky
2011-06-08
菜鸟从中飞过,,,。心慌慌。
16 楼
marshaldong
2011-06-08
两层循环,如果内层循环的节点有等于外层循环的节点的,说明有环,后续分享代码:
似乎和找出一个List里两个值相同的元素的索引是一个解法,只不过这里是比较两个节点的相等(内存地址相同),再思考。
public class TestCircularList { static class Node<T> { T value; Node<T> next; Node(Node<T> next, T value) { this.value = value; this.next = next; } } public static Node<Integer> generateLinkList(int number) { Node<Integer> t = new Node<Integer>(null, 0); Node<Integer> temp = t; Node<Integer> temp1 = null; for (int i = 1; i < number; i++) { temp1 = new Node<Integer>(null, i % number); temp.next = temp1; temp = temp1; } temp.next = t.next.next.next;// construct circular linked list return t; } public static void main(String[] args) { Node<Integer> node = TestCircularList.generateLinkList(10); TestCircularList.traverse(node, 10); } /** * * @param <T> * @param node * the head node * @param length * the actural number of nodes of the linked list */ public static <T> void traverse(Node<T> node, int length) { Node<T> temp = node; Node<T> temp1 = null; while (temp != null) { temp1 = temp.next; int tailIndex = --length; while (temp1 != null && tailIndex != 0) { if (temp1 == temp) { System.out.println("has rings!"); System.out.println("Begin node value: " + temp.value); while (temp.next != temp1) { System.out.println(temp.next.value); temp = temp.next; } System.out.println("End node value: " + temp.value); return; } temp1 = temp1.next; tailIndex--; } temp = temp.next; } } }
似乎和找出一个List里两个值相同的元素的索引是一个解法,只不过这里是比较两个节点的相等(内存地址相同),再思考。
15 楼
enefry
2011-06-07
支持hashMap说法.遍历是必须的.只是需要多余空间的支持.
14 楼
fivestarwy
2011-06-07
Durian 写道
这样的题没啥意义。
除非你喜欢信息奥林匹克竞赛题。
除非你喜欢信息奥林匹克竞赛题。
普通的数据结构习题,信息奥林匹克不知道比这难多少倍
13 楼
antonia
2011-06-07
这些题目看着好难。。。。
12 楼
lance4t
2011-06-07
别去百度浪费大好青春。。。
11 楼
java_web
2011-06-07
唉
完全看不懂啊
学习学习啊
完全看不懂啊
学习学习啊
10 楼
wuzaizhong283
2011-06-07
这是百度的题
9 楼
dwbin
2011-06-07
我觉着还是别去吧,这样的所谓的算法题没市场的。
8 楼
Durian
2011-06-06
cttnbcj 写道
Durian 写道
这样的题没啥意义。
除非你喜欢信息奥林匹克竞赛题。
除非你喜欢信息奥林匹克竞赛题。
有些东西做不出来就进不去,那就搞不定了。。。。。
想进入好的公司真的需要做足功课。不过对于这些算法题,我不行,也不打算浪费青春去学。
7 楼
thihy
2011-06-06
avi2 写道
这是什么问题?,他们想要什么样的人?
HULU
6 楼
avi2
2011-06-06
这是什么问题?,他们想要什么样的人?
5 楼
cttnbcj
2011-06-06
Durian 写道
这样的题没啥意义。
除非你喜欢信息奥林匹克竞赛题。
除非你喜欢信息奥林匹克竞赛题。
有些东西做不出来就进不去,那就搞不定了。。。。。
4 楼
Durian
2011-06-06
这样的题没啥意义。
除非你喜欢信息奥林匹克竞赛题。
除非你喜欢信息奥林匹克竞赛题。
3 楼
wyp12
2011-06-06
遍历一次链表,没次遍历一个节点,对该节点取hash,然后保存在一个hashmap中,key为hash值,value为该节点的位置,可以用一个自增i变量表示,每次访问一个节点的时候,查询下hashmap中是否已存在该节点,存在,则说明出现了一个环
2 楼
小怪兽
2011-06-06
在校学生...表示压力巨大
1 楼
asst2003
2011-06-05
应该使用HashSet:遍历链表,在访问一个节点后,把这个节点放入HashSet中;在访问一个节点前先调用HashSet
的contains(Object node)方法来判断该节点是否已访问过,如果是,这个节点就是环的位置。
你的method1()使用了LinkedList的contains(Object node)方法。该方法会从头开始依次遍历链表来查找是否包含指定的节点,效率比较低。HashSet底层是通过包装了一个HashMap来实现的,它的contains(node)方法其实是调用HashMap的containsKey(Object node)来实现的,由于散列的缘故,这个查找的执行效率会很高。
的contains(Object node)方法来判断该节点是否已访问过,如果是,这个节点就是环的位置。
你的method1()使用了LinkedList的contains(Object node)方法。该方法会从头开始依次遍历链表来查找是否包含指定的节点,效率比较低。HashSet底层是通过包装了一个HashMap来实现的,它的contains(node)方法其实是调用HashMap的containsKey(Object node)来实现的,由于散列的缘故,这个查找的执行效率会很高。
发表评论
-
看到一段很有新意的java代码
2013-06-10 15:03 859问题: 现在有N多授权用户(id,name. ... -
Ubuntu环境下在Eclipse中安装jad反编译插件
2013-02-23 14:36 3745首先,还是到http://www.varaneckas.co ... -
Java调用JavaScript示例
2011-11-07 14:20 5128/** * ScriptTest * j ... -
JDK代码也不是完美的,垃圾四处可见
2011-10-13 16:53 0package java.nio; public abstr ... -
基于Eclipse的代码开发准备
2011-10-07 17:13 1427//这个代码框在可视化编辑器下无法删除,切换编辑器整篇文章格式 ... -
关于一段代码的疑惑
2011-09-28 13:50 847今天需要写一段关于输入字符串的check的代码,突然想到equ ... -
个人java基础总结
2011-06-12 21:55 932<!-- @page { margin: 2cm } ... -
一个简单的Structs2+Spring3+Hibernate3的例子
2011-04-07 23:43 2854留着以后学习用,嘿嘿 基本环境: Eclipse j2ee j ... -
关于getHibernateTemplate返回值为空的问题
2011-04-07 00:32 15csdn提问,需要将2个压缩包同时下载后放到同一目录方可解压缩 ... -
Junit测试备忘录
2011-03-28 21:14 935最简单的Junit4x sample, ... -
Java反射备忘录
2011-03-28 20:09 940在看spring的时候发现很 ... -
一个简单的Spring验证登录示例
2011-03-17 23:50 8782//*************************** ... -
将配置文件转化为utf-8的dos命令
2011-03-17 23:38 1312如果Eclipse 没有安装对应的插件,可以使用dos命令将配 ... -
SSH问题汇总1
2011-03-01 20:40 1444SSH遇到如下异常: Exception in thread ... -
spring学习笔记
2011-01-08 21:08 01.在config.xml中配置 <?xml ver ... -
log4j的配置示例
2011-01-08 17:48 793突然发现无论java还是.net关于log那部分都是人家做好了 ...
相关推荐
2020最新5G试题屏南某通讯服务公司面试试题(含答案).docx2020最新5G试题屏南某通讯服务公司面试试题(含答案).docx2020最新5G试题屏南某通讯服务公司面试试题(含答案).docx2020最新5G试题屏南某通讯服务公司面试试题...
出租车起步价14元,含3公里 起步价之后,每公里2.5元 晚上11点之后(含),次日6点前(不含)起步价18元,含3公里。计价以上车时间为准,不考虑乘坐期间从白天到晚上的情况。 晚上起步价之后,每公里3元 ...
2020最新5G基础大田某动通信有限公司二面试题(含答案).docx2020最新5G基础大田某动通信有限公司二面试题(含答案).docx2020最新5G基础大田某动通信有限公司二面试题(含答案).docx2020最新5G基础大田某动通信有限公司...
2020最新5G基础题库及答案——本溪市某动通信有限公司面试试题.docx2020最新5G基础题库及答案——本溪市某动通信有限公司面试试题.docx2020最新5G基础题库及答案——本溪市某动通信有限公司面试试题.docx2020最新5G...
MySQL面试题及答案,发现网上很多MySQL面试题及答案整理都没有答案,所以花了很长时间搜集,本套MySQL面试题大全,MySQL面试题大汇总,有大量经典的MySQL面试题以及答案,包含MySQL语言常见面试题、主要偏基础人士,...
ios开发面试题,精选题目,直面基础,可以看出来面试者的基础知识是否牢固
sql模拟面试题
本人发现网上虽然有不少Java相关的面试题,但是都没有针对性, 有些甚至没有答案,所以在本文档中,罗列了18题大厂基础Java岗位面试常见题型,并站在面试官的立场上,罗列出了答案,特别是应聘Java基础工程师的可以...
某互联网大厂开发岗面试题(一)
这是一些关于机器学习面试的一些问题的整理,虽然不是特别详细,但希望能帮助需要的人们,祝大家早日找到好的工作!
文档里有自己总结大大厂Redis常见面试题,自己凭借这套面试题拿下5-10个offer,目前已入职北京某互联网大厂,适合于正在找工作的同学。
文档里有自己总结大大厂Kafka常见面试题,自己凭借这套面试题拿下5-10个offer,目前已入职北京某互联网大厂,适合于正在找工作的同学。
文档里有自己总结的大厂HTTP常见面试题,自己凭借这套面试题拿下5-10个offer,目前已入职北京某互联网大厂,适合于正在找工作的同学。
。。。
。。。
文档里有自己总结大大厂Mysql常见面试题,自己凭借这套面试题拿下5-10个offer,目前已入职北京某互联网大厂,适合于正在找工作的同学。
JAVA面试题.doc 北京格尔.doc 晨阑数据.doc 东大金智.doc 互联网软件面试题.doc 花旗面试题目.doc 慧广面试题.doc 基础题收集.doc 金蝶面试题.doc 金蝶新.doc 金仕达多媒体.doc 晋恒软件.doc 隆达软件.doc 面试题1...
程序员在面试 Java 开发岗位时经常会遇上各类笔试面试题,针对这些笔试面试题做准备是必要的环节,在此过程中也能加深对 Java 知识的理解。 本面试试题均来自于网上。按照 Java 知识点的分类整理出试题,每道题都有...
文档里有自己总结计算机网络l常见面试题,自己凭借这套面试题拿下5-10个offer,目前已入职北京某互联网大厂,适合于正在找工作的同学。
文档里有自己总结了大厂JVM常见面试题,自己凭借这套面试题拿下5-10个offer,目前已入职北京某互联网大厂,适合于正在找工作的同学。