变位词问题

排序算法相信对大家来说都不陌生，或许很多人已经把它们记得滚瓜烂熟，随时可以写出来。是的，这些都是最基本的算法。很惭愧我没有达到那种熟练程度，甚至都快忘了。最近把各种内部排序算法复习了一下，包括插入排序（直接插入排序，折半插入排序，希尔排序）、交换排序（冒泡排序，快速排序）、选择排序（简单选择排序，堆排序）、2-路归并排序。（另：堆排序原理说起来比较长，请看我的另一篇文章：堆排序的算法实现）

阅读全文 »

堆排序的算法实现

发表于 2014-04-02 | 分类于 Basic-算法与数据结构 |

由于堆排序算法说起来比较长，所以在这里单独讲一下。堆排序是一种树形选择排序方法，它的特点是：在排序过程中，将L[n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大（或最小）的元素。

堆的定义

堆的定义如下：n个关键字序列L[n]成为堆，当且仅当该序列满足：①L(i) <= L(2i)且L(i) <= L(2i+1) 或者 ②L(i) >= L(2i)且L(i) >= L(2i+1) 其中i属于[1, n/2]。

阅读全文 »

二叉树遍历序列的求解

发表于 2014-04-01 | 分类于 Basic-算法与数据结构 |

由遍历序列构造二叉树

阅读全文 »

观察者模式

发表于 2014-03-12 | 分类于 Basic-设计模式 |

观察者模式（Observer）：定义了对象之间的一对多关系，当一个对象改变状态时，它的所有依赖者都会收到通知并自动更新。

实现观察者模式的方法有多种，但是以包含Subject与Observer接口的类设计的做法最常见，下面看看观察者模式的类图：

阅读全文 »

C++中的单例模式

发表于 2014-03-11 | 分类于 Basic-设计模式 |

一、什么是单例模式

单例模式(Singleton Pattern，也称为单件模式)，使用最广泛的设计模式之一。其意图是保证一个类仅有一个实例，并提供一个访问它的全局访问点，该实例被所有程序模块共享。

定义一个单例类，私有化它的构造函数，以防止外界创建单例类的对象；使用类的私有静态指针变量指向类的唯一实例，并用一个公有的静态方法获取该实例。

二、懒汉版（Lazy Singleton）

教学版，即懒汉版（Lazy Singleton）：单例实例在第一次被使用时才进行初始化，这叫做延迟初始化。

// version 1.0
class Singleton
{
private:
	static Singleton* instance;
private:
	Singleton() {};
	~Singleton() {};
	Singleton(const Singleton&);
	Singleton& operator=(const Singleton&);
public:
	static Singleton* getInstance() {
		if(instance == NULL) {
			instance = new Singleton();
		}
		return instance;
	}
};

// init static member
Singleton* Singleton::instance = NULL;

Lazy Singleton存在内存泄露的问题，这里有两种解决方法：

使用智能指针
使用静态的嵌套类对象

对于第二种解决方法，代码如下：

// version 1.1
class Singleton
{
private:
	static Singleton* instance;
private:
	Singleton() { };
	~Singleton() { };
	Singleton(const Singleton&);
	Singleton& operator=(const Singleton&);
private:
	class Deletor {
	public:
		~Deletor() {
			if(Singleton::instance != NULL)
				delete Singleton::instance;
		}
	};
	static Deletor deletor;
public:
	static Singleton* getInstance() {
		if(instance == NULL) {
			instance = new Singleton();
		}
		return instance;
	}
};

// init static member
Singleton* Singleton::instance = NULL;

在程序运行结束时，系统会调用静态成员deletor的析构函数，该析构函数会删除单例的唯一实例。使用这种方法释放单例对象有以下特征：

在单例类内部定义专有的嵌套类。
在单例类内定义私有的专门用于释放的静态成员。
利用程序在结束时析构全局变量的特性，选择最终的释放时机。

注意version 1.0与version 1.1都不是线程安全的，要使其线程安全，可以使用双检测锁模式（Double-Checked Locking Pattern）：

static Singleton* getInstance() {
	if(instance == NULL) {
		Lock lock;  // 基于作用域的加锁，超出作用域，自动调用析构函数解锁
        if(instance == NULL) {
        	instance = new Singleton();
        }
	}
	return instance;
}

在单例类内再定义一个嵌套类，总是感觉很麻烦，所以《Effective C++》（Item 04）中的提出另一种更优雅的单例模式实现，使用函数内的 local static 对象。当第一次访问getInstance()方法时才创建实例：

// version 1.2
class Singleton
{
private:
	Singleton() { };
	~Singleton() { };
	Singleton(const Singleton&);
	Singleton& operator=(const Singleton&);
public:
	static Singleton& getInstance() {
		static Singleton instance;
		return instance;
	}
};

C++0X以后，要求编译器保证内部静态变量的线程安全性，故C++0x之后该实现是线程安全的，C++0x之前仍需加锁。

三、饿汉版（Eager Singleton）

饿汉版（Eager Singleton）：指单例实例在程序运行时被立即执行初始化

// version 1.3
class Singleton
{
private:
	static Singleton instance;
private:
	Singleton();
	~Singleton();
	Singleton(const Singleton&);
	Singleton& operator=(const Singleton&);
public:
	static Singleton& getInstance() {
		return instance;
	}
}

// initialize defaultly
Singleton Singleton::instance;

由于在main函数之前初始化，所以没有线程安全的问题。但是潜在问题在于no-local static对象（函数外的static对象）在不同编译单元中的初始化顺序是未定义的。如果在初始化完成之前调用 getInstance() 方法会返回一个未定义的实例。

总结：

Eager Singleton 虽然是线程安全的，但存在潜在问题；
Lazy Singleton通常需要加锁来保证线程安全，但局部静态变量版本在C++11后是线程安全的；
局部静态变量版本（Meyers Singleton）最优雅，面试时建议写这个版本。

参考：
[1] 单例模式的Java实现，请看CoolShell的《深入浅出Singleton设计模式》
[2] www.zkt.name/dan-li-mo-shi-singleton-ji-c-shi-xian