隨筆檔案

面試題分析小結-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.shnenglu.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.shnenglu.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.shnenglu.com/jake1036/archive/2011/05/22/146909.html

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

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

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