程序员面试题精选100题完整版

2024年3月29日发(作者：宁静拼音)

程序员面试题精选100题

前言

随着高校的持续扩张，每年应届毕业生的数目都在不断增长，伴随而来的是应届毕业生

的就业压力也越来越大。

在这样的背景下，就业变成一个买方市场的趋势越来越明显。为了找到一个称心的工作，

绝大多数应届毕业生都必须反复经历简历筛选、电话面试、笔试、面试等环节。在这些环节

中，面试无疑起到最为重要的作用，因为通过面试公司能够最直观的了解学生的能力。

为了有效地准备面试，面经这个新兴概念应运而生。笔者在当初找工作阶段也从面经中

获益匪浅并最终找到满意的工作。为了方便后来者，笔者花费大量时间收集并整理散落在茫

茫网络中的面经。不同行业的面经全然不同，笔者从自身专业出发，着重关注程序员面试的

面经，并从精选出若干具有代表性的技术类的面试题展开讨论，希望能给读者带来一些启发。

由于笔者水平有限，给各面试题提供的思路和代码难免会有错误，还请读者批评指正。

另外，热忱欢迎读者能够提供更多、更好的面试题，本人将感激不尽。

(01)把二元查找树转变成排序的双向链表

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创

建任何新的结点，只调整指针的指向。

比如将二元查找树

10

/

6 14

/ /

4 8 12 16

转换成双向链表

4=6=8=10=12=14=16。

分析：本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决，本题也不

例外。下面我们用两种不同的递归思路来分析。

思路一：当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树将

左子树转换成一个排好序的左子链表，再调整其右子树转换右子链表。最近链接左子链表的

最右结点（左子树的最大结点）、当前结点和右子链表的最左结点（右子树的最小结点）。

从树的根结点开始递归调整所有结点。

思路二：我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果

我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整

当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个

排序双向链表了。

参考代码：

首先我们定义二元查找树结点的数据结构如下：

struct BSTreeNode // a node in the binary arch tree

{

int m_nValue; // value of node

BSTreeNode *m_pLeft; // left child of node

BSTreeNode *m_pRight; // right child of node

};

思路一对应的代码：

/////////////////////////////////////////////////////////////////////

//

// Covert a sub binary-arch-tree into a sorted double-linked list

// Input: pNode - the head of the sub tree

// asRight - whether pNode is the right child of its parent

// Output: if asRight is true, return the least node in the sub-tree

// el return the greatest node in the sub-tree

/////////////////////////////////////////////////////////////////////

//

BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight)

{

// Connect the least node in the right sub-tree to the current node

// Convert the right sub-tree

if(pNode->m_pRight)

pRight = ConvertNode(pNode->m_pRight, true);

// Connect the greatest node in the left sub-tree to the current node

if(pLeft)

{

}

pLeft->m_pRight = pNode;

pNode->m_pLeft = pLeft;

// Convert the left sub-tree

if(pNode->m_pLeft)

pLeft = ConvertNode(pNode->m_pLeft, fal);

BSTreeNode *pLeft = NULL;

BSTreeNode *pRight = NULL;

if(!pNode)

return NULL;

}

if(pRight)

{

}

BSTreeNode *pTemp = pNode;

// If the current node is the right child of its parent,

// return the least node in the tree who root is the current node

if(asRight)

{

}

// If the current node is the left child of its parent,

// return the greatest node in the tree who root is the current node

el

{

}

return pTemp;

while(pTemp->m_pRight)

pTemp = pTemp->m_pRight;

while(pTemp->m_pLeft)

pTemp = pTemp->m_pLeft;

pNode->m_pRight = pRight;

pRight->m_pLeft = pNode;

/////////////////////////////////////////////////////////////////////

//

// Covert a binary arch tree into a sorted double-linked list

// Input: the head of tree

// Output: the head of sorted double-linked list

/////////////////////////////////////////////////////////////////////

//

BSTreeNode* Convert(BSTreeNode* pHeadOfTree)

{

}

// As we want to return the head of the sorted double-linked list,

// we t the cond parameter to be true

return ConvertNode(pHeadOfTree, true);

思路二对应的代码：

/////////////////////////////////////////////////////////////////////

//

// Covert a sub binary-arch-tree into a sorted double-linked list

// Input: pNode - the head of the sub tree

// pLastNodeInList - the tail of the double-linked list

/////////////////////////////////////////////////////////////////////

//

void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)

{

}

/////////////////////////////////////////////////////////////////////

//

// Covert a binary arch tree into a sorted double-linked list

// Input: pHeadOfTree - the head of tree

// Output: the head of sorted double-linked list

/////////////////////////////////////////////////////////////////////

//

BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)

{

return pHeadOfList;

// Get the head of the double-linked list

BSTreeNode *pHeadOfList = pLastNodeInList;

while(pHeadOfList && pHeadOfList->m_pLeft)

pHeadOfList = pHeadOfList->m_pLeft;

BSTreeNode *pLastNodeInList = NULL;

ConvertNode(pHeadOfTree, pLastNodeInList);

// Convert the right sub-tree

if (pCurrent->m_pRight != NULL)

ConvertNode(pCurrent->m_pRight, pLastNodeInList);

pLastNodeInList = pCurrent;

// Put the current node into the double-linked list

pCurrent->m_pLeft = pLastNodeInList;

if(pLastNodeInList != NULL)

pLastNodeInList->m_pRight = pCurrent;

// Convert the left sub-tree

if (pCurrent->m_pLeft != NULL)

ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

BSTreeNode *pCurrent = pNode;

if(pNode == NULL)

return;

}

(02)设计包含min函数的栈

题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、

push以及pop的时间复杂度都是O(1)。

分析：这是去年google的一道面试题。

我看到这道题目时，第一反应就是每次push一个新元素时，将栈里所有逆序元素排序。这

样栈顶元素将是最小元素。但由于不能保证最后push进栈的元素最先出栈，这种思路设计

的数据结构已经不是一个栈了。

在栈里添加一个成员变量存放最小元素（或最小元素的位置）。每次push一个新元素进栈

的时候，如果该元素比当前的最小元素还要小，则更新最小元素。

乍一看这样思路挺好的。但仔细一想，该思路存在一个重要的问题：如果当前最小元素被

pop出去，如何才能得到下一个最小元素？

因此仅仅只添加一个成员变量存放最小元素（或最小元素的位置）是不够的。我们需要一个

辅助栈。每次push一个新元素的时候，同时将最小元素（或最小元素的位置。考虑到栈元

素的类型可能是复杂的数据结构，用最小元素的位置将能减少空间消耗）push到辅助栈中；

每次pop一个元素出栈的时候，同时pop辅助栈。

参考代码：

#include

#include

template class CStackWithMin

{

public:

private:

};

// get the last element of mutable stack

T>m_data;// theelements of stack

size_t>m_minIndex;// the indicesof minimum elements

const T& min(void) const;

void push(const T& value);

void pop(void);

T& top(void);

const T& top(void) const;

CStackWithMin(void) {}

virtual ~CStackWithMin(void) {}

template T& CStackWithMin::top()

{

}

// get the last element of non-mutable stack

template const T& CStackWithMin::top() const

{

}

// inrt an elment at the end of stack

template void CStackWithMin::push(const T& value)

{

}

// erea the element at the end of stack

template void CStackWithMin::pop()

{

}

// get the minimum element of stack

template const T& CStackWithMin::min() const

{

asrt(m_() > 0);

asrt(m_() > 0);

// pop m_minIndex

m__back();

// pop m_data

m__back();

// t the index of minimum elment in m_data at the end of m_minIndex

if(m_() == 0)

{

}

if(value < m_data[m_()])

m__back(m_() - 1);

m__back(m_());

el

m__back(0);

el

// append the data into the end of m_data

m__back(value);

return m_();

return m_();

}

return m_data[m_()];

举个例子演示上述代码的运行过程：

步骤 数据栈 辅助栈 最小值

3 3 0 3

4 3,4 0,0 3

2 3,4,2 0,0,2 2

1 3,4,2,1 0,0,2,3 1

3,4,2 0,0,2 2

3,4 0,0 3

0 3,4,0 0,0,2 0

讨论：如果思路正确，编写上述代码不是一件很难的事情。但如果能注意一些细节无疑能在

面试中加分。比如我在上面的代码中做了如下的工作：

• 用模板类实现。如果别人的元素类型只是int类型，模板将能给面试官带来好印象；

• 两个版本的top函数。在很多类中，都需要提供const和非const版本的成员访问函

数；

• min函数中asrt。把代码写的尽量安全是每个软件公司对程序员的要求；

• 添加一些注释。注释既能提高代码的可读性，又能增加代码量，何乐而不为？

总之，在面试时如果时间允许，尽量把代码写的漂亮一些。说不定代码中的几个小亮点就能

让自己轻松拿到心仪的Offer。

(03)－求子数组的最大和

题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个

子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为

该子数组的和18。

分析：本题最初为2005年浙江大学计算机系的考研题的最后一道程序设计题，在2006年

里包括google在内的很多知名公司都把本题当作面试题。由于本题在网络中广为流传，本

题也顺利成为2006年程序员面试题中经典中的经典。

如果不考虑时间复杂度，我们可以枚举出所有子数组并求出他们的和。不过非常遗憾的是，

由于长度为n的数组有O(n

2

)个子数组；而且求一个长度为n的数组的和的时间复杂度为

O(n)。因此这种思路的时间是O(n

3

)。

很容易理解，当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果

当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个

负数将会减少接下来的和。基于这样的思路，我们可以写出如下代码。

参考代码：

/////////////////////////////////////////////////////////////////////

////////

// Find the greatest sum of all sub-arrays

// Return value: if the input is valid, return true, otherwi return fal

/////////////////////////////////////////////////////////////////////

////////

bool FindGreatestSumOfSubArray

(

)

{

}

return true;

// if all data are negative, find the greatest element in the array

if(nGreatestSum == 0)

{

}

nGreatestSum = pData[0];

for(unsigned int i = 1; i < nLength; ++i)

{

}

if(pData[i] > nGreatestSum)

nGreatestSum = pData[i];

}

// if a greater sum is found, update the greatest sum

if(nCurSum > nGreatestSum)

nGreatestSum = nCurSum;

// if the current sum is negative, discard it

if(nCurSum < 0)

nCurSum = 0;

int nCurSum = nGreatestSum = 0;

for(unsigned int i = 0; i < nLength; ++i)

