随笔档案

面试题分析小结-3

33 O(1) 删除单链表中的节点

常规的方法是从 head 遍历到待删除节点 p 的上一个节点 q
q->next = p->next;
delete p;
遍历到 p 的时间复杂度是 O(N)

既然知道了 p ，则就可以 O(1) 得到下一个节点 t ，将 t 的值拷贝到 p 所指的节点，然后删除 t 即可。
t = p->next;
p->data = t->data;
p->next = t->next;
delete t;
这样时间复杂度是 O(1)

要考虑 p 是不是最后一个节点，但是最终不会影响 O(1) 的时间复杂度

void delete(node* p, node* head)
{
 if (p == 0 || head == 0)
 {
  return;
 }
 if (p->next != 0)
 {
  node* t = p->next;
  p->data = t->data;
  p->next = t->next;
  delete t;
  t = 0;
 }
 else
 {
  node * t = head;
  while (t->next != p)
  {
   t = t->next;
  }
  t->next = 0;
  delete p;
  p = 0;
 }
}

http://www.cppblog.com/jake1036/archive/2011/05/21/146879.html

34 找出数组中唯一出现一次的两个数
如果一个数组中其他数都是出现偶数次，只有一个数出现奇数次，则可以直接对这个数组中的所有元素进行异或运算，最终的结果即是这个出现奇数次的数。
异或运算的特性。

这里是有两个数出现了一次，其他数都出现了两次。
对整个数组进行异或运算，所得到的结果即是这两个数的异或值 a ^ b = c

考虑 c
考虑 c 的某位为 1 的那位，比如考虑最低的那个为 1 的位
根据这个位，把原数组分成两部门，即该位为 1 的集合和为 0 的集合，a 和 b 必然被分开，然后对这两个集合分别做异或运算，即可得到相应的 a 和 b 。

异或运算的特性：
a ^ (全 0) = a
a ^ (全 1) = ~a
a ^ a = 0
偶数个 a 异或 = 0
奇数个 a 异或 = a

http://www.cppblog.com/jake1036/archive/2011/05/21/146881.html

35 找出两个链表的第一个共同节点
这个题目也可以简化为判断两个单链表是否交叉
1.
最直观的解法是两个循环，直接检测，O(M * N)
2.
对每个节点的地址哈希 O(M + N)
3.
遍历两个链表，取得长度，然后再次遍历，先遍历长的那个链表，提前走 t 步，然后共同向后走，检测第一次两个节点地址是否一样，如果一样，则是那个共同节点。O(M + N)
4.
交叉的链表是 Y 型的，将其中一个链表 a 连到另一个链表 b 尾部，从 a 的 head 遍历，如果再次回到了 a 的 head 即可判定 a 和 b 是交叉的。如果想找到交叉节点，则同时从 a 的 head 和 b 的 head 遍历，直到 a 的 head 和 b 的 head 遇到一起时，这时 a 的 head 也就是 b 的 head 即是指向的那个公共节点。

http://www.cppblog.com/jake1036/archive/2011/05/22/146909.html

36 在字符串中删除指定的字符
给定两个字符串，删除第一个字符串中在第二个字符串出现的字符
例如：
"abcefgh", "abcef"
得到：
"gh"

先对第二个字符串，做 hash 记录要删除的字符
然后遍历第一个字符串，根据 hash 表，判断当前字符是否是要删除的那个字符
对第一个字符串的处理，可以利用一个指针和一个已删除的字符数目记录
也可以利用两个指针，分别记录当前遍历的字符和删除后的字符串记录

http://www.cppblog.com/jake1036/archive/2011/05/22/146944.html
http://baike.baidu.com/view/15482.htm
http://zh.wikipedia.org/wiki/ASCII
http://zh.wikipedia.org/wiki/File:ASCII_Code_Chart-Quick_ref_card.jpg