判断链表是否有环

题目描述

有一个单向链表,链表中有可能出现“环”,就像下图这样。
那么,如何用程序判断该链表是否为有环链表呢?
有环链表

题解

我们可以采用快慢指针的方法,创建两个指针p1和p2,让它们同时指向这个链表的头节点。然后开始一个大循环,在循环体中。让指针p1每次向后移动1个节点,让指针p2每次向后移动2个节点,然后比较两个指针指向的节点是否相同。如果相同,则可以判断出链表有环,如果不同,则继续下一次循环。

代码

有环链表
//判断是否有环
public static bool IsCycle(Node head)
{
Node p1 = head;
Node p2 = head;

while(p2 != null && p2.next != null)
{
p1 = p1.next;
p2 = p2.next.next;
if(p1 == p2)
return true;
}
return false;
}

//链表节点
private static class Node
{
int data;
Node next;
Node(int data)
{
this.data = data;
}
}
 

问题扩展

1. 求环长

当两个指针首次相遇,证明链表有环的时候,让两个指针从相遇点继续前进,并统计前进的循环次数,直到两个指针第二次相遇。此时,统计出来的前进次数就是环长。

2. 求入环点

入环点

上图是对有环链表所做的一个抽象示意图。假设从链表头节点到入环点的距离是D,从入环点到两个指针首次相遇点的距离是S1,从首次相遇点回到入环点的距离是S2 。
那么,当两个指针首次相遇时,各自所走的距离是多少呢?

指针p1一次只走1步,所走的距离是D+S1。
指针p2一次走2步,多走了n(n>=1)整圈,所走的距离是D+S1+n(S1+S1)。

由于p2的速度是p1的2倍,所以所走距离也是p1的2倍,因此:
2(D+S1 ) = D+S1 +n(S1 +S2 )

等式经过整理得出:
D = (n-1)(S1 +S2 )+S2

也就是说,从链表头结点到入环点的距离,等于从首次相遇点绕环n-1圈再回到入环点的距离。

这样一来,只要把其中一个指针放回到头节点位置,另一个指针保持在首次相遇点,两个指针都是每次向前走1步。那么,它们最终相遇的节点,就是入环节点。

最小栈的实现

题目描述

实现一个栈,该栈带有出栈(pop)、入栈(push)、取最小元素(getMin)3个方法。要保证这3个方法的时间复杂度都是O(1)。

题解

  1. 设原有的栈叫作栈A,此时创建一个额外的“备胎”栈B,用于辅助栈A。
  2. 当第1个元素进入栈A时,让新元素也进入栈B。这个唯一的元素是栈A的当前最小值。
  3. 之后,每当新元素进入栈A时,比较新元素和栈A当前最小值的大小,如果小于栈A当前最小值,则让新元素进入栈B,此时栈B的栈顶元素就是栈A当前最小值。
  4. 每当栈A有元素出栈时,如果出栈元素是栈A当前最小值,则让栈B的栈顶元素也出栈。此时栈B余下的栈顶元素所指向的,是栈A当中原本第2小的元素,代替刚才的出栈元素成为栈A的当前最小值。(备胎转正。)
  5. 当调用getMin方法时,返回栈B的栈顶所存储的值,这也是栈A的最小值。

2的整数次幂

判断 n & (n-1) == 0

栈实现队列

题解

使用两个栈,让一个栈作为队列的入口,负责插入新元素;另一个栈作为队列的出口,负责移除老元素。
即每次入队就是入栈A,出队时时出栈B,如果B为空,则栈A中的元素入B。

找到正整数全排列的下一个数

即找到这个整数组全排列中仅大于原数的新整数。

题解

我们先找到逆序区域的前一位数字,然后我们从低位开始找,找到大于这个数的最右边的一个数,交换,然后排列这个数交换之后的低位数。

获得全排列下一个数的3个步骤。

  1. 从后向前查看逆序区域,找到逆序区域的前一位,也就是数字置换的边界。
  2. 让逆序区域的前一位和逆序区域中大于它的最小的数字交换位置。
  3. 把原来的逆序区域转为顺序状态 。

删除K个数字后的最小值

题目描述
给出一个整数,从该整数中去掉k个数字,要求剩下的数字形成的新整数尽可能小。应该如何选取被去掉的数字?

题解

贪心算法,把原整数的所有数字从左到右进行比较,如果发现某一位数字大于它右面的数字,那么在删除该数字后,必然会使该数位的值降低 ,因为右面比它小的数字顶替了它的位置。

可以使用栈,有次数K,每次比较栈顶元素,若小于栈顶元素,则交换栈顶元素,否则入栈,每次K-1,直到K为0。

大整数相加

使用两个数组存储整数,将大整数拆分(可以直接计算即可),然后逆序放入数组,再将两个数组相加,注意进位。最后逆序输出结果数组。

寻找缺失整数

无序数组中有99个不重复正整数,范围是1100,唯独缺少一个1100中的整数,找出它。

思路
进行异或运算,最后得到的就是那个缺失的整数。

扩展
若有两个数字,可以采用分治法,可以先得出这两个数字的异或结果,找到结果中二进制哪一位是1,然后把原数组划分之后进行第二次异或。