{

nCurSum += pData[i];

// if the input is invalid, return fal

if((pData == NULL) || (nLength == 0))

return fal;

int *pData, // an array

unsigned int nLength, // the length of array

int &nGreatestSum // the greatest sum of all sub-arrays

讨论：上述代码中有两点值得和大家讨论一下：

• 函数的返回值不是子数组和的最大值，而是一个判断输入是否有效的标志。如果函数

返回值的是子数组和的最大值，那么当输入一个空指针是应该返回什么呢？返回0？那这个

函数的用户怎么区分输入无效和子数组和的最大值刚好是0这两中情况呢？基于这个考虑，

本人认为把子数组和的最大值以引用的方式放到参数列表中，同时让函数返回一个函数是否

正常执行的标志。

• 输入有一类特殊情况需要特殊处理。当输入数组中所有整数都是负数时，子数组和的

最大值就是数组中的最大元素。

(04)－在二元树中找出和为某一值的所有路径

题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有

结点形成一条路径。打印出和与输入整数相等的所有路径。

例如输入整数22和如下二元树

10

/

5 12

/

4 7

则打印出两条路径：10, 12和10, 5, 7。

二元树结点的数据结构定义为：

struct BinaryTreeNode // a node in the binary tree

{

};

int m_nValue; // value of node

BinaryTreeNode *m_pLeft; // left child of node

BinaryTreeNode *m_pRight; // right child of node

分析：这是百度的一道笔试题，考查对树这种基本数据结构以及递归函数的理解。

当访问到某一结点时，把该结点添加到路径上，并累加当前结点的值。如果当前结点为叶结

点并且当前路径的和刚好等于输入的整数，则当前的路径符合要求，我们把它打印出来。如

果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回

到父结点。因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值，以确保

返回父结点时路径刚好是根结点到父结点的路径。我们不难看出保存路径的数据结构实际上

是一个栈结构，因为路径要与递归调用状态一致，而递归调用本质就是一个压栈和出栈的过

程。

参考代码：

/////////////////////////////////////////////////////////////////////

//

// Find paths who sum equal to expected sum

/////////////////////////////////////////////////////////////////////

//

void FindPath

(

)

BinaryTreeNode* pTreeNode, // a node of binary tree

int expectedSum, // the expected sum

std::vector&path, // a pathfrom root to current node

int& currentSum // the sum of path

{

// if the node is a leaf, and the sum is same as pre-defined,

// the path is what we want. print the path

bool isLeaf = (!pTreeNode->m_pLeft && !pTreeNode->m_pRight);

if(currentSum == expectedSum && isLeaf)

{

currentSum += pTreeNode->m_nValue;

_back(pTreeNode->m_nValue);

if(!pTreeNode)

return;

std::vector::iterator iter =();

for(; iter != (); ++ iter)

}

// when we finish visiting a node and return to its parent node,

// we should delete this node from the path and

// minus the node's value from the current sum

currentSum -= pTreeNode->m_nValue; //!!I think here is no u

_back();

// if the node is not a leaf, goto its children

if(pTreeNode->m_pLeft)

FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum);

FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum);

if(pTreeNode->m_pRight)

}

std::cout<<*iter<<'t';

std::cout<

(05)查找最小的k个元素

题目：输入n个整数，输出其中最小的k个。

例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

分析：这道题最简单的思路莫过于把输入的n个整数排序，这样排在最前面的k个数就是

最小的k个数。只是这种思路的时间复杂度为O(nlogn)。我们试着寻找更快的解决思路。

我们可以开辟一个长度为k的数组。每次从输入的n个整数中读入一个数。如果数组中已

经插入的元素少于k个，则将读入的整数直接放到数组中。否则长度为k的数组已经满了，

不能再往数组里插入元素，只能替换了。如果读入的这个整数比数组中已有k个整数的最大

值要小，则用读入的这个整数替换这个最大值；如果读入的整数比数组中已有k个整数的最

大值还要大，则读入的这个整数不可能是最小的k个整数之一，抛弃这个整数。这种思路相

当于只要排序k个整数，因此时间复杂可以降到O(n+nlogk)。

通常情况下k要远小于n，

所以这种办法要优于前面的思路。

这是我能够想出来的最快的解决方案。不过从给面试官留下更好印象的角度出发，我们可以

进一步把代码写得更漂亮一些。从上面的分析，当长度为k的数组已经满了之后，如果需要

替换，每次替换的都是数组中的最大值。在常用的数据结构中，能够在O(1)时间里得到最

大值的数据结构为最大堆。因此我们可以用堆（heap）来代替数组。

另外，自己重头开始写一个最大堆需要一定量的代码。我们现在不需要重新去发明车轮，因

为前人早就发明出来了。同样，STL中的t和multit为我们做了很好的堆的实现，我们

可以拿过来用。既偷了懒，又给面试官留下熟悉STL的好印象，何乐而不为之？

参考代码：

#include

#include

#include

using namespace std;

typedef multit > IntHeap;

/////////////////////////////////////////////////////////////////////

//

// find k least numbers in a vector

/////////////////////////////////////////////////////////////////////

//

void FindKLeastNumbers

(

)

{

// leastNumbers contains k numbers and it's full now

el

{

// first number in leastNumbers is the greatest one

vector::const_iterator iter = ();

for(; iter != (); ++ iter)

{

// if less than k numbers was inrted into leastNumbers

if((()) < k)

(*iter);

if(k == 0 || () < k)

return;

();

const vector& data, // a vector of data

IntHeap& leastNumbers, // k least numbers, output

unsigned int k

}

}

}

IntHeap::iterator iterFirst = ();

// if is less than the previous greatest number

if(*iter < *(()))

{

}

// replace the previous greatest number

(iterFirst);

(*iter);

(06)判断整数序列是不是二元查找树的后序遍历结果

题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回

true，否则返回fal。

例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：

8

/

6 10

/ /

5 7 9 11

因此返回true。

如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回fal。

分析：这是一道trilogy的笔试题，主要考查对二元查找树的理解。

在后续遍历得到的序列中，最后一个元素为树的根结点。从头开始扫描这个序列，比根结点

小的元素都应该位于序列的左半部分；从第一个大于跟结点开始到跟结点前面的一个元素为

止，所有元素都应该大于跟结点，因为这部分元素对应的是树的右子树。根据这样的划分，

把序列划分为左右两部分，我们递归地确认序列的左、右两部分是不是都是二元查找树。

参考代码：

using namespace std;

/////////////////////////////////////////////////////////////////////

//

// Verify whether a squence of integers are the post order traversal

// of a binary arch tree (BST)

// Input: squence - the squence of integers

// length - the length of squence

// Return: return ture if the squence is traversal result of a BST,

// otherwi, return fal

/////////////////////////////////////////////////////////////////////

//

bool verifySquenceOfBST(int squence[], int length)

{

}

return (left && right);

// verify whether the right sub-tree is a BST

bool right = true;

if(i < length - 1)

right = verifySquenceOfBST(squence + i, length - i - 1);

// verify whether the left sub-tree is a BST

bool left = true;

if(i > 0)

left = verifySquenceOfBST(squence, i);

// the nodes in the right sub-tree are greater than the root

int j = i;

for(; j < length - 1; ++ j)

{

}

if(squence[j] < root)

return fal;

// the nodes in left sub-tree are less than the root

int i = 0;

for(; i < length - 1; ++ i)

{

}

if(squence[i] > root)

break;

// root of a BST is at the end of post order traversal squence

int root = squence[length - 1];

if(squence == NULL || length <= 0)

return fal;

(07)－翻转句子中单词的顺序

题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词

以空格符隔开。为简单起见，标点符号和普通字母一样处理。

例如输入“I am a student.”，则输出“student. a am I”。

分析：由于编写字符串相关代码能够反映程序员的编程能力和编程习惯，与字符串相关的问

题一直是程序员笔试、面试题的热门题目。本题也曾多次受到包括微软在内的大量公司的青

睐。

由于本题需要翻转句子，我们先颠倒句子中的所有字符。这时，不但翻转了句子中单词的顺

序，而且单词内字符也被翻转了。我们再颠倒每个单词内的字符。由于单词内的字符被翻转

两次，因此顺序仍然和输入时的顺序保持一致。

还是以上面的输入为例子。翻转“I am a student.”中所有字符得到“.tneduts a ma I”，

再翻转每个单词中字符的顺序得到“students. a am I”，正是符合要求的输出。

参考代码：

/////////////////////////////////////////////////////////////////////

//

// Rever a string between two pointers

// Input: pBegin - the begin pointer in a string

// pEnd - the end pointer in a string

/////////////////////////////////////////////////////////////////////

//

void Rever(char *pBegin, char *pEnd)

{

}

/////////////////////////////////////////////////////////////////////

//

// Rever the word order in a ntence, but maintain the character

// order inside a word

// Input: pData - the ntence to be reverd

/////////////////////////////////////////////////////////////////////

//

char* ReverSentence(char *pData)

{

char *pBegin = pData;

char *pEnd = pData;

if(pData == NULL)

return NULL;

}

pBegin ++, pEnd --;

while(pBegin < pEnd)

{

char temp = *pBegin;

*pBegin = *pEnd;

*pEnd = temp;

if(pBegin == NULL || pEnd == NULL)

return;

}

return pData;

// Rever every word in the ntence

pBegin = pEnd = pData;

while(*pBegin != '0')

{

}

if(*pBegin == ' ')

{

}

// A word is between with pBegin and pEnd, rever it

el if(*pEnd == ' ' || *pEnd == '0')

{

}

el

{

}

pEnd ++;

Rever(pBegin, --pEnd);

pBegin = ++pEnd;

pBegin ++;

pEnd ++;

continue;

// Rever the whole ntence

Rever(pBegin, pEnd);

while(*pEnd != '0')

pEnd ++;

pEnd--;

(08)－求1+2+...+n

题目：求1+2+…+n，要求不能使用乘除法、for、while、if、el、switch、ca等关键字以

及条件判断语句（A?B:C）。

分析：这道题没有多少实际意义，因为在软件开发中不会有这么变态的限制。但这道题却能

有效地考查发散思维能力，而发散思维能力能反映出对编程相关技术理解的深刻程度。

通常求1+2+…+n除了用公式n(n+1)/2之外，无外乎循环和递归两种思路。由于已经明确限

制for和while的使用，循环已经不能再用了。同样，递归函数也需要用if语句或者条件判

断语句来判断是继续递归下去还是终止递归，但现在题目已经不允许使用这两种语句了。

我们仍然围绕循环做文章。循环只是让相同的代码执行n遍而已，我们完全可以不用for和

while达到这个效果。比如定义一个类，我们new一含有n个这种类型元素的数组，那么该

类的构造函数将确定会被调用n次。我们可以将需要执行的代码放到构造函数里。如下代码

正是基于这个思路：

class Temp

{

public:

private:

};

int Temp::N = 0;

int Temp::Sum = 0;

int solution1_Sum(int n)

{

Temp::Ret();

return Temp::GetSum();

}

Temp *a = new Temp[n];

delete []a;

