而在一开始，就已经有朋友劝我，在简历中得弄点虚假和夸张，否则很难找到好的工作。可惜，本人对这种夸大优点，剔除一切不利信息的简历制作实在是难以为之！最终，想而易知，我所投出的简历所得到的回应是少得可怜。期间，我听说了一些通过在简历上的“美化”而取得求职成功的例子，也陆续的有几个朋友劝我在简历上不要太老实，得做些变通，如，“将中间的某两个公司的经历合写成一个公司的经历”、“某些内容可以不要写到简历上”、“某些内容应该再做些扩充，并对某些词替换成更吸引人点的词”等等。我也确有几次去尝试调整简历，可是，以到这弄虚假、夸张、隐瞒时，我却又实在是下不了手。没办法，或许这就是本性难移吧。

还好，回应总算还是有一些，而且目前也拿到了一份还算满意的Offer。在即将进入的新公司里，还是好好干吧！~

哎！~这可怕的求职市场啊，实在太令人心冷了！~

【补充条件】：

      树是普通的树，而且树中的结点没有指向父节点的指针。

针对上述的题目和条件，书中给出了如下解决方案。

【原方案】：

      使用两个链表，对树进行两次遍历以查找两个树结点，并保持路径到两个链表中，从而将问题转化为求两个链表的最后一个公共结点。

从该方案中，观察到两次树结点查找的遍历中，其中一个结点的遍历过的树结点序列将完全覆盖查找另一结点时所遍历的树结点序列。由此入手，本文提出了如下的改进解决方案。

【改进方案】：

    深度优先遍历树，并记录路径，当找到第一个结点后，在当前基础上继续遍历搜索第二个结点，并记录第一个结点路径的变化程度，直到找到第二个结点。最后，根据栈信息和记录的结点路径变化程度得到最低公共祖先。如图1，假设输入的两个树结点为D和K，树的根节点为R，则求D和K的最低公共结点的过程如下表： 

步骤	栈	第一个结点	第二个结点	路径变化程度
1	R	—	—	—
2	R，A	—	—	—
3	R，A，F	—	—	—
4	R，A，F，J	—	—	—
5	R，A，F，G	—	—	—
6	R，A，F，K	K	—	0（或K）
7	R，A，C	K	—	1（或A）
8	R，A，C，E	K	—	2（或A）
9	R，A，C，I	K	—	2（或A）
10	R，A，D	K	D	1（或A）
è 得出结果，最低公共祖先结点为A

从中，可以看到，改进后的方案，只需对树执行一次遍历。而在辅助空间的需求上， 只需使用一个栈（外加少量结点指针变量和1个表示路径变化程度的整型变量）。而且，如果采用递归的方式实现，该栈所需保存的信息，还可以通过递归时的函数调用栈得以保存。

【附注】：

1. 此处，有如下一个问题：
   假设待查找公共祖先的两树结点，其中一结点在以另一结点为根的子树上（包括两结点相同）时，公共祖先的确定规则——
   “作为子树根结点的那个结点”还是“子树根结点的父节点”？
   例如：对上面图1中的那棵树，如果待查结点为根结点R和结点F，那么最终的查找结果是为R呢，还是因为R是根结点无父结点而得出NULL？
   此问题在书中未提及，但查看书中代码，确认是选择了后者；而在本人的样例代码中则采用了前面的观点。
2. 在样例代码中，对树结点在栈中的存储方式略有改动。
3. 样例代码工程所使用的环境为 Visual C++ 2010；
   其中：tree.h/cpp为功能代码文件，TestLowestCommonAncestor.h/cpp为相应的UT代码文件；
   UT采用gtest所编写，编译链接请根据gtest在自己本机的路径状况修改gtest_link.props文件中相应的链接项。

但是，当我们准备写一个自己的 pow 时，我们又会怎么写呢？一般的，我们会写上一个 for 循环来循环幂的指数次，而且每次循环都会去执行一次浮点数的乘法操作。但是，当我们拿这个 pow 函数来跟系统 pow 函数作一运行比较时，就会发现，我们的 pow 实在是太低效了。那么怎么样才能使我们自己写的 pow 也能有系统函数那样的时间效率呢？

仔细分析，我们用的那个求幂值的循环过程，就能发现，其实我们还是做了很多不必要的浮点数乘法炒作。整个计算过程太过按步就班了。譬如说在计算 val（待传入pow 函数求幂的浮点数，下同） 的4次方，我们总是先计算出3次方的值，然后再根据3次方的值和原始值来求4次方的值；然而，我们其实本可以在计算出2次方值后，平方2次方值来得到4次方的值的。接下来，就是探索算法，以减少浮点数乘法的事了。

通过所学的指数函数的知识，我们知道指数函数有着这样的性质：

• V^(a+b) = V^a * V^b
• V^a*b = (V^a)^{b             ；这里 * 为乘法运算符}

另外，对于整数，有如下性质：

1.  2ⁿ = (1 << n)         ;这里 << 是向左移位的操作符。
2. C++中的任何一个正整数（负整数同，但须处理好符合位）都可以表示为以下形式：
   n = 2^a1 + 2^a2 + ... + 2^ak
   (其中，a1, a2, ... , ak 为闭区间 [0, 30] 上的整数值，且互不相同。)

