字节-Android开发面经(十)
共 3883字,需浏览 8分钟
·
2021-06-12 08:39
点击蓝字关注我们,获取更多面经
![](https://filescdn.proginn.com/e65bfd0c1dd761ee866fd09fd4cb2040/30815afd1454779844478e83f8171a07.webp)
![](https://filescdn.proginn.com/2198bce8b5af4bc38f177f0291077966/683e32b02f4d8dcc1926e34ee5709135.webp)
所谓对称,就是采用这种加密方法的双方使用方式用同样的密钥进行加密和解密。
非对称加密算法需要两个密钥:公开密钥(publickey:简称公钥)和私有密钥(privatekey:简称私钥)。公钥与私钥是一对,如果用公钥对数据进行加密,只有用对应的私钥才能解密。如果用公钥对数据进行加密,只有用对应的私钥才能解密。因为加密和解密使用的是两个不同的密钥
先通过公开密钥加密获取到对称密钥加密的密钥,再通过对称密钥加密传输数据。
HTTPS采用的是处理信息的方式是:结合对称加密+非对称加密这两种方式,我们可以用非对称加密的方式来传输对称加密过程中的密钥,之后我们就可以采取对称加密的方式来传输数据了。具体是这样子的:
服务器用明文的方式给客户端发送自己的公钥,客户端收到公钥之后,会生成一把密钥(对称加密用的),然后用服务器的公钥对这把密钥进行加密,之后再把密钥传输给服务器,服务器收到之后进行解密,最后服务器就可以安全得到这把密钥了,而客户端也有同样一把密钥,他们就可以进行对称加密了
![](https://filescdn.proginn.com/e65bfd0c1dd761ee866fd09fd4cb2040/30815afd1454779844478e83f8171a07.webp)
![](https://filescdn.proginn.com/2198bce8b5af4bc38f177f0291077966/683e32b02f4d8dcc1926e34ee5709135.webp)
思路:
链表分有环链表和无环链表,如果两个链表存在相交,则只有两种可能,两个链表都无环或者都有环。
(1)如果链表都无环,则先判断链表的尾指针是否一样,如果不一样,则没有相交。如果一样,则找出两个链表的长度差,将两个链表从距离尾节点同样的距离进行扫描,如果相交,则必然有一处扫描节点相同。实例数据List1:1->2->3->4->5->6->7->null,List2:0->9->8->6->7->null,第一个相交节点为6
(2)如果链表都有环,则只肯能有下面两种情况(如下图)。两种情况区分的方法为:入环点是否相同。
如果相同则为第一种情况:那么查找第一个相交点与无环的单链表相交找第一个交点的方法一样。
如果入环点不同,则为第二种情况,这个相交点或者为list1 的入环点loop1或者为list2的入环点loop2。
情况1实例数据(List1:1->2->3->4->5->6->7->4,List2:0->9->8->2->3->4->5->6->7->4,第一个交点为2)
情况2实例数据(List1:1->2->3->4->5->6->7->4,List2:0->9->8->6->7->4->5->6,第一个交点为4或6)
下面为实现代码
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
/*判断是否相交,如果相交,得到第一个相交点*/
public static Node getIntersectNode(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node loop1 = getLoopNode(head1);
Node loop2 = getLoopNode(head2);
if (loop1 == null && loop2 == null) {
return noLoop(head1, head2);
}
if (loop1 != null && loop2 != null) {
return bothLoop(head1, loop1, head2, loop2);
}
return null;
}
/*
* 判断是否存在环,如果存在,则找出环的入口点。
* 入口点找法:快慢指针,块指针走两步,满指针走一步,如果存在循环,则在慢指针走完环前,总会和快指针相遇。
* 从头指针和相遇点同时向后走,相遇的点必定是入口点。*/
public static Node getLoopNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
Node n1 = head.next; // n1 -> slow
Node n2 = head.next.next; // n2 -> fast
while (n1 != n2) {
if (n2.next == null || n2.next.next == null) {
return null;
}
n2 = n2.next.next;
n1 = n1.next;
}
n2 = head; // n2 -> walk again from head
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
return n1;
}
/*无环时的判断方法*/
public static Node noLoop(Node head1, Node head2) {
if (head1 == null || head2 == null) {
return null;
}
Node cur1 = head1;
Node cur2 = head2;
int n = 0;
while (cur1.next != null) {
n++;
cur1 = cur1.next;
}
while (cur2.next != null) {
n--;
cur2 = cur2.next;
}
if (cur1 != cur2) {
return null;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
}
/*有环时的判断方法*/
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
Node cur1 = null;
Node cur2 = null;
if (loop1 == loop2) {
cur1 = head1;
cur2 = head2;
int n = 0;
while (cur1 != loop1) {
n++;
cur1 = cur1.next;
}
while (cur2 != loop2) {
n--;
cur2 = cur2.next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} else {
cur1 = loop1.next;
while (cur1 != loop1) {
if (cur1 == loop2) {
return loop1;
}
cur1 = cur1.next;
}
return null;
}
更多面经
扫描二维码
获取更多面经
扶摇就业