Contents
  1. 1. 异常安全
  2. 2. 线程安全
  3. 3. 链表
  4. 4. 二分算法
  5. 5. 位运算
  6. 6. 幂运算
  7. 7. 数字和字符串
  8. 8. 数组
  9. 9. 模拟题
  10. 10.
  11. 11.
  12. 12. 无厘头

工作比较空闲,趁机补(复)下(习)各种(其实是怕出去面试被秒杀啦)。

温馨建议: 内容较多,可以根据右侧导航阅读。

异常安全

实现异常安全的关键在于异常发生时关键逻辑的回退资源的正常回收(我的看法)。下面的栗子部分说明了这一点,看一个字符串cp的栗子:

// 添加赋值运算函数
class CMyString
{
public:
	CMyString(char* pData = NULL);
	CMyString(const CMyString& str);
	~CMyString();

	CMyString& operator = (const CMyString& str)
	{
		if (this == &str)
		{
			CMyString tmp(str);	 // exception safe
			std::swap(m_pData, tmp.m_pData);
		}
		return *this;
	}
	
	/*
	CMyString& operator = (const CMyString& str)
	{
		delete [] m_pData;
		m_pData = new char[strlen(str.m_pData)+1];
		strcpy(m_pData, str.m_pData);
		return *this;
	}
	*/
private:
	char* m_pData;
};

分析:

同样是4行代码,但第二种实现至少存在下面2个问题

  • 自己对自己赋值时,对一块已经释放掉的内存进行cp
  • 内存不足导致new失败时,没有保留原数据

我觉得要使得代码具有异常安全级别的强度,首先要非常清楚哪些操作可能导致异常(这边说的异常都是指软件异常),除了常规的非法内存访问、除零、栈溢出之类,就以各种系统资源申请最为常见。前面几种日常开发的时候就应该极力避免,而资源管理是相对容易被人忽视的地方。

因为很多时候出现异常都不是C++的标准异常,所以通常也没有机会进行自定义的异常处理,考虑到栈还是会正常unwind,所以思路只能是利用局部变量的自动销毁去解决,结合C++的RAII技术,是一项非常实用的实践方法。

但是具体实施的时候,因为谁都可能会偷懒,高速开发时究竟有多大意愿去坚持很大程度上取决于需要为此承担多少的工作量。为了降低成本,我们还是要预制一些工具来做的,关于这一方面,这篇博客有比较详细的讨论:http://mindhacks.cn/2012/08/27/modern-cpp-practices/

当然,前提还是需要我们比较清楚异常发生后的程序的走向的,不过这个算是一个比较基础的知识。

其实还有另外一种思路来解决这个问题——异常捕获

上面说的因为不是标准异常,对此我们好像也做不了什么,只能采取局部变量这种防御性措施。但这种思路实际上是在语言能力范围内进行考虑的,我们还可以利用一下操作系统的API

像我略有了解的Win和Linux都有提供一些捕获一些非标准异常的方法,比如说Win下有许多set_xx_handler的方法,Linux的信号处理函数等等,多看看系统API手册可能有不少新奇的功能可以挖掘出来。

虽然是不是一种跨平台方案,但是聊胜于无嘛,自用软件多数时候它也只在一个环境下工作。

异常发生后,操作系统又经过各种各样的处理,捕捉到的时候已经不在原来发送错误的那个栈上了,这时候我们没有context去处理问题,所以我们期望的是回到原来的地方做处理。

这时候longjump就能派上用场了,可以帮你回到“存档点”重新来过,这时候因为栈还没有被退掉(因为案发现场被控制,没有扩散出去,原栈还不知道这事情),我们就有足够的信息处理问题,该干啥干啥,就算不明真相至少也可以报一个Unknow Error,然后再创建一个标准异常往外扔。

为了实现这一点,除了要在进程启动后使用系统API进行异常处理函数设置之外,还需要“圈定”每个需要安全处理的区域,并且加入异常处理的代码。

具体的做法可以是在区域起始处创建jmp_buf并setjmp,同时加上if-else,在if区域执行,else区域处理异常,并把longjump的带回来的值作为区分条件,这些繁琐的事务我们可以通过宏来包装,使他看起来更符合TRY-CATCH的语意。

