幾個(gè)面試題的小分析

面試題 100 - 20 最長(zhǎng)公共子串
求兩個(gè)字符串的最長(zhǎng)公共子串，不需要連續(xù)
根據(jù)當(dāng)前的兩個(gè)字符 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 去哪個(gè)值，記錄 m 矩陣的走勢(shì)，是向右、向下還是向右下
求路徑的時(shí)候，利用輔助矩陣 t[][] 記錄的走勢(shì)狀態(tài)，遞歸求出具體的最長(zhǎng)公共子串。

面試題 100 - 30 異常安全的復(fù)制
一般函數(shù)指針成員的類對(duì)象，對(duì) 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)被釋放。

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

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

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

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

最上面的非異常安全的做法是
1
0
1
當(dāng) 0 過后，可能在產(chǎn)生 1 的時(shí)候異常，就無法恢復(fù)了。
臨時(shí)多一份的策略是
1
2
1
即便在產(chǎn)生 2 的過程中發(fā)生了異常，仍然有一個(gè)，所以是異常安全的。
兩個(gè)發(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