随笔档案

几个面试题的小分析

面试题 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.cppblog.com/jake1036/archive/2011/05/20/146689.html
http://www.cppblog.com/jake1036/archive/2011/05/20/146816.html