a = 0;

static int N;

static int Sum;

static void Ret() { N = 0; Sum = 0; }

static int GetSum() { return Sum; }

Temp() { ++ N; Sum += N; }

我们同样也可以围绕递归做文章。既然不能判断是不是应该终止递归，我们不妨定义两个函

数。一个函数充当递归函数的角色，另一个函数处理终止递归的情况，我们需要做的就是在

两个函数里二选一。从二选一我们很自然的想到布尔变量，比如ture（1）的时候调用第一

个函数，fal（0）的时候调用第二个函数。那现在的问题是如和把数值变量n转换成布尔

值。如果对n连续做两次反运算，即!!n，那么非零的n转换为true，0转换为fal。有了上

述分析，我们再来看下面的代码：

class A;

A* Array[2];

class A

{

public:

};

class B: public A

virtual int Sum (int n) { return 0; }

{

public:

};

int solution2_Sum(int n)

{

}

return value;

int value = Array[1]->Sum(n);

A a;

B b;

Array[0] = &a;

Array[1] = &b;

virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; }

这种方法是用虚函数来实现函数的选择。当n不为零时，执行函数

B::Sum

；当n为0时，

执行

A::Sum

。我们也可以直接用函数指针数组，这样可能还更直接一些：

typedef int (*fun)(int);

int solution3_f1(int i)

{

}

int solution3_f2(int i)

{

}

另外我们还可以让编译器帮我们来完成类似于递归的运算，比如如下代码：

template struct solution4_Sum

{

};

template <> struct solution4_Sum<1>

{

};

solution4_Sum<100>::N

就是1+2+...+100的结果。当编译器看到

solution4_Sum<100>

enum Value { N = 1};

enum Value { N = solution4_Sum::N + n};

fun f[2]={solution3_f1, solution3_f2};

return i+f[!!i](i-1);

return 0;

时，就是为模板类

solution4_Sum

以参数100生成该类型的代码。但以100为参数的类型

需要得到以99为参数的类型，因为

solution4_Sum<100>::N=solution4_Sum<99>::N+100

。这个过程会递归一直到参数

为1的类型，由于该类型已经显式定义，编译器无需生成，递归编译到此结束。由于这个过

程是在编译过程中完成的，因此要求输入n必须是在编译期间就能确定，不能动态输入。这

是该方法最大的缺点。而且编译器对递归编译代码的递归深度是有限制的，也就是要求n

不能太大。

大家还有更多、更巧妙的思路吗？欢迎讨论^_^

(09)－查找链表中倒数第k个结点

题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表

的尾指针。链表结点定义如下：

struct ListNode

{

};

int m_nKey;

ListNode* m_pNext;

分析：为了得到倒数第k个结点，很自然的想法是先走到链表的尾端，再从尾端回溯k步。

可是输入的是单向链表，只有从前往后的指针而没有从后往前的指针。因此我们需要打开我

们的思路。

既然不能从尾结点开始遍历这个链表，我们还是把思路回到头结点上来。假设整个链表有n

个结点，那么倒数第k个结点是从头结点开始的第n-k-1个结点（从0开始计数）。如果我

们能够得到链表中结点的个数n，那我们只要从头结点开始往后走n-k-1步就可以了。如何

得到结点数n？这个不难，只需要从头开始遍历链表，每经过一个结点，计数器加一就行了。

这种思路的时间复杂度是O(n)，但需要遍历链表两次。第一次得到链表中结点个数n，第

二次得到从头结点开始的第n-k-1个结点即倒数第k个结点。

如果链表的结点数不多，这是一种很好的方法。但如果输入的链表的结点个数很多，有可能

不能一次性把整个链表都从硬盘读入物理内存，那么遍历两遍意味着一个结点需要两次从硬

盘读入到物理内存。我们知道把数据从硬盘读入到内存是非常耗时间的操作。我们能不能把

链表遍历的次数减少到1？如果可以，将能有效地提高代码执行的时间效率。

如果我们在遍历时维持两个指针，第一个指针从链表的头指针开始遍历，在第k-1步之前，

第二个指针保持不动；在第k-1步开始，第二个指针也开始从链表的头指针开始遍历。由于

两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指

针（走在后面的）指针正好是倒数第k个结点。

这种思路只需要遍历链表一次。对于很长的链表，只需要把每个结点从硬盘导入到内存一次。

因此这一方法的时间效率前面的方法要高。

思路一的参考代码：

/////////////////////////////////////////////////////////////////////

//

// Find the kth node from the tail of a list

// Input: pListHead - the head of list

// k - the distance to the tail

// Output: the kth node from the tail of a list

/////////////////////////////////////////////////////////////////////

//

ListNode* FindKthToTail_Solution1(ListNode* pListHead, unsigned int k)

{

if(pListHead == NULL)

return NULL;

// count the nodes number in the list

ListNode *pCur = pListHead;

unsigned int nNum = 0;

while(pCur->m_pNext != NULL)

{

}

// if the number of nodes in the list is less than k

// do nothing

if(nNum < k)

return NULL;

pCur = pCur->m_pNext;

nNum ++;

// the kth node from the tail of a list

// is the (n - k)th node from the head

pCur = pListHead;

for(unsigned int i = 0; i < nNum - k; ++ i)

pCur = pCur->m_pNext;

return pCur;

}

思路二的参考代码：

/////////////////////////////////////////////////////////////////////

//

// Find the kth node from the tail of a list

// Input: pListHead - the head of list

// k - the distance to the tail

// Output: the kth node from the tail of a list

/////////////////////////////////////////////////////////////////////

//

ListNode* FindKthToTail_Solution2(ListNode* pListHead, unsigned int k)

{

for(unsigned int i = 0; i < k; ++ i)

{

ListNode *pAhead = pListHead;

ListNode *pBehind = NULL;

if(pListHead == NULL)

return NULL;

}

}

if(pAhead->m_pNext != NULL)

{

}

// if the number of nodes in the list is less than k,

// do nothing

return NULL;

pAhead = pAhead->m_pNext;

el

pBehind = pListHead;

// the distance between pAhead and pBehind is k

// when pAhead arrives at the tail, p

// Behind is at the kth node from the tail

while(pAhead->m_pNext != NULL)

{

}

return pBehind;

pAhead = pAhead->m_pNext;

pBehind = pBehind->m_pNext;

讨论：这道题的代码有大量的指针操作。在软件开发中，错误的指针操作是大部分问题的根

源。因此每个公司都希望程序员在操作指针时有良好的习惯，比如使用指针之前判断是不是

空指针。这些都是编程的细节，但如果这些细节把握得不好，很有可能就会和心仪的公司失

之交臂。

另外，这两种思路对应的代码都含有循环。含有循环的代码经常出的问题是在循环结束条件

的判断。是该用小于还是小于等于？是该用k还是该用k-1？由于题目要求的是从0开始计

数，而我们的习惯思维是从1开始计数，因此首先要想好这些边界条件再开始编写代码，

再者要在编写完代码之后再用边界值、边界值减1、边界值加1都运行一次（在纸上写代码

就只能在心里运行了）。

扩展：和这道题类似的题目还有：输入一个单向链表。如果该链表的结点数为奇数，输出中

间的结点；如果链表结点数为偶数，输出中间两个结点前面的一个。如果各位感兴趣，请自

己分析并编写代码。

(10)－在排序数组中查找和为给定值的两个数字

题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和

正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，

输出任意一对即可。

例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

分析：如果我们不考虑时间复杂度，最简单想法的莫过去先在数组中固定一个数字，再依次

判断数组中剩下的n-1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复

杂度是O(n

2

)。

我们假设现在随便在数组中找到两个数。如果它们的和等于输入的数字，那太好了，我们找

到了要找的两个数字；如果小于输入的数字呢？我们希望两个数字的和再大一点。由于数组

已经排好序了，我们是不是可以把较小的数字的往后面移动一个数字？因为排在后面的数字

要大一些，那么两个数字的和也要大一些，就有可能等于输入的数字了；同样，当两个数字

的和大于输入的数字的时候，我们把较大的数字往前移动，因为排在数组前面的数字要小一

些，它们的和就有可能等于输入的数字了。

我们把前面的思路整理一下：最初我们找到数组的第一个数字和最后一个数字。当两个数字

的和大于输入的数字时，把较大的数字往前移动；当两个数字的和小于数字时，把较小的数

字往后移动；当相等时，打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。

问题是这样的思路是不是正确的呢？这需要严格的数学证明。感兴趣的读者可以自行证明一

下。

参考代码：

/////////////////////////////////////////////////////////////////////

//

// Find two numbers with a sum in a sorted array

// Output: ture is found such two numbers, otherwi fal

/////////////////////////////////////////////////////////////////////

//

bool FindTwoNumbersWithSum

(

)

{

// if the sum of two numbers is equal to the input

// we have found them

if(curSum == sum)

{

num1 = data[behind];

while(ahead > behind)

{

long long curSum = data[ahead] + data[behind];

int ahead = length - 1;

int behind = 0;

bool found = fal;

if(length < 1)

return found;

int data[], // a sorted array

unsigned int length, // the length of the sorted array

int sum, // the sum

int& num1, // the first number, output

int& num2 // the cond number, output

}

}

}

num2 = data[ahead];

found = true;

break;

// if the sum of two numbers is greater than the input

// decrea the greater number

el if(curSum > sum)

ahead --;

// if the sum of two numbers is less than the input

// increa the less number

el

behind ++;

return found;

扩展：如果输入的数组是没有排序的，但知道里面数字的范围，其他条件不变，如和在O(n)

时间里找到这两个数字？

(11)－求二元查找树的镜像

题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树

的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。

例如输入：

8

/

6 10

/ /

5 7 9 11

输出：

8

/

10 6

/ /

11 9 7 5

定义二元查找树的结点为：

struct BSTreeNode // a node in the binary arch tree (BST)

{

};

int m_nValue; // value of node

BSTreeNode *m_pLeft; // left child of node

BSTreeNode *m_pRight; // right child of node

分析：尽管我们可能一下子不能理解镜像是什么意思，但上面的例子给我们的直观感觉，就

是交换结点的左右子树。我们试着在遍历例子中的二元查找树的同时来交换每个结点的左右

子树。遍历时首先访问头结点8，我们交换它的左右子树得到：

8

/

10 6

/ /

9 11 5 7

我们发现两个结点6和10的左右子树仍然是左结点的值小于右结点的值，我们再试着交换

他们的左右子树，得到：

8

/

10 6

/ /

11 9 7 5

刚好就是要求的输出。

上面的分析印证了我们的直觉：在遍历二元查找树时每访问到一个结点，交换它的左右子树。

这种思路用递归不难实现，将遍历二元查找树的代码稍作修改就可以了。参考代码如下：

