隨筆檔案

面試題分析小結(jié)-3

33 O(1) 刪除單鏈表中的節(jié)點(diǎn)

常規(guī)的方法是從 head 遍歷到待刪除節(jié)點(diǎn) p 的上一個(gè)節(jié)點(diǎn) q
q->next = p->next;
delete p;
遍歷到 p 的時(shí)間復(fù)雜度是 O(N)

既然知道了 p ，則就可以 O(1) 得到下一個(gè)節(jié)點(diǎn) t ，將 t 的值拷貝到 p 所指的節(jié)點(diǎn)，然后刪除 t 即可。
t = p->next;
p->data = t->data;
p->next = t->next;
delete t;
這樣時(shí)間復(fù)雜度是 O(1)

要考慮 p 是不是最后一個(gè)節(jié)點(diǎn)，但是最終不會(huì)影響 O(1) 的時(shí)間復(fù)雜度

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.shnenglu.com/jake1036/archive/2011/05/21/146879.html

34 找出數(shù)組中唯一出現(xiàn)一次的兩個(gè)數(shù)
如果一個(gè)數(shù)組中其他數(shù)都是出現(xiàn)偶數(shù)次，只有一個(gè)數(shù)出現(xiàn)奇數(shù)次，則可以直接對這個(gè)數(shù)組中的所有元素進(jìn)行異或運(yùn)算，最終的結(jié)果即是這個(gè)出現(xiàn)奇數(shù)次的數(shù)。
異或運(yùn)算的特性。

這里是有兩個(gè)數(shù)出現(xiàn)了一次，其他數(shù)都出現(xiàn)了兩次。
對整個(gè)數(shù)組進(jìn)行異或運(yùn)算，所得到的結(jié)果即是這兩個(gè)數(shù)的異或值 a ^ b = c

考慮 c
考慮 c 的某位為 1 的那位，比如考慮最低的那個(gè)為 1 的位
根據(jù)這個(gè)位，把原數(shù)組分成兩部門，即該位為 1 的集合和為 0 的集合，a 和 b 必然被分開，然后對這兩個(gè)集合分別做異或運(yùn)算，即可得到相應(yīng)的 a 和 b 。

異或運(yùn)算的特性：
a ^ (全 0) = a
a ^ (全 1) = ~a
a ^ a = 0
偶數(shù)個(gè) a 異或 = 0
奇數(shù)個(gè) a 異或 = a

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

35 找出兩個(gè)鏈表的第一個(gè)共同節(jié)點(diǎn)
這個(gè)題目也可以簡化為判斷兩個(gè)單鏈表是否交叉
1.
最直觀的解法是兩個(gè)循環(huán)，直接檢測，O(M * N)
2.
對每個(gè)節(jié)點(diǎn)的地址哈希 O(M + N)
3.
遍歷兩個(gè)鏈表，取得長度，然后再次遍歷，先遍歷長的那個(gè)鏈表，提前走 t 步，然后共同向后走，檢測第一次兩個(gè)節(jié)點(diǎn)地址是否一樣，如果一樣，則是那個(gè)共同節(jié)點(diǎn)。O(M + N)
4.
交叉的鏈表是 Y 型的，將其中一個(gè)鏈表 a 連到另一個(gè)鏈表 b 尾部，從 a 的 head 遍歷，如果再次回到了 a 的 head 即可判定 a 和 b 是交叉的。如果想找到交叉節(jié)點(diǎn)，則同時(shí)從 a 的 head 和 b 的 head 遍歷，直到 a 的 head 和 b 的 head 遇到一起時(shí)，這時(shí) a 的 head 也就是 b 的 head 即是指向的那個(gè)公共節(jié)點(diǎn)。

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

36 在字符串中刪除指定的字符
給定兩個(gè)字符串，刪除第一個(gè)字符串中在第二個(gè)字符串出現(xiàn)的字符
例如：
"abcefgh", "abcef"
得到：
"gh"

先對第二個(gè)字符串，做 hash 記錄要?jiǎng)h除的字符
然后遍歷第一個(gè)字符串，根據(jù) hash 表，判斷當(dāng)前字符是否是要?jiǎng)h除的那個(gè)字符
對第一個(gè)字符串的處理，可以利用一個(gè)指針和一個(gè)已刪除的字符數(shù)目記錄
也可以利用兩個(gè)指針，分別記錄當(dāng)前遍歷的字符和刪除后的字符串記錄

http://www.shnenglu.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