有时候我们也会想要做到TRY-CATCH之间嵌套TRY-CATCH,这种需求挺常见,比如对于游戏服务器来说,因为主要事务都是在处理网络消息,而消息和消息之间不一定有强的关联,希望处理一条消息出错时不要影响到别的消息处理,那么首先就会在处理的入口设置TRY-CATCH。然后对于后续具体的处理逻辑,我们可能正在开发一些不太容易做稳定的新功能,那么也会希望借助TRY-CATCH使得新功能尽量不要干扰整个系统运作。

显然setjmp并不理解这个事情,于是我们自然从嵌套结构想到了栈,利用栈结构保存jmp_buf,这样内层出了问题就可以拿到栈顶——内层的jmp_buf,而处理完之后才会轮到外层的jmp_buf。

这种方法也可以用来作为一种容错方案

回到上面栗子代码,未注释的实现重新创建了一个对象,堆内存的分配在其构造函数中进行,若申请失败,因为原数据还没进行处理,该赋值函数退出后在这一层就保障了资源的安全性。

线程安全

线程安全是继异常安全之后另一令人头痛的重大课题,“这两个安全”也是衡量代码是否具有工业强度的重要标准了。再看一个栗子:

// 方案1
class CSingletonClass
{
public:
	static CSingletonClass* Inst()
	{
		if (!m_pInst)
		{
			m_pInst = new CSingletonClass;
		}
		return m_pInst;
	}
	//...
private:
	static CSingletonClass* m_pInst;
};

// 方案2
class CSingletonClass
{
public:
	static CSingletonClass* Inst()
	{
		static CSingletonClass g;
		return &g;
	}
	//...
};

// 方案3:
class CSingletonClass
{
public:
	static CSingletonClass* Inst()
	{
		if (!m_pInst)
		{
			// section A
			MUTEX_LOCK(lock);
			if (!m_pInst)
			{
				// section B
				m_pInst = new CSingletonClass;
			}
			MUTEX_UNLOCK(lock);
		}
		return m_pInst;
	}
	//...
private:
	static volatile CSingletonClass* m_pInst;
};

Singleton我认为差不多是用的最多的设计模式了,实现起来虽然根据情况有几种不同的范式(也有为数不少怪异的实现),但归根结底没有本质的差别——都是用类来包装全局变量嘛。

但考虑多线程下的访问就麻烦的多,但不能不解决——像这样的需求还是很常见的,比如log、mempool、一些特殊的全局模块之类的,方案1显然不能做到这点。

可行的办法可以考虑直接进行静态变量的全局初始化,或者像方案2这种也不失为一种简洁取巧的处理方式。

重点说说方案3,如果在if判断之外加锁,每次访问Inst()都会进行锁定不免浪费,毕竟m_pInst大多数时间都不是空的。所以移到if里面去,但如果只是做到这一步,就又-掉-进-坑-里-了,不免又要叫人感叹道高一尺魔高一丈。

假设两个线程,线程A执行到 section A 处不幸被挂起,而线程B突破重围进入了section B,此时那个可疑的第二个 if 就派上用场了,没有它的话引起的问题可能不仅仅是内存泄漏哟~ 于是它有个时髦的名字“双检测锁定”

看起来貌似万无一失了,我们已经得到了一个“理论上无比正确”的Singleton,可惜故事并没有到此结束…

某些书中提到关于它是否能够真正的“正确”还得看编译器和CPU的脸色…它们这帮家伙有可能把你的代码以一种新的顺序组织起来(所谓的Code Arranger),而新的顺序未必有安全保障。

鉴于这些问题,苦逼的C++程序猴子们除了要会写代码,还得hold住编译器才行,至少要对一些优化选项有所了解不要乱来。另外,多线程访问的变量加上volatile不会少了你的好处的~

这样才算是基本(勉强)作出了一个靠谱的多线程Singleton了,当然只是保障这一层的访问,至于变量本身的操作就只能自己去保障啦。

关于Singleton的问题在《C++设计新思维》第六章有比较详细的讲解。

链表

看书的时候偶尔会留意到一些“老问题”的“新解法”(对我而言…)。

比如这段单链逆序打印元素的:

void ReversePrintList(ListNode* pHead)
{
	if (!pHead) return;
	ReversePrintList(pHead->next);
	cout << pHead->val << " ";
}

我以前没什么好想法,只想到先进行逆序操作,然后再打印。如果不允许修改链表呢?也许我就不知道怎么弄了。

但其实如果能联系到这本质上是个FILO的操作,应该能够想到栈的解法的,进而能够想到递归的解法的…

于是像原来写的很笨拙的单链表原地逆序的代码:

ListNode* ReverseList(ListNode* pHead)
{
	if (!pHead) return pHead;

	ListNode* pPre = NULL;
	ListNode* pCur = pHead;
	
	while (pCur)
	{
		ListNode* pNext = pCur->next;
		pCur->next = pPre;
		pPre = pCur;
		pCur = pNext;
	}

	return pPre;
}

现在可以像这样轻巧的解决:

ListNode* ReverseList_r(ListNode* pPre, ListNode* pAft)
{
	if (!pAft) return pPre;
	ListNode* pHead = ReverseList_r(pAft, pAft->next);
	pAft->next = pPre;
	return pHead;
}

//ReverseList_r(0, pHead);

链表的故事很多,总也讲不完,又如:

// O(1)时间删除单链表节点
void DeleteNode(ListNode** ppHead, ListNode* pToDelete)
{
	if (!ppHead || !*ppHead || !pToDelete)
	{
		return;
	}
	// 待删节点为末尾节点就只能遍历了
	if (!pToDelete->next)
	{
		ListNode* pNode = pHead;
		while (pNode->next != pToDelete && pNode != NULL) pNode = pNode->next;
		assert(pNode != NULL && "pToDelete is not in the list");
		delete pToDelete;
		pNode->next = pToDelete = NULL;
	}
	// 只有一个节点
	else if (*ppHead == pToDelete)
	{
		delete pToDelete;
		*ppHead = NULL;
		pToDelete = NULL:
	}
	else
	{
		// 复制下一个节点的值到当前节点,把下一个节点删掉。
		ListNode* pNext = pToDelete->next;
		pToDelete->val = pNext->val;
		pToDelete->next = pNext->next;
		delete pNext;
	}
}

前面是一大堆铺垫,真正的过程是最下面的else里,处理的非常漂亮,给思路点个赞。我以前都觉得“君要臣死 臣不得不死”,这段代码可说是彻底颠覆了这一世界观=。=,原来还可以找替罪羊啊…

还有个所谓的复杂链表复制的思路也十分巧妙:

// 所谓的复杂链表在这里就是每个链表有两个指针,一个到next,还有一个瞎JB指(链表内某个节点)的情况。

// 给出结构:
struct ComplexListNode
{
	ComplexListNode(int val, ComplexListNode* next, ComplexListNode* sibling)
		: val(val), next(next), sibling(sibling) { }
	int val;
	ComplexListNode* next;
	ComplexListNode* sibling;
};

ComplexListNode* Clone(ComplexListNode* pHead)
{
	if (!pHead)
	{
		return 0;
	}

	// 在原链表每个节点后面复制一个节点出来
	ComplexListNode* pCurNode = pHead;
	while (pCurNode)
	{
		ComplexListNode* pOriNext = pCurNode->next;
		pCurNode->next = new ComplexListNode(pCurNode->val, pCurNode->next, NULL);
		pCurNode->next->next = pOriNext;
		pCurNode = pOriNext;
	}

	// 拆分 & 重连
	pCurNode = pHead;
	ComplexListNode* pClonedHead = pHead->next;
	while (pCurNode)
	{
		ComplexListNode* pCloned = pCurNode->next;
		if (pCurNode->sibling != NULL)
		{
			pCurNode->sibling = pCurNode->sibling->next;
		}
		pCurNode->next = pCloned->next;
		pCloned->next = pCloned->next->next;
		pCurNode = pCurNode->next;
	}

	return pClonedHead;
}

传统思路来做这个很难有效率的完成,最多也就是新建节点的时候建个HashMap<原节点,新节点>了,这样新链表建完后再遍历一遍,把所有师妹指针(通过查表)都指到正确的小师妹身上=。=

再差的就是O(n*n)的粗糙解法了,不能比。

虽然链表写的有点多了,但是至少(被丢鞋子)…至少还有一点是不能不提的,runner技巧——助你成为CTO!(鸡蛋命中…>.<)

// 输出单链表倒数第k个节点
ListNode* GetLastK(ListNode* pHead, int k)
{
	if (k <= 0)
	{
		return NULL;
	}
	ListNode* pFirst, * pLast;
	pFirst = pLast = pHead;
	int t = k-1;
	while (t-- && pFirst->next)
	{
		pFirst = pFirst->next;
	}
	if (t != 0)
	{
		return NULL;
	}
	while (pFirst->next != NULL)
	{
		pFirst = pFirst->next;
		pLast = pLast->next;
	}
	return pLast;
}