/////////////////////////////////////////////////////////////////////

//

// Mirror a BST (s left right child of each node) recursively

// the head of BST in initial call

/////////////////////////////////////////////////////////////////////

//

void MirrorRecursively(BSTreeNode *pNode)

{

}

// mirror right child sub-tree if not null

if(pNode->m_pRight)

MirrorRecursively(pNode->m_pRight);

// s right and left child sub-tree

BSTreeNode *pTemp = pNode->m_pLeft;

pNode->m_pLeft = pNode->m_pRight;

pNode->m_pRight = pTemp;

if(pNode->m_pLeft)

MirrorRecursively(pNode->m_pLeft);

if(!pNode)

return;

// mirror left child sub-tree if not null

由于递归的本质是编译器生成了一个函数调用的栈，因此用循环来完成同样任务时最简单的

办法就是用一个辅助栈来模拟递归。首先我们把树的头结点放入栈中。在循环中，只要栈不

为空，弹出栈的栈顶结点，交换它的左右子树。如果它有左子树，把它的左子树压入栈中；

如果它有右子树，把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子

树了。参考代码如下：

/////////////////////////////////////////////////////////////////////

//

// Mirror a BST (s left right child of each node) Iteratively

// Input: pTreeHead: the head of BST

/////////////////////////////////////////////////////////////////////

//

void MirrorIteratively(BSTreeNode *pTreeHead)

{

while(())

}

}

// push right child sub-tree into stack if not null

if(pNode->m_pRight)

(pNode->m_pRight);

// push left child sub-tree into stack if not null

if(pNode->m_pLeft)

(pNode->m_pLeft);

// s right and left child sub-tree

BSTreeNode *pTemp = pNode->m_pLeft;

pNode->m_pLeft = pNode->m_pRight;

pNode->m_pRight = pTemp;

{

BSTreeNode *pNode = ();

();

std::stackstackTreeNode;

(pTreeHead);

if(!pTreeHead)

return;

(12)－从上往下遍历二元树

题目：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序

打印。

例如输入

8

/

6 10

/ /

5 7 9 11

输出8 6 10 5 7 9 11。

分析：这曾是微软的一道面试题。这道题实质上是要求遍历一棵二元树，只不过不是我们熟

悉的前序、中序或者后序遍历。

我们从树的根结点开始分析。自然先应该打印根结点8，同时为了下次能够打印8的两个子

结点，我们应该在遍历到8时把子结点6和10保存到一个数据容器中。现在数据容器中就

有两个元素6 和10了。按照从左往右的要求，我们先取出6访问。打印6的同时要把6的

两个子结点5和7放入数据容器中，此时数据容器中有三个元素10、5和7。接下来我们

应该从数据容器中取出结点10访问了。注意10比5和7先放入容器，此时又比5和7先

取出，就是我们通常说的先入先出。因此不难看出这个数据容器的类型应该是个队列。

既然已经确定数据容器是一个队列，现在的问题变成怎么实现队列了。实际上我们无需自己

动手实现一个，因为STL已经为我们实现了一个很好的deque（两端都可以进出的队列），

我们只需要拿过来用就可以了。

我们知道树是图的一种特殊退化形式。同时如果对图的深度优先遍历和广度优先遍历有比较

深刻的理解，将不难看出这种遍历方式实际上是一种广度优先遍历。因此这道题的本质是在

二元树上实现广度优先遍历。

参考代码：

#include

#include

using namespace std;

struct BTreeNode // a node in the binary tree

{

};

/////////////////////////////////////////////////////////////////////

//

// Print a binary tree from top level to bottom level

// Input: pTreeRoot - the root of binary tree

/////////////////////////////////////////////////////////////////////

//

void PrintFromTopToBottom(BTreeNode *pTreeRoot)

{

// inrt the root at the tail of queue

_back(pTreeRoot);

// get a empty queue

deque dequeTreeNode;

if(!pTreeRoot)

return;

int m_nValue; // value of node

BTreeNode *m_pLeft; // left child of node

BTreeNode *m_pRight; // right child of node

}

}

// print its left child sub-tree if it has

if(pNode->m_pLeft)

_back(pNode->m_pLeft);

// print its right child sub-tree if it has

if(pNode->m_pRight)

_back(pNode->m_pRight);

// print the node

cout << pNode->m_nValue << ' ';

while(())

