隨筆檔案

幾個面試題的小分析

面試題 100 - 20 最長公共子串
求兩個字符串的最長公共子串，不需要連續
根據當前的兩個字符 a[i] b[j]
m[i][j]
= max(m[i - 1][j], m[i][j - 1], m[i - 1][j - 1] + k)
if (a[i] = b[j]) k = 1
else k = 0

m[LenA][LenB]

記錄路徑，根據 max 去哪個值，記錄 m 矩陣的走勢，是向右、向下還是向右下
求路徑的時候，利用輔助矩陣 t[][] 記錄的走勢狀態，遞歸求出具體的最長公共子串。

面試題 100 - 30 異常安全的復制
一般函數指針成員的類對象，對 operator = 進行重載
在重載的函數體內，有可能造成重新分配內存失敗，造成了異常，原來的內存空間已經被釋放掉了，無法恢復之前的狀態。例如：
T& T::operator = (const T& rhs)
{
 if (this != &rhs)
 {
  delete [] pdata;
  pdata = new Type[];
  copy(...);
 }
 return *this;
}

這種情況下，可能 new 失敗造成異常，但是 pdate 指向的內存已經被釋放。

為了異常安全
采用臨時多一份的策略
第一種方法是，使用一個臨時指針，給這個指針分配塊內存，然后刪除原來的內存，將這個臨時指針賦值給本對象中的指針成員。
T& T::operator = (const T& rhs)
{
 if (this != &rhs)
 {
  Type * temp = new Type[];
  copy(...);
  delete [] pdata;
  pdata = temp;
 }
 return *this;
}

第二種方法也是用臨時多一份的策略，使用一個臨時本類型的對象，利用拷貝構造函數，然后交換臨時對象與本對象。
T& T::operator = (const T& rhs)
{
 if (this != &rhs)
 {
  T temp(rhs);
  swap(*this, temp);
 }
 return *this;
}

這里交換的是 *this 和 temp 的指針的值，而不是指針成員指向的內存內容，也就是說是做的對象的位交換。
這種有了一個臨時對象，可以不用做自賦值的檢測。即便是自賦值，也不會造成原數據的丟失。可以寫成：
T& T::operator = (const T& rhs)
{
 T temp(rhs);
 swap(*this, temp);
 return *this;
}

上面的第一種做法，也可以不做自賦值檢測。

最上面的非異常安全的做法是
1
0
1
當 0 過后，可能在產生 1 的時候異常，就無法恢復了。
臨時多一份的策略是
1
2
1
即便在產生 2 的過程中發生了異常，仍然有一個，所以是異常安全的。
兩個發生異常的階段分別是
0->1
1->2
關鍵要看異常前的情況，如果異常前就保證有效，則即使發生了異常也沒有問題，即是異常安全的。

http://www.shnenglu.com/jake1036/archive/2011/05/20/146689.html
http://www.shnenglu.com/jake1036/archive/2011/05/20/146816.html