所谓的runner就是在目标指针之前再添一个机油陪你一起跑,有时候他先跑n步,有时候你跑1步他就要跑2步…

这种方法能够助你解决包括求带环链表分叉点、交叉链表公共节点等一系列和节点位置有关的问题。

二分算法

二分算法有很多应用常见,常见的比如binary_search、merge_sort之类的,但我过去倒是从未想过拿来做一些“特殊”的工作,比如下面这题:

// 求递增数组旋转1次后的最小值(旋转就像是位的循环左(右)移)
int* BinSearch(int* input, int l, int r)
{
	if (l >= r)
	{
		return &input[0];
	}

	int mid = l + (r-l)/2;
	if (input[mid] < input[mid-1])
	{
		return &input[mid];
	}

	if (input[mid] >= input[0])
	{
		return BinSearch(input, mid+1, r);
	}
	else
	{
		return BinSearch(input, l, mid-1);
	}
}

int* FindMinNum(int* input, int len)
{
	if (!input || len <= 0)
	{
		return NULL;
	}
	// 坑点:注意这种情况二分算法无法正确给结果,只能线性
	if (input[0] == input[len-1] && input[0] == input[(len-1)/2])
	{
		return min_element(input, input+len);
	}
	return BinSearch(input, 0, len-1);
}

这个需求常规的二分算法虽然处理起来有困难,但是只要准确把握数字规律,还是可以尝试写个二分算法来做的,这题主要难度还是特殊情况容易考虑不全,但关于二分的运用还是受到一些启发。

类似的还有这个问题:给定有序数组和数字n,求n出现的次数。

// 给定有序数组和数字n,求n出现的次数。

int get_appear_cnt(int* arr, int len, int n)
{
	auto res_pair = equal_range(arr, arr+len, n);
	return distance(res_pair.first, res_pair.second);
}

娃哈哈,偷懒的感觉真棒!背书就这点好处!

实际上解题思路就是用二分搜索分别找到两个n的两个端点,即lower_bound和upper_bound做的事情,equal_range就是一下子做两件事情,一回事情。自己写也差不多这么个意思。

归并排序看名字感觉也就到此为止了,但是谁会知道其实改改也会有妙用呢!

// 找出数组中的逆序对总数(所谓逆序对,就是大的在前,小的在后的一对整数)

void merge_arr(int* arr, int left, int right, int& cnt)
{
	int c[1024];
	int mid = left + (right-left)/2;
	int i = mid;
	int j = right;
	int k = 0;
	
	// 将数组倒着合并,出现第一个数组元素大于第二个数组的当前元素,则它能和第二个数组所有左边的数形成逆序对。
	while (i >=left && j>=mid+1)
	{
		if (arr[i] > arr[j])
		{
			cnt += j-mid;
			c[k] = arr[j];
		}
		else
		{
			c[k] = arr[i];
		}
		--i,--j,++k;
	}
	while (i >= left) c[k++] = arr[i--];
	while (j >= mid+1) c[k++] = arr[j--];

	copy(c, c+k, arr+left);
}

void merge_sort(int* arr, int left, int right, int& cnt)
{
	if (left >= right)
	{
		return;
	}
	int mid = left + (right-left)/2;
	merge_sort(arr, left, mid, cnt);
	merge_sort(arr, mid+1, right, cnt);
	merge_arr(arr, left, right, cnt);
}

void get_reverse_pairs(int* arr, int len)
{
	int cnt = 0;
	merge_sort(arr, 0, len-1, cnt);
	cout << "cnt:" << cnt << endl;
}

这样一遍排序一遍就完成了逆序对的统计,相比O(n*n)的暴力解法,是个麻烦但很漂亮的思路。

位运算

程序猴子的一生大概总会遇到几个非要你做一些看起来无甚营养又感觉蛋疼的题,其中要求进行位运算的差不多占了半壁江山。

比如这题:

// 统计整数的二进制中1的个数

// 改进:为了避免负数问题的处理,改为每次对“1”进行左移,依次比较
int NumOf1(int n)
{
	int flag = 1;
	int cnt = 0;
	while(flag)
	{
		if (n & flag)
		{
			++cnt;
		}
		flag << 1;
	}
	return cnt;
}

// 改进:利用性质“ (n-1) & n 可以消除n最右一位的1”进行操作,统计消除多少次为0
int NumOf1_v2(int n)
{
	int cnt = 0;
	while (n)
	{
		n = (n-1) & n;
		++cnt;
	}
	return cnt;
}