{

// get a node from the head of queue

BTreeNode *pNode = ();

_front();

(13)－第一个只出现一次的字符

题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。

分析：这道题是2006年google的一道笔试题。

看到这道题时，最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时

拿这个字符和后面的每个字符相比较，如果在后面没有发现重复的字符，则该字符就是只出

现一次的字符。如果字符串有n个字符，每个字符可能与后面的O(n)个字符相比较，因此

这种思路时间复杂度是O(n

2

)。我们试着去找一个更快的方法。

由于题目与字符出现的次数相关，我们是不是可以统计每个字符在该字符串中出现的次数？

要达到这个目的，我们需要一个数据容器来存放每个字符的出现次数。在这个数据容器中可

以根据字符来查找它出现的次数，也就是说这个容器的作用是把一个字符映射成一个数字。

在常用的数据容器中，哈希表正是这个用途。

哈希表是一种比较复杂的数据结构。由于比较复杂，STL中没有实现哈希表，因此需要我

们自己实现一个。但由于本题的特殊性，我们只需要一个非常简单的哈希表就能满足要求。

由于字符（char）是一个长度为8的数据类型，因此总共有可能256 种可能。于是我们创

建一个长度为256的数组，每个字母根据其ASCII码值作为数组的下标对应数组的对应项，

而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256，以字符ASCII

码为键值的哈希表。

我们第一遍扫描这个数组时，每碰到一个字符，在哈希表中找到对应的项并把出现的次数增

加一次。这样在进行第二次扫描时，就能直接从哈希表中得到每个字符出现的次数了。

参考代码如下：

/////////////////////////////////////////////////////////////////////

//

// Find the first char which appears only once in a string

// Input: pString - the string

// Output: the first not repeating char if the string has, otherwi 0

/////////////////////////////////////////////////////////////////////

//

char FirstNotRepeatingChar(char* pString)

{

// get a hash table, and initialize it

constinttableSize =256;

// invalid input

if(!pString)

return 0;

unsignedinthashTable[tableSize];

for(unsignedinti = 0; i

hashTable[i] = 0;

}

// if the string is empty

// or every char in the string appears at least twice

return 0;

}

pHashKey++;

// find the first char which appears only once in a string

pHashKey = pString;

while(*pHashKey != '0')

{

if(hashTable[*pHashKey] == 1)

return *pHashKey;

// get the how many times each char appears in the string

char* pHashKey = pString;

while(*(pHashKey) != '0')

hashTable[*(pHashKey++)] ++;

(14)－圆圈中最后剩下的数字

题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，每次从这个圆圈中删除第m

个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，

从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。

分析：既然题目有一个数字圆圈，很自然的想法是我们用一个数据结构来模拟这个圆圈。在

常用的数据结构中，我们很容易想到用环形列表。我们可以创建一个总共有m个数字的环

形列表，然后每次从这个列表中删除第m个元素。

在参考代码中，我们用STL中std::list来模拟这个环形列表。由于list并不是一个环形的结

构，因此每次跌代器扫描到列表末尾的时候，要记得把跌代器移到列表的头部。这样就是按

照一个圆圈的顺序来遍历这个列表了。

这种思路需要一个有n个结点的环形列表来模拟这个删除的过程，因此内存开销为O(n)。

而且这种方法每删除一个数字需要m步运算，总共有n个数字，因此总的时间复杂度是

O(mn)。当m和n都很大的时候，这种方法是很慢的。

接下来我们试着从数学上分析出一些规律。首先定义最初的n个数字（0,1,…,n-1）中最后

剩下的数字是关于n和m的方程为f(n,m)。

在这n个数字中，第一个被删除的数字是m%n-1，为简单起见记为k。那么删除k之后的

剩下n-1的数字为0,1,…,k-1,k+1,…,n-1，并且下一个开始计数的数字是k+1。相当于在剩

下的序列中，k+1排到最前面，从而形成序列k+1,…,n-1,0,…k-1。该序列最后剩下的数字

也应该是关于n和m的函数。由于这个序列的规律和前面最初的序列不一样（最初的序列

是从0开始的连续序列），因此该函数不同于前面函数，记为f’(n-1,m)。最初序列最后剩下

的数字f(n,m)一定是剩下序列的最后剩下数字f’(n-1,m)，所以f(n,m)=f’(n-1,m)。

接下来我们把剩下的的这n-1个数字的序列k+1,…,n-1,0,…k-1作一个映射，映射的结果是

形成一个从0到n-2的序列：

k+1 -> 0

k+2 -> 1

…

n-1 -> n-k-2

0 -> n-k-1

…

k-1 -> n-2

把映射定义为p，则p(x)= (x-k-1)%n，即如果映射前的数字是x，则映射后的数字是

(x-k-1)%n。对应的逆映射是p

-1

(x)=(x+k+1)%n。

由于映射之后的序列和最初的序列有同样的形式，都是从0开始的连续序列，因此仍然可

以用函数f来表示，记为f(n-1,m)。根据我们的映射规则，映射之前的序列最后剩下的数字

f’(n-1,m)= p

-1

[f(n-1,m)]=[f(n-1,m)+k+1]%n。把k=m%n-1代入得到

f(n,m)=f’(n-1,m)=[f(n-1,m)+m]%n。

经过上面复杂的分析，我们终于找到一个递归的公式。要得到n个数字的序列的最后剩下

的数字，只需要得到n-1个数字的序列的最后剩下的数字，并可以依此类推。当n=1时，

也就是序列中开始只有一个数字0，那么很显然最后剩下的数字就是0。我们把这种关系表

示为：

0 n=1

f(n,m)={

[f(n-1,m)+m]%n n>1

尽管得到这个公式的分析过程非常复杂，但它用递归或者循环都很容易实现。最重要的是，

这是一种时间复杂度为O(n)，空间复杂度为O(1)的方法，因此无论在时间上还是空间上都

优于前面的思路。

思路一的参考代码：

/////////////////////////////////////////////////////////////////////

//

// n integers (0, 1, ... n - 1) form a circle. Remove the mth from

// the circle at every time. Find the last number remaining

// Input: n - the number of integers in the circle initially

// m - remove the mth number at every time

// Output: the last number remaining when the input is valid,

// otherwi -1

/////////////////////////////////////////////////////////////////////

//

int LastRemaining_Solution1(unsigned int n, unsigned int m)

{

}

return *(curinteger);

}

-- curinteger;

(curinteger);

curinteger = nextinteger;

// remove the mth integer. Note that std::list is not a circle

// so we should handle it manually

list::iterator nextinteger = ++ curinteger;

if(nextinteger == ())

nextinteger = ();

list::iterator curinteger = ();

while(() > 1)

{

// find the mth integer. Note that std::list is not a circle

// so we should handle it manually

for(int i = 1; i < m; ++ i)

{

}

curinteger ++;

if(curinteger == ())

curinteger = ();

// initiate a list with n integers (0, 1, ... n - 1)

list integers;

for(i = 0; i < n; ++ i)

_back(i);

unsigned int i = 0;

// invalid input

if(n < 1 || m < 1)

return -1;

思路二的参考代码：

/////////////////////////////////////////////////////////////////////

//

// n integers (0, 1, ... n - 1) form a circle. Remove the mth from

// the circle at every time. Find the last number remaining

// Input: n - the number of integers in the circle initially

// m - remove the mth number at every time

// Output: the last number remaining when the input is valid,

// otherwi -1

/////////////////////////////////////////////////////////////////////

//

int LastRemaining_Solution2(int n, unsigned int m)

{

}

return lastinteger;

// find the last remaining one in the circle with n integers

for (int i = 2; i <= n; i ++)

lastinteger = (lastinteger + m) % i;

// if there are only one integer in the circle initially,

// of cour the last remaining one is 0

int lastinteger = 0;

// invalid input

if(n <= 0 || m < 0)

return -1;

如果对两种思路的时间复杂度感兴趣的读者可以把n和m的值设的稍微大一点，比如十万

这个数量级的数字，运行的时候就能明显感觉出这两种思路写出来的代码时间效率大不一

样。

(15)－含有指针成员的类的拷贝

题目：下面是一个数组类的声明与实现。请分析这个类有什么问题，并针对存在的问题提出

几种解决方案。

template class Array

{

public:

~Array()

Array(unsigned arraySize):data(0), size(arraySize)

{

}

if(size > 0)

data = new T[size];

{

}

void tValue(unsigned index, const T& value)

{

}

T getValue(unsigned index) const

{

}

if(index < size)

return data[index];

return T();

el

if(index < size)

data[index] = value;

if(data) delete[] data;

private:

};

T* data;

unsigned size;

分析：我们注意在类的内部封装了用来存储数组数据的指针。软件存在的大部分问题通常都

可以归结指针的不正确处理。

这个类只提供了一个构造函数，而没有定义构造拷贝函数和重载拷贝运算符函数。当这个类

的用户按照下面的方式声明并实例化该类的一个实例

Array A(10);

Array B(A);

或者按照下面的方式把该类的一个实例赋值给另外一个实例

Array A(10);

Array B(10);

B=A;

编译器将调用其自动生成的构造拷贝函数或者拷贝运算符的重载函数。在编译器生成的缺省

的构造拷贝函数和拷贝运算符的重载函数，对指针实行的是按位拷贝，仅仅只是拷贝指针的

地址，而不会拷贝指针的内容。因此在执行完前面的代码之后，和指向的同

一地址。当A或者B中任意一个结束其生命周期调用析构函数时，会删除data。由于他们

的data指向的是同一个地方，两个实例的data都被删除了。但另外一个实例并不知道它的

data已经被删除了，当企图再次用它的data的时候，程序就会不可避免地崩溃。

由于问题出现的根源是调用了编译器生成的缺省构造拷贝函数和拷贝运算符的重载函数。一

个最简单的办法就是禁止使用这两个函数。于是我们可以把这两个函数声明为私有函数，如

果类的用户企图调用这两个函数，将不能通过编译。实现的代码如下：

private:

Array(const Array& copy);

const Array& operator = (const Array& copy);

最初的代码存在问题是因为不同实例的data指向的同一地址，删除一个实例的data会把另

外一个实例的data也同时删除。因此我们还可以让构造拷贝函数或者拷贝运算符的重载函

数拷贝的不只是地址，而是数据。由于我们重新存储了一份数据，这样一个实例删除的时候，

对另外一个实例没有影响。这种思路我们称之为深度拷贝。实现的代码如下：

public:

}

size = ;

if(size > 0)

{

}

data = new T[size];

for(int i = 0; i < size; ++ i)

tValue(i, ue(i));

if(data != NULL)

{

}

delete []data;

data = NULL;

const Array& operator = (const Array& copy)

{

if(this == ©)

return *this;

Array(const Array& copy):data(0), size()

{

}

if(size > 0)

{

}

data = new T[size];

for(int i = 0; i < size; ++ i)

tValue(i, ue(i));

为了防止有多个指针指向的数据被多次删除，我们还可以保存究竟有多少个指针指向该数

据。只有当没有任何指针指向该数据的时候才可以被删除。这种思路通常被称之为引用计数

技术。在构造函数中，引用计数初始化为1；每当把这个实例赋值给其他实例或者以参数传

给其他实例的构造拷贝函数的时候，引用计数加1，因为这意味着又多了一个实例指向它的

data；每次需要调用析构函数或者需要把data赋值为其他数据的时候，引用计数要减1，

因为这意味着指向它的data的指针少了一个。当引用计数减少到0的时候，data已经没有

任何实例指向它了，这个时候就可以安全地删除。实现的代码如下：

public:

Array(unsigned arraySize)

:data(0), size(arraySize), count(new unsigned int)

{

}

Array(const Array& copy)

{

}

~Array()

{

}

const Array& operator = (const Array& copy)

{

}

if(data == )

return *this;

Relea();

++ (*count);

: size(), data(), count()

*count = 1;

if(size > 0)

data = new T[size];

Relea();

data = ;

size = ;

count = ;

++(*count);

private:

delete count;

count = 0;

void Relea()

{

--(*count);

if(*count == 0)

{

if(data)

{

}

delete []data;

data = NULL;

}

}

unsigned int *count;

(16)－O(logn)求Fibonacci数列

题目：定义Fibonacci数列如下：

/ 0 n=0

f(n)= 1 n=1

f(n-1)+f(n-2) n=2

输入n，用最快的方法求该数列的第n项。

分析：在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。因此很多

程序员对这道题的递归解法非常熟悉，看到题目就能写出如下的递归求解的代码。

/////////////////////////////////////////////////////////////////////

//

// Calculate the nth item of Fibonacci Series recursively

/////////////////////////////////////////////////////////////////////

//

long long Fibonacci_Solution1(unsigned int n)

{

}

return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);

int result[2] = {0, 1};

if(n < 2)

return result[n];

但是，教科书上反复用这个题目来讲解递归函数，并不能说明递归解法最适合这道题目。我

们以求解f(10)作为例子来分析递归求解的过程。要求得f(10)，需要求得f(9)和f(8)。同样，

要求得f(9)，要先求得f(8)和f(7)……我们用树形结构来表示这种依赖关系

f(10)

/

f(9) f(8)

/ /

f(8) f(7) f(6) f(5)

/ /

f(7) f(6) f(6) f(5)

我们不难发现在这棵树中有很多结点会重复的，而且重复的结点数会随着n的增大而急剧增

加。这意味这计算量会随着n的增大而急剧增大。事实上，用递归方法计算的时间复杂度是

以n的指数的方式递增的。大家可以求Fibonacci的第100项试试，感受一下这样递归会慢

到什么程度。在我的机器上，连续运行了一个多小时也没有出来结果。

其实改进的方法并不复杂。上述方法之所以慢是因为重复的计算太多，只要避免重复计算就

行了。比如我们可以把已经得到的数列中间项保存起来，如果下次需要计算的时候我们先查

找一下，如果前面已经计算过了就不用再次计算了。

更简单的办法是从下往上计算，首先根据f(0)和f(1)算出f(2)，在根据f(1)和f(2)算出f(3)……

依此类推就可以算出第n项了。很容易理解，这种思路的时间复杂度是O(n)。

/////////////////////////////////////////////////////////////////////

//

// Calculate the nth item of Fibonacci Series iteratively

/////////////////////////////////////////////////////////////////////

//

long long Fibonacci_Solution2(unsigned n)

{

return fibN;

}

}

fibNMinusTwo = fibNMinusOne;

fibNMinusOne = fibN;

long long fibNMinusOne = 1;

long long fibNMinusTwo = 0;

long long fibN = 0;

for(unsigned int i = 2; i <= n; ++ i)

{

fibN = fibNMinusOne + fibNMinusTwo;

int result[2] = {0, 1};

if(n < 2)

return result[n];

这还不是最快的方法。下面介绍一种时间复杂度是O(logn)的方法。在介绍这种方法之前，

先介绍一个数学公式：

{f(n), f(n-1), f(n-1), f(n-2)} ={1, 1, 1,0}

n-1

(注：{f(n+1), f(n), f(n), f(n-1)}表示一个矩阵。在矩阵中第一行第一列是f(n+1)，第一行第二

列是f(n)，第二行第一列是f(n)，第二行第二列是f(n-1)。)

有了这个公式，要求得f(n)，我们只需要求得矩阵{1, 1, 1,0}的n-1次方，因为矩阵{1, 1, 1,0}

的n-1次方的结果的第一行第一列就是f(n)。这个数学公式用数学归纳法不难证明。感兴趣

的朋友不妨自己证明一下。

现在的问题转换为求矩阵{1, 1, 1, 0}的乘方。如果简单第从0开始循环，n次方将需要n次

运算，并不比前面的方法要快。但我们可以考虑乘方的如下性质：

/ a

n/2

*a

n/2

n为偶数时

a

n

=

a(

n-1)/2

*a

(n-1)/2

n为奇数时

要求得n次方，我们先求得n/2次方，再把n/2的结果平方一下。如果把求n次方的问题看

成一个大问题，把求n/2看成一个较小的问题。这种把大问题分解成一个或多个小问题的思

路我们称之为分治法。这样求n次方就只需要logn次运算了。

实现这种方式时，首先需要定义一个2×2的矩阵，并且定义好矩阵的乘法以及乘方运算。

当这些运算定义好了之后，剩下的事情就变得非常简单。完整的实现代码如下所示。

#include

/////////////////////////////////////////////////////////////////////

//

// A 2 by 2 matrix

/////////////////////////////////////////////////////////////////////

//

struct Matrix2By2

{

};

/////////////////////////////////////////////////////////////////////

//

// Multiply two matrices

// Input: matrix1 - the first matrix

// matrix2 - the cond matrix

//Output: the production of two matrices

/////////////////////////////////////////////////////////////////////

//

Matrix2By2 MatrixMultiply

(

)

{

return Matrix2By2(

matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,

matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,

matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,

const Matrix2By2& matrix1,

const Matrix2By2& matrix2

long long m_00;

long long m_01;

long long m_10;

long long m_11;

Matrix2By2

(

)

:m_00(m00), m_01(m01), m_10(m10), m_11(m11)

{

}

long long m00 = 0,

long long m01 = 0,

long long m10 = 0,

long long m11 = 0

}

matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);

/////////////////////////////////////////////////////////////////////

//

// The nth power of matrix

// 1 1

// 1 0

/////////////////////////////////////////////////////////////////////

//

Matrix2By2 MatrixPower(unsigned int n)

{

}

/////////////////////////////////////////////////////////////////////

//

// Calculate the nth item of Fibonacci Series using devide and conquer

/////////////////////////////////////////////////////////////////////

//

long long Fibonacci_Solution3(unsigned int n)

{

int result[2] = {0, 1};

if(n < 2)

return result[n];

return matrix;

Matrix2By2 matrix;

if(n == 1)

{

}

el if(n % 2 == 0)

{

}

el if(n % 2 == 1)

{

}

matrix = MatrixPower((n - 1) / 2);

matrix = MatrixMultiply(matrix, matrix);

matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));

matrix = MatrixPower(n / 2);

matrix = MatrixMultiply(matrix, matrix);

matrix = Matrix2By2(1, 1, 1, 0);

asrt(n > 0);

}

Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);

