隨筆檔案

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

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

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

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

要考慮 p 是不是最后一個節(jié)點，但是最終不會影響 O(1) 的時間復(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://m.shnenglu.com/jake1036/archive/2011/05/21/146879.html

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

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

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

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

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

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

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

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

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

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