由此，我们就可以事先依次计算出 val, val², val⁴, ... , val³⁰ 预存备用，然后再根据 val 相应 bit 上是 1 还是 0，来选取相应的预存数据进行相乘，从而得到最终的结果。当然，合理设计逻辑，还可以减少所需的预存数据。下面是我的Pow 代码，欢迎点评。

#define INTBITS_WITHOUT_SIGN 31 // the bit-size of type int with the sign bit being excluded.


bool IsZero(double val, double precision /**//*= DEFAULT_PRECISION*/)
{
    if (precision >= 0) {
        return (-precision <= val) && (val <= precision);
    } else {
        return (precision <= val) && (val <= -precision);
    }
}

double Pow(double val, int exponent)
{
    if (IsZero(val)) {
        return 0.0;
    }

    if (0 == exponent) {
        return 1.0;
    }

    bool bIsExponentMinus = false;
    if (exponent < 0) {
        exponent = -exponent;
        bIsExponentMinus = true;
    }

    double tempVal[INTBITS_WITHOUT_SIGN];
    memset(tempVal, 0, INTBITS_WITHOUT_SIGN);
    tempVal[0] = val;

    double result = 1.0;
    int index = 0;
    while (exponent != 0) {
        if ((exponent & 1) != 0) {
            result *= tempVal[index];
        }

        exponent >>= 1;
        if (exponent != 0) {
            tempVal[index + 1] = tempVal[index] * tempVal[index];
            ++index;
        }
    }

    if (bIsExponentMinus) {
        result = 1.0 / result;
    }

    return result;
}

 
【补充】：

1. 在指数中，0的负数次方和0的0次方，都是没有意义的，所以对“if (IsZero(val))”分支内的处理如果能加上一些异常的输出就更好了，如：

   在Widows下，可通过 SetLastError(...) 来设置错误码。

2. Pow中的 “double tempVal[INTBITS_WITHOUT_SIGN];” 一句，改写为

   double * pTempVal = new double[sizeof(int) * 8 - 1];

(当然，后面代码中的tempVal 也都要改为相应的 pTempVal，同时须记得在return 前把delete [] pTempVal)

就可以使代码也能够适应于64位系统的处理。对于无符号整数的为指数的情况，则辅助值空间应为“sizeof(unsigned int) * 8”，同时，无需再考虑负指数的情况。

(这里，很感谢春秋十二月的补充。)
 

我们知道，定义于函数内部的静态局部变量，有着

• 定义的实时性，即只在函数第一次被调用时才被定义
• 线程安全性
• 生命期直到程序结束

的特点。那么，通过这个局部静态变量来创建的单件又会是什么样呢？贴上我的Demo代码，这就来看看吧。

  1// Singleton demo_1: Singleton instance is a local static varible of class.
  2
  3#include <Windows.h>
  4#include <iostream>
  5
  6class A 
  7{
  8public:
  9    static A& GetInstance();
 10
 11private:
 12    A() : m_nStat1(-1), m_nStat2(-1) {
 13        m_nStat1 = 0;
 14        std::cout << "Construct A" << std::endl;
 15        m_nStat2 = 0;
 16    }
 17    A(const A&);
 18
 19public:
 20    ~A() {
 21        m_nStat1 = 0;
 22        std::cout << "Destruct A" << std::endl;
 23        m_nStat2 = 0;
 24    }
 25
 26    void Do() {
 27        ++m_nStat1;
 28        ++m_nStat2;
 29        std::cout << "Called Do() by object of A. [" 
 30                  << m_nStat1 << ", " 
 31                  << m_nStat2 << "]" 
 32                  << std::endl;
 33    }
 34
 35private:
 36    int m_nStat1;
 37    int m_nStat2;
 38};
 39
 40class B
 41{
 42public:
 43    B(int nID) : m_nID(nID) {
 44        std::cout << "Construct B: " << m_nID << std::endl;
 45        A::GetInstance().Do();
 46    }
 47    ~B() {
 48        std::cout << "Destruct B: " << m_nID << std::endl;
 49        A::GetInstance().Do();
 50    }
 51
 52private:
 53    int m_nID;
 54};
 55
 56class C
 57{
 58public:
 59    static C& GetInstance();
 60
 61private:
 62    C() : m_nStat(-1) {
 63        std::cout << "Construct C" << std::endl;
 64        m_nStat = 0;
 65    }
 66    C(const C&);
 67
 68public:
 69    ~C() {
 70        std::cout << "Destruct C" << std::endl;
 71        m_nStat = 0;
 72    }
 73
 74    void Do() {
 75        ++m_nStat;
 76        std::cout << "Called Do() by object of C. [" 
 77            << m_nStat << "]" 
 78            << std::endl;
 79    }
 80
 81private:
 82    int m_nStat;
 83};
 84
 85static B gs_B0(0);
 86B g_B1(1);
 87
 88A& A::GetInstance()
 89{
 90    static A s_instance;
 91    
 92    return s_instance;
 93}
 94
 95C& C::GetInstance()
 96{
 97    static C s_instance;
 98
 99    return s_instance;
100}
101
102static B gs_B2(2);
103B g_B3(3);
104
105int main(int argc, char * argv[])
106{
107    std::cout << "Enter main" << std::endl;
108    A::GetInstance().Do();
109    C::GetInstance().Do();
110
111    system("pause");
112    return 0;
113}
114

 接下来，自然就是执行结果：