return PowerNMinus2.m_00;

(17)－把字符串转换成整数

题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。例如输入字符串"345"，

则输出整数345。

分析：这道题尽管不是很难，学过C/C++语言一般都能实现基本功能，但不同程序员就这

道题写出的代码有很大区别，可以说这道题能够很好地反应出程序员的思维和编程习惯，因

此已经被包括微软在内的多家公司用作面试题。建议读者在往下看之前自己先编写代码，再

比较自己写的代码和下面的参考代码有哪些不同。

首先我们分析如何完成基本功能，即如何把表示整数的字符串正确地转换成整数。还是以

"345"作为例子。当我们扫描到字符串的第一个字符'3'时，我们不知道后面还有多少位，仅

仅知道这是第一位，因此此时得到的数字是3。当扫描到第二个数字'4'时，此时我们已经知

道前面已经一个3了，再在后面加上一个数字4，那前面的3相当于30，因此得到的数字

是3*10+4=34。接着我们又扫描到字符'5'，我们已经知道了'5'的前面已经有了34，由于后

面要加上一个5，前面的34就相当于340了，因此得到的数字就是34*10+5=345。

分析到这里，我们不能得出一个转换的思路：每扫描到一个字符，我们把在之前得到的数字

乘以10再加上当前字符表示的数字。这个思路用循环不难实现。

由于整数可能不仅仅之含有数字，还有可能以'+'或者'-'开头，表示整数的正负。因此我们需

要把这个字符串的第一个字符做特殊处理。如果第一个字符是'+'号，则不需要做任何操作；

如果第一个字符是'-'号，则表明这个整数是个负数，在最后的时候我们要把得到的数值变成

负数。

接着我们试着处理非法输入。由于输入的是指针，在使用指针之前，我们要做的第一件是判

断这个指针是不是为空。如果试着去访问空指针，将不可避免地导致程序崩溃。另外，输入

的字符串中可能含有不是数字的字符。每当碰到这些非法的字符，我们就没有必要再继续转

换。最后一个需要考虑的问题是溢出问题。由于输入的数字是以字符串的形式输入，因此有

可能输入一个很大的数字转换之后会超过能够表示的最大的整数而溢出。

现在已经分析的差不多了，开始考虑编写代码。首先我们考虑如何声明这个函数。由于是把

字符串转换成整数，很自然我们想到：

int StrToInt(const char* str);

这样声明看起来没有问题。但当输入的字符串是一个空指针或者含有非法的字符时，应该返

回什么值呢？0怎么样？那怎么区分非法输入和字符串本身就是”0”这两种情况呢？

接下来我们考虑另外一种思路。我们可以返回一个布尔值来指示输入是否有效，而把转换后

的整数放到参数列表中以引用或者指针的形式传入。于是我们就可以声明如下：

bool StrToInt(const char *str, int& num);

这种思路解决了前面的问题。但是这个函数的用户使用这个函数的时候会觉得不是很方便，

因为他不能直接把得到的整数赋值给其他整形变脸，显得不够直观。

前面的第一种声明就很直观。如何在保证直观的前提下当碰到非法输入的时候通知用户呢？

一种解决方案就是定义一个全局变量，每当碰到非法输入的时候，就标记该全局变量。用户

在调用这个函数之后，就可以检验该全局变量来判断转换是不是成功。

下面我们写出完整的实现代码。参考代码：

enum Status {kValid = 0, kInvalid};

int g_nStatus = kValid;

/////////////////////////////////////////////////////////////////////

//

// Convert a string into an integer

/////////////////////////////////////////////////////////////////////

//

int StrToInt(const char* str)

{

// overflow

{

num = 0;

break;

}

digit++;

}

if(num>std::numeric_limits::max())

// the remaining chars in the string

while(*digit != '0')

{

if(*digit >= '0' && *digit <= '9')

{

num = num * 10 + (*digit - '0');

// the first char in the string maybe '+' or '-'

bool minus = fal;

if(*digit == '+')

{

}

digit ++;

minus = true;

digit ++;

el if(*digit == '-')

if(str != NULL)

{

const char* digit = str;

g_nStatus = kInvalid;

longlongnum = 0;

}

}

// if the char is not a digit, invalid input

el

{

}

num = 0;

break;

if(*digit == '0')

{

}

g_nStatus = kValid;

if(minus)

num = 0 - num;

return static_cast(num);

}

讨论：在参考代码中，我选用的是第一种声明方式。不过在面试时，我们可以选用任意一种声明

方式进行实现。但当面试官问我们选择的理由时，我们要对两者的优缺点进行评价。第一种声明

方式对用户而言非常直观，但使用了全局变量，不够优雅；而第二种思路是用返回值来表明输入

是否合法，在很多API中都用这种方法，但该方法声明的函数使用起来不够直观。

最后值得一提的是，

在C语言提供的库函数中，函数atoi能够把字符串转换整数。它的声明

是

int atoi(const char *str)。该函数就是用一个全局变量来标志输入是否合法的。

(18)－用两个栈实现队列

题目：某队列的声明如下：

template class CQueue

{

public:

private:

};

T>m_stack1;

T>m_stack2;

CQueue() {}

~CQueue() {}

void appendTail(const T& node); // append a element to tail

void deleteHead(); // remove a element from head

分析：从上面的类的声明中，我们发现在队列中有两个栈。因此这道题实质上是要求我们用

两个栈来实现一个队列。相信大家对栈和队列的基本性质都非常了解了：栈是一种后入先出

的数据容器，因此对队列进行的插入和删除操作都是在栈顶上进行；队列是一种先入先出的

数据容器，我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。

我们通过一个具体的例子来分析往该队列插入和删除元素的过程。首先插入一个元素a，不

妨把先它插入到m_stack1。这个时候m_stack1中的元素有{a}，m_stack2为空。再插入

两个元素b和c，还是插入到m_stack1中，此时m_stack1中的元素有{a,b,c}，m_stack2

中仍然是空的。

这个时候我们试着从队列中删除一个元素。按照队列先入先出的规则，由于a比b、c先插

入到队列中，这次被删除的元素应该是a。元素a存储在m_stack1中，但并不在栈顶上，

因此不能直接进行删除。注意到m_stack2我们还一直没有使用过，现在是让m_stack2起

作用的时候了。如果我们把m_stack1中的元素逐个pop出来并push进入m_stack2，元

素在m_stack2中的顺序正好和原来在m_stack1中的顺序相反。因此经过两次pop和push

之后，m_stack1为空，而m_stack2中的元素是{c,b,a}。这个时候就可以pop出m_stack2

的栈顶a了。pop之后的m_stack1为空，而m_stack2的元素为{c,b}，其中b在栈顶。

这个时候如果我们还想继续删除应该怎么办呢？在剩下的两个元素中b和c，b比c先进入

队列，因此b应该先删除。而此时b恰好又在栈顶上，因此可以直接pop出去。这次pop

之后，m_stack1中仍然为空，而m_stack2为{c}。

从上面的分析我们可以总结出删除一个元素的步骤：当m_stack2中不为空时，在m_stack2

中的栈顶元素是最先进入队列的元素，可以pop出去。如果m_stack2为空时，我们把

m_stack1中的元素逐个pop出来并push进入m_stack2。由于先进入队列的元素被压到

m_stack1的底端，经过pop和push之后就处于m_stack2的顶端了，又可以直接pop出

去。

接下来我们再插入一个元素d。我们是不是还可以把它push进m_stack1？这样会不会有问

题呢？我们说不会有问题。因为在删除元素的时候，如果m_stack2中不为空，处于m_stack2

中的栈顶元素是最先进入队列的，可以直接pop；如果m_stack2为空，我们把m_stack1

中的元素pop出来并push进入m_stack2。由于m_stack2中元素的顺序和m_stack1相反，

最先进入队列的元素还是处于m_stack2的栈顶，仍然可以直接pop。不会出现任何矛盾。

我们用一个表来总结一下前面的例子执行的步骤：

操作

append a

append b

append c

m_stack1

{a}

{a,b}

{a,b,c}

m_stack2

{}

{}

{}

{b,c}

{c}

{c}

{}

delete head {}

delete head {}

append d {d}

delete head {d}

总结完push和pop对应的过程之后，我们可以开始动手写代码了。参考代码如下：

/////////////////////////////////////////////////////////////////////

//

// Append a element at the tail of the queue

/////////////////////////////////////////////////////////////////////

//

template void CQueue::appendTail(const T& element)

{

// push the new element into m_stack1

}

m_(element);

/////////////////////////////////////////////////////////////////////

//

// Delete the head from the queue

/////////////////////////////////////////////////////////////////////

//

template void CQueue::deleteHead()

{

// if m_stack2is empty,and there are some

//elements inm_stack1, push them in m_stack2

if(m_()<= 0)

{

while(m_()>0)

{

T&data =m_();

m_();

m_(data);

}

}

// push theelement into m_stack2

asrt(m_()>0);

m_();

}

扩展：这道题是用两个栈实现一个队列。反过来能不能用两个队列实现一个栈？如果可以，

该如何实现？

(19)－反转链表

题目：输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。链表结点定义如

下：

struct ListNode

{

};

int m_nKey;

ListNode* m_pNext;

分析：这是一道广为流传的微软面试题。由于这道题能够很好的反应出程序员思维是否严密，

在微软之后已经有很多公司在面试时采用了这道题。

为了正确地反转一个链表，需要调整指针的指向。与指针操作相关代码总是容易出错的，因

此最好在动手写程序之前作全面的分析。在面试的时候不急于动手而是一开始做仔细的分析

和设计，将会给面试官留下很好的印象，因为在实际的软件开发中，设计的时间总是比写代

