快慢指针

起

本页作为日常刷题时，对于算法的一点思考，不定期更新，定期维护。

中

快慢指针

在关于单链表是否有环的问题上，一般使用一个visited数组，可以较好的解决这个问题。但有一个更别致的方法可以解决这个问题——快慢指针法。

快慢指针的概念，源自于操场的跑圈，当一个跑步速度很快的人和一个速度较慢的人跑步，假设他们一直跑下去，那么很显然，他们会在一个地方再次相遇，类比到链表上来，也就是是否有环的问题。使用两个指针，每次在循环体内，慢指针只走一步：slow = listed[slow] 快指针走两步：fast = listed[listed[fast]] 这样当fast = slow 时，可以证明单链表有环。

1
2
3
4
5
6
7
8
9
10
11
12
13
boolean hasLoop(int nums[]){
  int slow=0,fast=0;
  boolean flag = false;
  while(fast==-1||nums[fast]==-1||nums[nums[fast]]==-1){
    slow = nums[slow];
    fast = nums[nums[fast]];
    if(slow == fast){
      flag = true;
      break;
    }
  }
  return flag;
}

神奇的异或操作

在学习逻辑的时候，就接触到异或^操作，但异或具有的一些性质很有意思。

例如：

1
2
3
4
5
6
0 ^ 1 = 1;
0 ^ 0 = 0;
1 ^ 1 = 0;
...
1 ^ 5 = 4;
4 ^ 5 = 1;

利用这一个性质，可以很方便的解决一些duplicate问题。

例如求出数组中的single number(only one)：

1
2
3
4
5
6
public int findSingle(int nums[]){
  int out = 0;
  for(int num : nums)
    out ^ num;
  return out;
}