一般人最容易想到的就是把原来的数左右移,然后每次比较最左或最右的位。但这忽略了一个移位运算的重要性质,写的时候容易出错:

正数右移向左补0,负数右移向左补1

于是如果实现的方法是右移并比较第一位的话,负数的时候是会死循环滴~

所以上面这两种实现是相对来说更加优秀的方法,尤其是第二种,独辟蹊径。

还有一个奇葩问题是这样(各种风骚的位计算技巧实在是令人倍感鸭梨):给定一个数组,有两个元素各只出现1次,其他所有元素出现2次,如何找出?

pair<int, int> get_once_num(int* arr, int len)
{
	// A ^ A == 0 你造哇?那么下面的结果就是 0 ^ 0 ^ 0 ^...a ^ ... b ... ^ 0 => a ^ b
	int resExecXOR = 0;
	for (int i=0; i<len; ++i)
	{
		resExecXOR ^= arr[i];
	}

	// 得到从右往左第一个1(鉴于a、b不相同,必然有个1)
	int bitflag = 1;
	while (true)
	{
		if (resExecXOR & bitflag) break;
		bitflag <<= 1;
	}
	
	// 用这个1进行分组,相同元素必然在相同组,a和b必然被棒打鸳鸯
	int resExecA = 0;
	int resExecB = 0;
	for (int i=0; i<len; ++i)
	{
		if (arr[i] & bitflag)
		{
			resExecA ^= arr[i];	// 各自再来 ^^^^ 寻找自我
		}
		else
		{
			resExecB ^= arr[i];
		}
	}

	return make_pair(resExecA, resExecB);
}

随便看看就好~

…………………….其实,还有更无聊的,一并奉上:

// 实现加法运算
int _Add(int a, int b)
{
	int sum, carry;
	do 
	{
		sum = a ^ b;
		carry = (a & b) << 1;
		a = sum;
		b = carry;
	} while (carry);
	return sum;
}

思路是,a+b时,考虑二进制加法过程,对于其中某一位有以下3种情况:1+0=1、1+1=0、0+0=0 和XOR的结果一致

而考虑二进制进位的情况时,只有1+1是存在进位的,即和AND的结果相同,鉴于进的是下一位,所以 a & b的结果左移就可以得到进位后的一个值。

二者相加得到和便是“+”的结果,但是要确保carry加完。

幂运算

幂运算当然就是pow(base, exponent)嘛,这没错,但是如果要求自己实现呢?

以前我觉得自古华山一条路,除了for exp,*=,*=,*=,*=…又能怎样呢?这里就有种“新思路”(其实是老方法了。。很久以前可能看过没在意)

double _Power_v2(double base, int exponent)
{
	assert(exponent > 0);
	if (exponent == 1)
	{
		return base;
	}
	double t = _Power_v2(base, exponent >> 1);
	return (exponent & 1) ? t*t*base : t*t;
}

思路就是,a^n => a^(n/2) * a^(n/2) (n is even)、a^(n/2) * a^(n/2) * a (n is odd)

利用递归,可以省去不少计算量。也许你会觉得剩的这点计算又被递归产生的开销填回去了,但是这是只是简单的整数幂,如果是别的呢?

数字和字符串

数字和字符串之间的关系就一句话——这就是爱,说也说不清楚~

给几个数字让你对其进行各种逆天的操作然后给出结果因为某种神秘原因,也成为了很常见的问题,比如下面这个:

// 输出1到最大的n位(十进制位)所有的整数。
void _Print(char* buf, int maxlen, int idx)
{
	if (idx == maxlen)
	{
		buf[maxlen] = 0;
		char* begin = buf;
		while(*begin == '0') ++begin;
		begin == buf+maxlen ? printf("0 ") : printf("%s ", begin);
		return;
	}
	
	for (int i=0; i<10; ++i)
	{
		buf[idx] = '0' + i;
		_Print(buf, maxlen, idx+1);
	}
}

由于n没给定范围,所以有可能出现大数这种“害群之马”来,临时写一组大数运算的代码是非常麻烦的事情,这个我想地球人应该要达成共识才对。为了避免做这种折寿的事情,这段代码巧妙的避开了数的处理,果断投奔字符串阵营了(好球..)。

关于数的排列组合的问题几乎没有不用递归来解的(没理由不递归,下了毒誓也不行),这题说来不难,但是可以说是比较经典,很多类似的问题都是像这种传一个字符串进去,对索引处进行修改来完成的。

对于字符串,也是类似,这里一个要求字符串全排列的问题:

void PrintAll(char* str, char* begin)
{
	if (!str || *str == 0)
	{
		return;
	}

	if (*begin == 0)
	{
		printf("%s ", str);
		return;
	}
	
	for (char* pch = begin; *pch != 0; ++pch)
	{
		iter_swap(pch, begin);
		PrintAll(str, begin+1);
		iter_swap(pch, begin);
	}
}

维护好每一层栈上的数据——也就可以了(感觉好欠揍的说法…)

数组

说实话我高中的时候万万是想不到大学里会这么反反复复的折腾数组,把啦么纯洁的数组弄的千奇百怪的,大学太可怕了!

// 求数组中出现次数超过总长度一半的数字

int GetMTHNum_2(int* arr, int len)
{
	assert(arr && len>0);
	int num = arr[0];
	int count = 1;
	for (int i=1; i<len; ++i)
	{
		if (arr[i] == num)
		{
			++count;
		}
		else
		{
			--count;
			if (!count)
			{
				num = arr[i];
				++count;
			}
		}
	}
	return num;
}

注意到我这里函数名又加了一个2,还有另一种解法,下面再说。

这种方法又是利用了数字间某种奇异的规律:从第一个数开始,遇到相同数则+1,不同则-1,为0时把数字换成当前的数,活到最后的一定是那个数量过半的数!

不明白为什么会有人发现这个事情…算了,管不了他了…我们说另一种解法..

== 有人提到了Partition?(对对,你猜的没错,就是快排御用的那个Partition)。

Partition非常适合用来解决最小K个数、第K个数是什么之类的问题(或nth_element),比如:

// 输入n个整数, 找出其中最小的k个数

void Nth_Elem(int* arr, int len, int k)
{
	assert(arr && len>0 && k>0 && k<=len);

	int idx = -1;
	int left = 0;
	int right = len-1;
	while (idx != k-1)
	{
		idx = Partition(arr, left, right);
		if (idx > k-1)
		{
			right = idx;
		}
		else if (idx < k-1)
		{
			left = idx;
		}
	}
}

// 附上Partition的其中一个版本(和维基百科上的差不多,《STL源码剖析》上的是另外一种):

int Partition(int* arr, int left, int right)
{
	int pivot = left + (right-left)/2;
	int pivot_val = arr[pivot];
	int store_idx = left;
	swap(arr[pivot], arr[right]);
	for (int i=left; i<right; ++i)
	{
		if (arr[i] < pivot_val)
		{
			swap(arr[i], arr[store_idx]);
			++store_idx;
		}
	}
	swap(arr[store_idx], arr[right]);
	return store_idx;
}

这样去做据说是O(n)的复杂度,但恕我不能直接而又犀利的看出来…

另外有一种也比较主流的O(nlogk)的二叉堆解法(据说比较适合海量数据),因为看的时候比较闲,所以被我封装成类了…

// 二叉堆
template <typename T, typename Pr>
class TBinHeap
{
public:
	TBinHeap(T* tarr, int size)
		: pr_(Pr())
	{
		heap_.reserve(size);
		copy(tarr, tarr+size, back_inserter(heap_));
		build_heap();
	}

	TBinHeap(const vector<T>& tvec)
		: heap_(tvec)
		, pr_(Pr())
	{
		build_heap();
	}

	void push(const T& elem)
	{
		heap_.push_back(elem);
		iter_swap(heap_.begin(), --heap_.end());
		heapify(0);
	}

	const T& top() const
	{
		assert(!heap_.empty());
		return heap_[0];
	}

	void pop()
	{
		assert(!heap_.empty());
		iter_swap(heap_.begin(), --heap_.end());
		heap_.erase(--heap_.end());
		heapify(0);
	}

	void print() const
	{
		copy(heap_.begin(), heap_.end(), ostream_iterator<T>(cout, " "));
		cout << endl;
	}

	int size() const				{ return heap_.size(); }
	bool empty() const				{ return heap_.empty(); }
private:
	// 建堆,从最后一个根节点开始
	void build_heap()
	{
		for (int i=father(size()-1); i>=0; --i)
		{
			heapify(i);
		}
	}
	
	// 堆调整(从根往下)
	void heapify(int i)
	{
		if (empty())
		{
			return;
		}
		int l = left_child(i);
		int r = right_child(i);
		int sz = size();
		int largest = (l < sz && pr_(heap_[l], heap_[i])) ? l : i;
		largest = (r < sz && pr_(heap_[r], heap_[largest])) ? r : largest;
		if (largest != i)
		{
			swap(heap_[i], heap_[largest]);
			heapify(largest);
		}
	}