哟吼~，这不正是自己想要的结果么，Perfect！！

构建简单，创建具有实时性（在且只在第一次用到时创建），线程安全，可以被全局变量的构造和析构正常调用，就是它了，极力推荐！O(∩_∩)O~

1. 何时释放通过new所创建的Singleton对象？
2. 如果不通过new、malloc等操作，是否能做到在第一次使用时才创建Singleton对象。

     在针对以上两个问题做了一番思考和尝试之后，终于有了成果。现呈现出来，供大家参考，也希望有更好妙招的朋友能不吝赐教。碍于连代码带文字，篇幅较长，所以我将分为四篇来讲。那么，开始咯！^_^

     一开始，我先拿使用静态成员变量的来实现的惰性单件来进行尝试，写了个Demo，一运行，O(∩_∩)O哈哈~，还真有意外的收获呢！嗯~，抓紧时间，先把我的Demo上来给大家瞧瞧！~

  1// Singleton demo_0: Singleton instance is a static member of class.
  2
  3#include <Windows.h>
  4#include <iostream>
  5
  6class A 
  7{
  8private:
  9    static A ms_instance;
 10
 11public:
 12    static A& GetInstance() {
 13        return ms_instance;
 14    }
 15
 16private:
 17    A() : m_nStat1(-1), m_nStat2(-1) {
 18        m_nStat1 = 0;
 19        std::cout << "Construct A" << std::endl;
 20        m_nStat2 = 0;
 21    }
 22    A(const A&);
 23
 24public:
 25    ~A() {
 26        m_nStat1 = 0;
 27        std::cout << "Destruct A" << std::endl;
 28        m_nStat2 = 0;
 29    }
 30
 31    void Do() {
 32        ++m_nStat1;
 33        ++m_nStat2;
 34        std::cout << "Called Do() by object of A. [" 
 35                  << m_nStat1 << ", " 
 36                  << m_nStat2 << "]" 
 37                  << std::endl;
 38    }
 39
 40private:
 41    int m_nStat1;
 42    int m_nStat2;
 43};
 44
 45class B
 46{
 47public:
 48    B(int nID) : m_nID(nID) {
 49        std::cout << "Construct B: " << m_nID << std::endl;
 50        A::GetInstance().Do();
 51    }
 52    ~B() {
 53        std::cout << "Destruct B: " << m_nID << std::endl;
 54        A::GetInstance().Do();
 55    }
 56
 57private:
 58    int m_nID;
 59};
 60
 61class C
 62{
 63private:
 64    static C ms_instance;
 65
 66public:
 67    static C& GetInstance() {
 68        return ms_instance;
 69    }
 70
 71private:
 72    C() : m_nStat(-1) {
 73        std::cout << "Construct C" << std::endl;
 74        m_nStat = 0;
 75    }
 76    C(const C&);
 77
 78public:
 79    ~C() {
 80        std::cout << "Destruct C" << std::endl;
 81        m_nStat = 0;
 82    }
 83
 84    void Do() {
 85        ++m_nStat;
 86        std::cout << "Called Do() by object of C. [" 
 87            << m_nStat << "]" 
 88            << std::endl;
 89    }
 90
 91private:
 92    int m_nStat;
 93};
 94
 95static B gs_B0(0);
 96B g_B1(1);
 97A A::ms_instance;
 98C C::ms_instance;
 99static B gs_B2(2);
100B g_B3(3);
101
102int main(int argc, char * argv[])
103{
104    std::cout << "Enter main" << std::endl;
105    A::GetInstance().Do();
106    C::GetInstance().Do();
107
108    system("pause");
109    return 0;
110}

为了能够分析得细致些，Demo写得长了点，见谅咯！~

    嗯，对了，还有运行结果：

仔细看看结果，有没觉得这结果很出乎意料啊？！！（顺便提下，我用的编译工具是Visual C++ 2010）

从这个运行结果，对通过静态成员实现的惰性单件，我得到了以下两点：

1. 对于定义在单件对象之前的全局或静态全局对象，虽然单件对象还是会在调用前及时构造，但构造函数内的初始化操作却可能在需要使用时还未能执行完全。
   如：std::cout 就会使得单件对象的构造函数调用被暂停（单件的其他操作还能继续调用），直到单件之前的全局或静态全局的构造函数全执行完了，才能继续执行。【*这个原因还请有知道的高手能赐教。】
2. 对于定义于单件对象之后的全局或静态全局对象，如果在析构中调用了单件，就会使得单件在释放后又被再次重新创建使用。当然，这时单件内所存的数据已跟之前毫无关联了。

因此，我要奉劝各位开发者，如果在你的全局或静态全局对象的构造或析构方法中调用某个单件，那么对该单件的实现就不要以静态成员来惰性地实现。