隨筆檔案

幾個面試題的小分析

面試題 100 - 20 最長公共子串
求兩個字符串的最長公共子串，不需要連續(xù)
根據(jù)當(dāng)前的兩個字符 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]

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

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

這種情況下，可能 new 失敗造成異常，但是 pdate 指向的內(nèi)存已經(jīng)被釋放。

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

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

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

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

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

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