	// 数组状二叉堆的节点位置关系
	int father(int i) const			{ return (i-1)/2; }
	int left_child(int i) const		{ return i*2+1; }
	int right_child(int i) const	{ return i*2+2; }
private:
	vector<T>	heap_;
	Pr			pr_;
};

// 解决问题
void Nth_Elem_v2(int* arr, int len, int k)
{
	assert(arr && len>0 && k>0 && k<=len);

	TBinHeap<int, greater<int> > heap(arr, k);
	// 建最大堆,后面数据只要比根节点小就丢进去,最后留在堆里的K个元素一定是最小的k个。
	for (int i=k; i<len; ++i)
	{
		if (arr[i] < heap.top())
		{
			heap.pop();
			heap.push(arr[i]);
		}
	}
	heap.print();
}

其实偷偷懒,就STL就可以啦!

void Nth_Elem_v3(int* arr, int len, int k)
{
	multiset<int, greater<int> > s(arr, arr+k);
	for (int i=k; i<len; ++i)
	{
		if (arr[i] < *s.begin())
		{
			s.erase(s.begin());
			s.insert(arr[i]);
		}
	}
	copy(s.begin(), s.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
}

又一个数组排列组合问题:

// 把数组元素合并起来,找出其中最小的整数

int min_combine(int* arr, int len)
{
	assert(arr && len>0);
	char buf_a[100];
	char buf_b[100];
	sort(arr, arr+len, [&](int a, int b){		// C++11
		sprintf(buf_a, "%d%d", a, b);
		sprintf(buf_b, "%d%d", b, a);
		return strcmp(buf_a, buf_b) < 0;
	});
	buf_b[0] = 0;
	for (int i=0; i<len; ++i)
	{
		sprintf(buf_a, "%d", arr[i]);
		strcat(buf_b, buf_a);
	}
	return atoi(buf_b);
}

关键性的思路在于,对于两个元素,怎样确定谁先谁后?

因为其组合ab和ba长度相同,所以先后顺序一定取决于ab和ba的大小,那么就可以直接使用字符串比较!

想到这一点之后,排下序,分分钟的事情~

模拟题

众多题型里面,模拟题绝对是助你堆代码量的利器,为了解决一个问题不顾天长地久。

下面是一道相对不那么恶心的,但也挺费劲的(要不出错的话):

// 顺时针打印整数矩阵内容(从外圈到内圈转转转)

struct dir_right { };
struct dir_down { };
struct dir_left { };
struct dir_up { };

template <int N> void ClockwisePrintMx(int mx[][N], int rows, int cols, int circle, int r, int c, dir_right);
template <int N> void ClockwisePrintMx(int mx[][N], int rows, int cols, int circle, int r, int c, dir_down);
template <int N> void ClockwisePrintMx(int mx[][N], int rows, int cols, int circle, int r, int c, dir_left);
template <int N> void ClockwisePrintMx(int mx[][N], int rows, int cols, int circle, int r, int c, dir_up);

template <int N>
void ClockwisePrintMx(int mx[][N], int rows, int cols, int circle, int r, int c, dir_right)
{
	++circle;
	while (c != cols-circle-1)
	{
		printf("%d ", mx[r][c]);
		++c;
	}
	ClockwisePrintMx(mx, rows, cols, circle, r, c, dir_down());
}

template <int N>
void ClockwisePrintMx(int mx[][N], int rows, int cols, int circle, int r, int c, dir_down)
{
	if (r >= rows-circle-1)
	{
		return;
	}
	while (r != rows-circle-1)
	{
		printf("%d ", mx[r][c]);
		++r;
	}
	ClockwisePrintMx(mx, rows, cols, circle, r, c, dir_left());
}

template <int N>
void ClockwisePrintMx(int mx[][N], int rows, int cols, int circle, int r, int c, dir_left)
{
	while (c != circle)
	{
		printf("%d ", mx[r][c]);
		--c;
	}
	ClockwisePrintMx(mx, rows, cols, circle, r, c, dir_up());
}

template <int N>
void ClockwisePrintMx(int mx[][N], int rows, int cols, int circle, int r, int c, dir_up)
{
	if (r <= circle)
	{
		return;
	}
	while (r != circle)
	{
		printf("%d ", mx[r][c]);
		--r;
	}
	ClockwisePrintMx(mx, rows, cols, circle, r, c, dir_right());
}

模拟题多数都没什么技巧性,但是逻辑多写起来容易出错,所以考虑解题的思路不再像一般情况那样找个好的算法,而是为了清晰不容易犯错,就算犯了错也要尽量容易看出来。对各个主要过程分别处理是种很好的方式。

关于树,尤其是二叉树的问题也是十分十分十分的常见。大多重在思路吧,一旦细节想明白了,编码一般都不需要写很多。

// 输入二叉搜索树,输出有序双向链表(不可以新建节点)

BinTreeNode* GetListByTree(BinTreeNode* root)
{
	if (!root)
	{
		return;
	}

	BinTreeNode* lastnode = NULL;

	ConvertToList(root, &lastnode);
	// 向前向前向前!我们的队伍像太阳(被拖走)..—— 弄到链表头
	while (lastnode && lastnode->left)
	{
		lastnode = lastnode->left;
	}
	return lastnode;
}

void ConvertToList(BinTreeNode* root, BinTreeNode** lastnode)
{
	assert(!root);

	if (!root->left)
	{
		ConvertToList(root->left, lastnode);
	}

	root->left = *lastnode;
	if (!*lastnode)
	{
		(*lastnode)->right = root;
	}
	*lastnode = root;

	if (!root->right)
	{
		ConvertToList(root->right, lastnode);
	}
}

感觉起来是挺困难的问题,实际上如果想明白其实就是中序遍历一把,在中间穿插一点点工作,就完成了。具体解决的时候还是重在对过程的仔细分析!

栈我虽然平时用的不多,但最近看了一下,发现搞搞怪还是能当作玩具用用的。比如说什么两个栈搞在一起来冒充队列啦,栈包含min()这个特异功能啦之类的。

template <typename T>
class TStack
{
public:
	bool empty() const
	{
		return m_stack.empty();
	}
	void push(const T& n)
	{
		m_stack.push(n);
		if (m_minstack.empty())
		{
			m_minstack.push(n);
		}
		else
		{
			if (n < m_minstack.top())
			{
				m_minstack.push(n);
			}
			else
			{
				m_minstack.push(m_minstack.top());
			}
		}
	}
	void pop()
	{
		if (m_stack.empty())
		{
			throw std::exception("the stack is empty!!");
		}
		m_stack.pop();
		m_minstack.pop();
	}
	T& min()
	{
		return m_minstack.top();
	}
private:
	stack<T> m_stack;
	stack<T> m_minstack;
};

这个乍一看感觉还挺奇葩的,不过每一层栈上都保存目前的最小值,这个思路确实不赖。

无厘头

各种常见问题里,还有一类我无情的将之归入《永远的无厘头》阵营,比如:求1+2+..n,不能使用乘除法、for\while\if\switch\三目运算等

// 方法1:构造函数
int sum=0;
struct x { x(){ sum+=sum+1; } };
x _x[100];

// 方法2:TMP
template <int N> struct Cal { enum { res = N+Cal<N-1>::res }; };
template < > struct Cal<0> { enum { res = 0}; };

// 方法3:函数指针
void t0(int cnt, int sum, int max);
void t1(int cnt, int sum, int max);

typedef void (*PFun)(int cnt, int sum, int max);
PFun pfn[] = {t0, t1};
void t0(int cnt, int sum, int max) { (*(pfn + cnt/max))(cnt+1,sum+cnt,max); }
void t1(int cnt, int sum, int max) { /*sum is here*/ }

void test() { t0(1,1,1000); }

// 方法4:异常
void test(int n, int sum, int max)
{
	1/(n-max);				// Div 0
	test(n+1, sum+n, max);
}

// 方法5:宏展开
#define REP_10(N) N N N N N N N N N N
#define REP_100(N) REP_10(REP_10(N))
#define REP_10000(N) REP_100(REP_100(N))

void test() 
{
	int sum = 0;
	int i = 1;
	REP_10000(sum+=i; ++i;);
}

// 方法6(如果支持&&的话)
bool test(int n, int& sum)
{
	sum += n;
	return n && test(n-1, sum);
}

先到这里。

Contents
  1. 1. 异常安全
  2. 2. 线程安全
  3. 3. 链表
  4. 4. 二分算法
  5. 5. 位运算
  6. 6. 幂运算
  7. 7. 数字和字符串
  8. 8. 数组
  9. 9. 模拟题
  10. 10.
  11. 11.
  12. 12. 无厘头