面试的滴滴研究院暑期实习生,岗位机器学习,二面除了电话面还要视频面试写代码,两个问题:
因为第二个之前有写过,所以没什么问题的过了;第一个其实也不难,但是有点紧张,最后面试官告诉我判断是否有环的函数写错了,哎。。。特此重新写下,mark之
package acmcoder;
class Node_t{
int value;
Node_t next;
public Node_t(int value, Node_t next) {
this.value = value;
this.next = next;
}
public Node_t() {
value = -999;
next = null;
}
@Override
public String toString() {
return "Node_t: value=" + value;
}
}
public class Test_didi {
private boolean hasLoop(Node_t head){
//使用快慢指针
Node_t p = head.next;
Node_t q = head.next;
boolean res = false;
while(q != null && q.next != null){
p = p.next;
q = q.next.next;
if(p == q){
res = true;
break;
}
}
return res;
}
private Node_t crashNode(Node_t head){
//假定一定有环
//使用快慢指针
Node_t p = head.next;
Node_t q = head.next;
while(q.next != null){
p = p.next;
q = q.next.next;
if(p == q){
break;
}
}
return p;
}
private Node_t findCircleStartNode(Node_t head){
boolean hasCircle = hasLoop(head);
if(!hasCircle){
return new Node_t();
}else{
//碰撞点到连接点的距离等于头指针到连接点的距离
Node_t crash = crashNode(head);
Node_t start = head.next;
while(start != crash){
start = start.next;
crash = crash.next;
}
return crash;
}
}
private int circleLen(Node_t head){
//找到碰撞点之后从碰撞点出发然后再次碰撞
Node_t crash = crashNode(head);
Node_t p = crash;
Node_t q = crash;
int len = 0;
while(q.next != null){
p = p.next;
q = q.next.next;
len++;
if(p == q){
break;
}
}
return len;
}
public static void main(String[] args) {
//建立单链表
Node_t node1 = new Node_t(1, null);
Node_t node2 = new Node_t(2, null);
Node_t node3 = new Node_t(3, null);
Node_t node4 = new Node_t(4, null);
Node_t node5 = new Node_t(5, null);
Node_t node6 = new Node_t(6, null);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node4;
//判断是否有环
Test_didi test = new Test_didi();
boolean hs = test.hasLoop(node1);
System.out.println("Has circle: " + hs);
//找出环的起点
Node_t circleStart = test.findCircleStartNode(node1);
System.out.println("Circle starts: " + circleStart.toString());
//计算环的长度
int len = test.circleLen(node1);
System.out.println("Circle length: " + len);
}
}
虽然面的不好, 好在还是拿到了offer, 侥幸