码的时间长。与其很快地写出一段漏洞百出的代码，远不如用较多的时间写出一段健壮的代

码。

为了将调整指针这个复杂的过程分析清楚，我们可以借助图形来直观地分析。假设下图中l、

m和n是三个相邻的结点：

ab…l mn…

假设经过若干操作，我们已经把结点l之前的指针调整完毕，这些结点的

m_pNext

指针都

指向前面一个结点。现在我们遍历到结点m。当然，我们需要把调整结点的

m_pNext指针

让它指向结点

l

。但注意一旦调整了指针的指向，链表就断开了，如下图所示：

ab…lm n…

因为已经没有指针指向结点n，我们没有办法再遍历到结点n了。因此为了避免链表断开，

我们需要在调整m的

m_pNext之前要把

n保存下来。

接下来我们试着找到反转后链表的头结点。不难分析出反转后链表的头结点是原始链表的尾

位结点。什么结点是尾结点？就是

m_pNext

为空指针的结点。

基于上述分析，我们不难写出如下代码：

/////////////////////////////////////////////////////////////////////

//

// Rever a list iteratively

// Input: pHead - the head of the original list

// Output: the head of the reverd head

/////////////////////////////////////////////////////////////////////

//

ListNode* ReverIteratively(ListNode* pHead)

{

}

return pReverdHead;

}

// move forward on the the list

pPrev = pNode;

pNode = pNext;

// rever the linkage between nodes

pNode->m_pNext = pPrev;

// if the next node is null, the currect is the end of original

// list, and it's the head of the reverd list

if(pNext == NULL)

pReverdHead = pNode;

ListNode* pReverdHead = NULL;

ListNode* pNode = pHead;

ListNode* pPrev = NULL;

while(pNode != NULL)

{

// get the next node, and save it at pNext

ListNode* pNext = pNode->m_pNext;

扩展：本题也可以递归实现。感兴趣的读者请自己编写递归代码。

(20)－最长公共子串

题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符

串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符

串二中。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子

串。

例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最

长公共子串，则输出它们的长度4，并打印任意一个子串。

分析：求最长公共子串（Longest Common Subquence, LCS）是一道非常经典的动态规

划题，因此一些重视算法的公司像MicroStrategy都把它当作面试题。

完整介绍动态规划将需要很长的篇幅，因此我不打算在此全面讨论动态规划相关的概念，只

集中对LCS直接相关内容作讨论。如果对动态规划不是很熟悉，请参考相关算法书比如算

法讨论。

先介绍LCS问题的性质：记X

m

={x

0

, x

1

,…x

m-1

}和Y

n

={y

0

,y

1

,…,y

n-1

}为两个字符串，而

Z

k

={z

0

,z

1

,…z

k-1

}是它们的LCS，则：

1. 如果x

m-1

=y

n-1

，那么z

k-1

=x

m-1

=y

n-1

，并且Z

k-1

是X

m-1

和Y

n-1

的LCS；

2. 如果x

m-1

≠y

n-1

，那么当z

k-1

≠x

m-1

时Z是X

m-1

和Y的LCS；

3. 如果x

m-1

≠y

n-1

，那么当z

k-1

≠y

n-1

时Z是Y

n-1

和X的LCS；

下面简单证明一下这些性质：

1. 如果z

k-1

≠x

m-1

，那么我们可以把x

m-1

（y

n-1

）加到Z中得到Z’，这样就得到X和Y的

一个长度为k+1的公共子串Z’。这就与长度为k的Z是X和Y的LCS相矛盾了。因此一

定有z

k-1

=x

m-1

=y

n-1

。

既然z

k-1

=x

m-1

=y

n-1

，那如果我们删除z

k-1

（x

m-1

、y

n-1

）得到的Z

k-1

，X

m-1

和Y

n-1

，显然Z

k-1

是X

m-1

和Y

n-1

的一个公共子串，现在我们证明Z

k-1

是X

m-1

和Y

n-1

的LCS。用反证法不难证

明。假设有X

m-1

和Y

n-1

有一个长度超过k-1的公共子串W，那么我们把加到W中得到W’，

那W’就是X和Y的公共子串，并且长度超过k，这就和已知条件相矛盾了。

2. 还是用反证法证明。假设Z不是X

m-1

和Y的LCS，则存在一个长度超过k的W是

X

m-1

和Y的LCS，那W肯定也X和Y的公共子串，而已知条件中X和Y的公共子串的最

大长度为k。矛盾。

3. 证明同2。

有了上面的性质，我们可以得出如下的思路：求两字符串X

m

={x

0

, x

1

,…x

m-1

}和

Y

n

={y

0

,y

1

,…,y

n-1

}的LCS，如果x

m-1

=y

n-1

，那么只需求得X

m-1

和Y

n-1

的LCS，并在其后添加

x

m-1

（y

n-1

）即可；如果x

m-1

≠y

n-1

，我们分别求得X

m-1

和Y的LCS和Y

n-1

和X的LCS，并

且这两个LCS中较长的一个为X和Y的LCS。

如果我们记字符串X

i

和Y

j

的LCS的长度为c[i,j]，我们可以递归地求c[i,j]：

/ 0 if i<0 or j<0

c[i,j]= c[i-1,j-1]+1 if i,j>=0 and x

i

=x

j

max(c[i,j-1],c[i-1,j] if i,j>=0 and x

i

≠x

j

上面的公式用递归函数不难求得。但从前面求Fibonacci第n项(本面试题系列第16题）的

分析中我们知道直接递归会有很多重复计算，我们用从底向上循环求解的思路效率更高。

为了能够采用循环求解的思路，我们用一个矩阵（参考代码中的

LCS_length

）保存下来当

前已经计算好了的c[i,j]，当后面的计算需要这些数据时就可以直接从矩阵读取。另外，求取

c[i,j]可以从c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三个方向计算得到，相当于在矩阵

LCS_length中

是从

c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一个各自移动到c[i,j]，因此在矩阵中有三种不同的移

动方向：向左、向上和向左上方，其中只有向左上方移动时才表明找到LCS中的一个字符

。

于是

我们需要用另外一个矩阵（参考代码中的

LCS_direction

）保存移动的方向。

参考代码如下：

#include "string.h"

// directions of LCS generation

enum decreaDir {kInit = 0, kLeft, kUp, kLeftUp};

/////////////////////////////////////////////////////////////////////

////////

// Get the length of two strings' LCSs, and print one of the LCSs

// Input: pStr1 - the first string

// pStr2 - the cond string

// Output: the length of two strings' LCSs

/////////////////////////////////////////////////////////////////////

////////

int LCS(char* pStr1, char* pStr2)

{

// initiate the direction matrix

int **LCS_direction;

LCS_direction = (int**)(new int[length1]);

for( i = 0; i < length1; ++ i)

for(i = 0; i < length1; ++ i)

for(j = 0; j < length2; ++ j)

LCS_length[i][j] = 0;

if(!pStr1 || !pStr2)

size_t length2 = strlen(pStr2);

if(!length1 || !length2)

int **LCS_length;

LCS_length = (int**)(new int[length1]);

for(i = 0; i < length1; ++ i)

LCS_length[i] = (int*)new int[length2];

return 0;

return 0;

size_t length1 = strlen(pStr1);

size_t i, j;

// initiate the length matrix

LCS_direction[i] = (int*)new int[length2];

for(i = 0; i < length1; ++ i)

for(j = 0; j < length2; ++ j)

LCS_direction[i][j] = kInit;

for(i = 0; i < length1; ++ i)

{

}

LCS_Print(LCS_direction, pStr1, pStr2, length1 - 1, length2 - 1);

return LCS_length[length1 - 1][length2 - 1];

for(j = 0; j < length2; ++ j)

{

}

if(i == 0 || j == 0)

{

}

// a char of LCS is found,

// it comes from the left up entry in the direction matrix

el if(pStr1[i] == pStr2[j])

{

}

// it comes from the up entry in the direction matrix

el if(LCS_length[i - 1][j] > LCS_length[i][j - 1])

{

}

// it comes from the left entry in the direction matrix

el

{

}

LCS_length[i][j] = LCS_length[i][j - 1];

LCS_direction[i][j] = kLeft;

LCS_length[i][j] = LCS_length[i - 1][j];

LCS_direction[i][j] = kUp;

LCS_length[i][j] = LCS_length[i - 1][j - 1] + 1;

LCS_direction[i][j] = kLeftUp;

if(pStr1[i] == pStr2[j])

{

}

el

LCS_length[i][j] = 0;

LCS_length[i][j] = 1;

LCS_direction[i][j] = kLeftUp;

}

/////////////////////////////////////////////////////////////////////

////////

// Print a LCS for two strings

// Input: LCS_direction - a 2d matrix which records the direction of

// LCS generation

// pStr1 - the first string

// pStr2 - the cond string

// row - the row index in the matrix LCS_direction

// col - the column index in the matrix LCS_direction

/////////////////////////////////////////////////////////////////////

////////

void LCS_Print(int **LCS_direction,

{

// kLeftUp implies a char in the LCS is found

if(LCS_direction[row][col] == kLeftUp)

{

}

el if(LCS_direction[row][col] == kLeft)

{

}

el if(LCS_direction[row][col] == kUp)

{

// move to the up entry in the direction matrix

// move to the left entry in the direction matrix

if(col > 0)

LCS_Print(LCS_direction, pStr1, pStr2, row, col - 1);

if(row > 0 && col > 0)

printf("%c", pStr1[row]);

LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col - 1);

size_t length1 = strlen(pStr1);

size_t length2 = strlen(pStr2);

return;

if(pStr1 == NULL || pStr2 == NULL)

return;

char* pStr1, char* pStr2,

size_t row, size_t col)

if(length1 == 0 || length2 == 0 || !(row < length1 && col < length2))

// print the char

}

}

if(row > 0)

LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col);

扩展：如果题目改成求两个字符串的最长公共子字符串，应该怎么求？子字符串的定义和子

串的定义类似，但要求是连续分布在其他字符串中。比如输入两个字符串BDCABA和

ABCBDAB的最长公共字符串有BD和AB，它们的长度都是2。

(21)－左旋转字符串

题目：定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。如把字

符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度

为n的字符串操作的复杂度为O(n)，辅助内存为O(1)。

分析：如果不考虑时间和空间复杂度的限制，最简单的方法莫过于把这道题看成是把字符串

分成前后两部分，通过旋转操作把这两个部分交换位置。于是我们可以新开辟一块长度为

n+1的辅助空间，把原字符串后半部分拷贝到新空间的前半部分，在把原字符串的前半部分

拷贝到新空间的后半部分。不难看出，这种思路的时间复杂度是O(n)，需要的辅助空间也

是O(n)。

接下来的一种思路可能要稍微麻烦一点。我们假设把字符串左旋转m位。于是我们先把第

0个字符保存起来，把第m个字符放到第0个的位置，在把第2m个字符放到第m个的位

置…依次类推，一直移动到最后一个可以移动字符，最后在把原来的第0个字符放到刚才

移动的位置上。接着把第1个字符保存起来，把第m+1个元素移动到第1个位置…重复前

面处理第0个字符的步骤，直到处理完前面的m个字符。

该思路还是比较容易理解，但当字符串的长度n不是m的整数倍的时候，写程序会有些麻

烦，感兴趣的朋友可以自己试一下。由于下面还要介绍更好的方法，这种思路的代码我就不

提供了。

我们还是把字符串看成有两段组成的，记位XY。左旋转相当于要把字符串XY变成YX。我

们先在字符串上定义一种翻转的操作，就是翻转字符串中字符的先后顺序。把X翻转后记

为X

T

。显然有(X

T

)

T

=X。

我们首先对X和Y两段分别进行翻转操作，这样就能得到X

T

Y

T

。接着再对X

T

Y

T

进行翻转

操作，得到(X

T

Y

T

)

T

=(Y

T

)

T

(X

T

)

T

=YX。正好是我们期待的结果。

分析到这里我们再回到原来的题目。我们要做的仅仅是把字符串分成两段，第一段为前面m

个字符，其余的字符分到第二段。再定义一个翻转字符串的函数，按照前面的步骤翻转三次

就行了。时间复杂度和空间复杂度都合乎要求。

参考代码如下：

#include "string.h"

/////////////////////////////////////////////////////////////////////

//

// Move the first n chars in a string to its end

/////////////////////////////////////////////////////////////////////

//

char* LeftRotateString(char* pStr, unsigned int n)

{

}

if(pStr != NULL)

{

}

return pStr;

int nLength = static_cast(strlen(pStr));

if(nLength > 0 || n == 0 || n > nLength)

{

}

char* pFirstStart = pStr;

char* pFirstEnd = pStr + n - 1;

char* pSecondStart = pStr + n;

char* pSecondEnd = pStr + nLength - 1;

// rever the first part of the string

ReverString(pFirstStart, pFirstEnd);

// rever the cond part of the strint

ReverString(pSecondStart, pSecondEnd);

// rever the whole string

ReverString(pFirstStart, pSecondEnd);

/////////////////////////////////////////////////////////////////////

//

// Rever the string between pStart and pEnd

/////////////////////////////////////////////////////////////////////

//

void ReverString(char* pStart, char* pEnd)

{

}

}

}

pStart ++;

pEnd --;

if(pStart == NULL || pEnd == NULL)

{

while(pStart <= pEnd)

{

char temp = *pStart;

*pStart = *pEnd;

*pEnd = temp;

(22)－整数的二进制表示中1的个数

题目：输入一个整数，求该整数的二进制表达中有多少个1。例如输入10，由于其二进制

表示为1010，有两个1，因此输出2。

分析：这是一道很基本的考查位运算的面试题。包括微软在内的很多公司都曾采用过这道题。

一个很基本的想法是，我们先判断整数的最右边一位是不是1。接着把整数右移一位，原来

处于右边第二位的数字现在被移到第一位了，再判断是不是1。这样每次移动一位，直到这

个整数变成0为止。现在的问题变成怎样判断一个整数的最右边一位是不是1了。很简单，

如果它和整数1作与运算。由于1除了最右边一位以外，其他所有位都为0。因此如果与运

算的结果为1，表示整数的最右边一位是1，否则是0。

得到的代码如下：

/////////////////////////////////////////////////////////////////////

//

// Get how many 1s in an integer's binary expression

/////////////////////////////////////////////////////////////////////

//

int NumberOf1_Solution1(int i)

{

}

可能有读者会问，整数右移一位在数学上是和除以2是等价的。那可不可以把上面的代码中的

右移运算符换成除以2呢？答案是最好不要换成除法。因为除法的效率比移位运算要低的多，

在实际编程中如果可以应尽可能地用移位运算符代替乘除法。

这个思路当输入i是正数时没有问题，但当输入的i是一个负数时，不但不能得到正确的1的

个数，还将导致死循环。以负数0x80000000为例，右移一位的时候，并不是简单地把最高位

的1移到第二位变成0x40000000，而是0xC0000000。这是因为移位前是个负数，仍然要保

证移位后是个负数，因此移位后的最高位会设为1。如果一直做右移运算，最终这个数字就会变

成0xFFFFFFFF而陷入死循环。

为了避免死循环，我们可以不右移输入的数字i。首先i和1做与运算，判断i的最低位是不

是为1。接着把1左移一位得到2，再和i做与运算，就能判断i的次高位是不是1……这样反

复左移，每次都能判断i的其中一位是不是1。基于此，我们得到如下代码：

/////////////////////////////////////////////////////////////////////

//

// Get how many 1s in an integer's binary expression

/////////////////////////////////////////////////////////////////////

return count;

}

i = i >> 1;

int count = 0;

while(i)

{

if(i & 1)

count ++;

//

int NumberOf1_Solution2(int i)

{

}

另外一种思路是如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减去

1，那么原来处在整数最右边的1就会变成0，原来在1后面的所有的0都会变成1。其余的所

有位将不受到影响。举个例子：一个二进制数1100，从右边数起的第三位是处于最右边的一个

1。减去1后，第三位变成0，它后面的两位0变成1，而前面的1保持不变，因此得到结果是

1011。

我们发现减1的结果是把从最右边一个1开始的所有位都取反了。这个时候如果我们再把原来

的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。

如1100&1011=1000。也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右

边一个1变成0。那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

这种思路对应的代码如下：

/////////////////////////////////////////////////////////////////////

//

// Get how many 1s in an integer's binary expression

/////////////////////////////////////////////////////////////////////

//

int NumberOf1_Solution3(int i)

{

}

return count;

while (i)

{

}

++ count;

i = (i - 1) & i;

int count = 0;

return count;

}

flag = flag << 1;

int count = 0;

unsigned int flag = 1;

while(flag)

{

if(i & flag)

count ++;

扩展：如何用一个语句判断一个整数是不是二的整数次幂？

(23)－跳台阶问题

题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法，

并分析算法的时间复杂度。

分析：这道题最近经常出现，包括MicroStrategy等比较重视算法的公司都曾先后选用过个

这道题作为面试题或者笔试题。

首先我们考虑最简单的情况。如果只有1级台阶，那显然只有一种跳法。如果有2级台阶，

那就有两种跳的方法了：一种是分两次跳，每次跳1级；另外一种就是一次跳2级。

现在我们再来讨论一般情况。我们把n级台阶时的跳法看成是n的函数，记为f(n)。当n>2

时，第一次跳的时候就有两种不同的选择：一是第一次只跳1级，此时跳法数目等于后面

剩下的n-1级台阶的跳法数目，即为f(n-1)；另外一种选择是第一次跳2级，此时跳法数目

等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此n级台阶时的不同跳法的总数

f(n)=f(n-1)+(f-2)。

我们把上面的分析用一个公式总结如下：

/ 1 n=1

f(n)= 2 n=2

f(n-1)+(f-2) n>2

分析到这里，相信很多人都能看出这就是我们熟悉的Fibonacci序列。至于怎么求这个序列

的第n项，请参考本面试题系列第16题，这里就不在赘述了。

(24)－栈的push、pop序列

题目：输入两个整数序列。其中一个序列表示栈的push顺序，判断另一个序列有没有可能

是对应的pop顺序。为了简单起见，我们假设push序列的任意两个整数都是不相等的。

比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。

因为可以有如下的push和pop序列：push 1，push 2，push 3，push 4，pop，push 5，pop，

pop，pop，pop，这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可

能是push序列1、2、3、4、5的pop序列。

分析：这到题除了考查对栈这一基本数据结构的理解，还能考查我们的分析能力。

这道题的一个很直观的想法就是建立一个辅助栈，每次push的时候就把一个整数push进入

这个辅助栈，同样需要pop的时候就把该栈的栈顶整数pop出来。

我们以前面的序列4、5、3、2、1为例。第一个希望被pop出来的数字是4，因此4需要先

push到栈里面。由于push的顺序已经由push序列确定了，也就是在把4 push进栈之前，

数字1，2，3都需要push到栈里面。此时栈里的包含4个数字，分别是1，2，3，4，其中

4位于栈顶。把4 pop出栈后，剩下三个数字1，2，3。接下来希望被pop的是5，由于仍然

不是栈顶数字，我们接着在push序列中4以后的数字中寻找。找到数字5后再一次push进

栈，这个时候5就是位于栈顶，可以被pop出来。接下来希望被pop的三个数字是3，2，1。

每次操作前都位于栈顶，直接pop即可。

再来看序列4、3、5、1、2。pop数字4的情况和前面一样。把4 pop出来之后，3位于栈顶，

直接pop。接下来希望pop的数字是5，由于5不是栈顶数字，我们到push序列中没有被

push进栈的数字中去搜索该数字，幸运的时候能够找到5，于是把5 push进入栈。此时pop

5之后，栈内包含两个数字1、2，其中2位于栈顶。这个时候希望pop的数字是1，由于不

是栈顶数字，我们需要到push序列中还没有被push进栈的数字中去搜索该数字。但此时push

序列中所有数字都已被push进入栈，因此该序列不可能是一个pop序列。

也就是说，如果我们希望pop的数字正好是栈顶数字，直接pop出栈即可；如果希望pop

的数字目前不在栈顶，我们就到push序列中还没有被push到栈里的数字中去搜索这个数字，

并把在它之前的所有数字都push进栈。如果所有的数字都被push进栈仍然没有找到这个数

字，表明该序列不可能是一个pop序列。

基于前面的分析，我们可以写出如下的参考代码：

#include

/////////////////////////////////////////////////////////////////////

////////

// Given a push order of a stack, determine whether an array is possible

to

// be its corresponding pop order

// Input: pPush - an array of integers, the push order

// pPop - an array of integers, the pop order

// nLength - the length of pPush and pPop

// Output: If pPop is possible to be the pop order of pPush, return true.

// Otherwi return fal

/////////////////////////////////////////////////////////////////////

////////

bool IsPossiblePopOrder(const int* pPush, const int* pPop, int nLength)

{

// check every integers in pPop

while(pNextPop - pPop < nLength)

{

// while the top of the ancillary stack is not the integer

// to be poped, try to push some integers into the stack

while(() || () != *pNextPop)

{

// pNextPush == NULL means all integers have been

// pushed into the stack, can't push any longer

if(!pNextPush)

break;

// ancillary stack

std::stackstackData;

if(pPush && pPop && nLength > 0)

{

const int *pNextPush = pPush;

const int *pNextPop = pPop;

bool bPossible = fal;