程序员面试题精选 100 题(01)－把二元查找树转变成排序的 双向链表
题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任 何新的结点，只调整指针的指向。 比如将二元查找树 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。 分析：本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决，本题也不 例外。下面我们用两种不同的递归思路来分析。 思路一： 当我们到达某一结点准备调整以该结点为根结点的子树时， 先调整其左子树将 左子树转换成一个排好序的左子链表， 再调整其右子树转换右子链表。 最近链接左子链表的 最右结点（左子树的最大结点） 、当前结点和右子链表的最左结点（右子树的最小结点） 。从 树的根结点开始递归调整所有结点。 思路二：我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果 我们每访问一个结点， 假设之前访问过的结点已经调整成一个排序双向链表， 我们再把调整 当前结点的指针将其链接到链表的末尾。 当所有结点都访问过之后， 整棵树也就转换成一个 排序双向链表了。 参考代码： 首先我们定义二元查找树结点的数据结构如下： struct BSTreeNode // a node in the binary search 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-search-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 // else return the greatest node in the sub-tree /////////////////////////////////////////////////////////////////////// BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight) { if(!pNode)

return NULL; BSTreeNode *pLeft = NULL; BSTreeNode *pRight = NULL; // Convert the left sub-tree if(pNode->m_pLeft) pLeft = ConvertNode(pNode->m_pLeft, false); // 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 right sub-tree if(pNode->m_pRight) pRight = ConvertNode(pNode->m_pRight, true); // Connect the least node in the right sub-tree to the current node if(pRight) { pNode->m_pRight = pRight; pRight->m_pLeft = pNode; } BSTreeNode *pTemp = pNode; // If the current node is the right child of its parent, // return the least node in the tree whose root is the current node if(asRight) { while(pTemp->m_pLeft) pTemp = pTemp->m_pLeft; } // If the current node is the left child of its parent, // return the greatest node in the tree whose root is the current node else { while(pTemp->m_pRight) pTemp = pTemp->m_pRight; }

return pTemp; } /////////////////////////////////////////////////////////////////////// // Covert a binary search 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 set the second parameter to be true return ConvertNode(pHeadOfTree, true); } 思路二对应的代码： /////////////////////////////////////////////////////////////////////// // Covert a sub binary-search-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) { if(pNode == NULL) return; BSTreeNode *pCurrent = pNode; // Convert the left sub-tree if (pCurrent->m_pLeft != NULL) ConvertNode(pCurrent->m_pLeft, pLastNodeInList); // Put the current node into the double-linked list pCurrent->m_pLeft = pLastNodeInList; if(pLastNodeInList != NULL) pLastNodeInList->m_pRight = pCurrent; pLastNodeInList = pCurrent; // Convert the right sub-tree if (pCurrent->m_pRight != NULL) ConvertNode(pCurrent->m_pRight, pLastNodeInList); } ///////////////////////////////////////////////////////////////////////

// Covert a binary search 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) { BSTreeNode *pLastNodeInList = NULL; ConvertNode(pHeadOfTree, pLastNodeInList); // Get the head of the double-linked list BSTreeNode *pHeadOfList = pLastNodeInList; while(pHeadOfList && pHeadOfList->m_pLeft) pHeadOfList = pHeadOfList->m_pLeft; return pHeadOfList; }

程序员面试题精选 100 题(02)－设计包含min函数的栈
题目：定义栈的数据结构，要求添加一个 min 函数， 能够得到栈的最小元素。 要求函数 min、 push 以及 pop 的时间复杂度都是 O(1)。 分析：这是去年 google 的一道面试题。 我看到这道题目时，第一反应就是每次 push 一个新元素时，将栈里所有逆序元素排序。这 样栈顶元素将是最小元素。但由于不能保证最后 push 进栈的元素最先出栈，这种思路设计 的数据结构已经不是一个栈了。 在栈里添加一个成员变量存放最小元素（或最小元素的位置） 。每次 push 一个新元素进栈的 时候，如果该元素比当前的最小元素还要小，则更新最小元素。 乍一看这样思路挺好的。但仔细一想，该思路存在一个重要的问题：如果当前最小元素被 pop 出去，如何才能得到下一个最小元素？ 因此仅仅只添加一个成员变量存放最小元素（或最小元素的位置）是不够的。我们需要一个 辅助栈。每次 push 一个新元素的时候，同时将最小元素（或最小元素的位置。考虑到栈元 素的类型可能是复杂的数据结构，用最小元素的位置将能减少空间消耗）push 到辅助栈中； 每次 pop 一个元素出栈的时候，同时 pop 辅助栈。 参考代码： #include #include template class CStackWithMin { public: CStackWithMin(void) {} virtual ~CStackWithMin(void) {} T& top(void);

const T& top(void) const; void push(const T& value); void pop(void); const T& min(void) const; private: T>m_data;// theelements of stack size_t>m_minIndex;// the indicesof minimum elements }; // get the last element of mutable stack template T& CStackWithMin::top() { return m_data.back(); } // get the last element of non-mutable stack template const T& CStackWithMin::top() const { return m_data.back(); } // insert an elment at the end of stack template void CStackWithMin::push(const T& value) { // append the data into the end of m_data m_data.push_back(value); // set the index of minimum elment in m_data at the end of m_minIndex if(m_minIndex.size() == 0) m_minIndex.push_back(0); else { if(value < m_data[m_minIndex.back()]) m_minIndex.push_back(m_data.size() - 1); else m_minIndex.push_back(m_minIndex.back()); } } // erease the element at the end of stack template void CStackWithMin::pop()

{ // pop m_data m_data.pop_back(); // pop m_minIndex m_minIndex.pop_back(); } // get the minimum element of stack template const T& CStackWithMin::min() const { assert(m_data.size() > 0); assert(m_minIndex.size() > 0); return m_data[m_minIndex.back()]; } 举个例子演示上述代码的运行过程： 步骤 数据栈 辅助栈 最小值 1.push 3 3 0 3 2.push 4 3,4 0,0 3 3.push 2 3,4,2 0,0,2 2 4.push 1 3,4,2,1 0,0,2,3 1 5.pop 3,4,2 0,0,2 2 6.pop 3,4 0,0 3 7.push 0 3,4,0 0,0,2 0 讨论：如果思路正确，编写上述代码不是一件很难的事情。但如果能注意一些细节无疑能在 面试中加分。比如我在上面的代码中做了如下的工作： · 用模板类实现。如果别人的元素类型只是 int 类型，模板将能给面试官带来好印象； · 两个版本的 top 函数。 在很多类中， 都需要提供 const 和非 const 版本的成员访问函数； · min 函数中 assert。把代码写的尽量安全是每个软件公司对程序员的要求； · 添加一些注释。注释既能提高代码的可读性，又能增加代码量，何乐而不为？ 总之，在面试时如果时间允许，尽量把代码写的漂亮一些。说不定代码中的几个小亮点就能 让自己轻松拿到心仪的 Offer。

程序员面试题精选 100 题(03)－求子数组的最大和
题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个 子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为 O(n)。 例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为 3, 10, -4, 7, 2，因此输出为该子 数组的和 18。 分析： 本题最初为 2005 年浙江大学计算机系的考研题的最后一道程序设计题， 2006 年里 在 包括 google 在内的很多知名公司都把本题当作面试题。由于本题在网络中广为流传，本题 也顺利成为 2006 年程序员面试题中经典中的经典。 如果不考虑时间复杂度，我们可以枚举出所有子数组并求出他们的和。不过非常遗憾的是，

由于长度为 n 的数组有 O(n2)个子数组；而且求一个长度为 n 的数组的和的时间复杂度为 O(n)。因此这种思路的时间是 O(n3)。 很容易理解，当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果 当前得到的和是个负数， 那么这个和在接下来的累加中应该抛弃并重新清零， 不然的话这个 负数将会减少接下来的和。基于这样的思路，我们可以写出如下代码。 参考代码： ///////////////////////////////////////////////////////////////////////////// // Find the greatest sum of all sub-arrays // Return value: if the input is valid, return true, otherwise return false ///////////////////////////////////////////////////////////////////////////// bool FindGreatestSumOfSubArray ( int *pData, // an array unsigned int nLength, // the length of array int &nGreatestSum // the greatest sum of all sub-arrays ) { // if the input is invalid, return false if((pData == NULL) || (nLength == 0)) return false; int nCurSum = nGreatestSum = 0; for(unsigned int i = 0; i < nLength; ++i) { nCurSum += pData[i]; // if the current sum is negative, discard it if(nCurSum < 0) nCurSum = 0; // if a greater sum is found, update the greatest sum if(nCurSum > nGreatestSum) nGreatestSum = nCurSum; } // 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]; }

} return true; } 讨论：上述代码中有两点值得和大家讨论一下： · 函数的返回值不是子数组和的最大值，而是一个判断输入是否有效的标志。如果函数 返回值的是子数组和的最大值，那么当输入一个空指针是应该返回什么呢？返回 0？那这个 函数的用户怎么区分输入无效和子数组和的最大值刚好是 0 这两中情况呢？基于这个考虑， 本人认为把子数组和的最大值以引用的方式放到参数列表中， 同时让函数返回一个函数是否 正常执行的标志。 · 输入有一类特殊情况需要特殊处理。当输入数组中所有整数都是负数时，子数组和的 最大值就是数组中的最大元素。

程序员面试题精选 100 题(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 whose 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(!pTreeNode) return; currentSum += pTreeNode->m_nValue; path.push_back(pTreeNode->m_nValue); // 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) { std::vector::iterator iter =path.begin(); for(; iter != path.end(); ++ iter) std::cout 0) left = verifySquenceOfBST(squence, i); // verify whether the right sub-tree is a BST bool right = true; if(i < length - 1) right = verifySquenceOfBST(squence + i, length - i - 1); return (left && right); }

程序员面试题精选 100 题(07)－翻转句子中单词的顺序
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词 以空格符隔开。为简单起见，标点符号和普通字母一样处理。 例如输入“I am a student.” ，则输出“student. a am I” 。 分析： 由于编写字符串相关代码能够反映程序员的编程能力和编程习惯， 与字符串相关的问 题一直是程序员笔试、 面试题的热门题目。 本题也曾多次受到包括微软在内的大量公司的青 睐。 由于本题需要翻转句子，我们先颠倒句子中的所有字符。这时，不但翻转了句子中单词的顺 序，而且单词内字符也被翻转了。我们再颠倒每个单词内的字符。由于单词内的字符被翻转 两次，因此顺序仍然和输入时的顺序保持一致。 还是以上面的输入为例子。翻转“I am a student.”中所有字符得到“.tneduts a ma I” ，再翻 转每个单词中字符的顺序得到“students. a am I” ，正是符合要求的输出。 参考代码： /////////////////////////////////////////////////////////////////////// // Reverse a string between two pointers // Input: pBegin - the begin pointer in a string // pEnd - the end pointer in a string /////////////////////////////////////////////////////////////////////// void Reverse(char *pBegin, char *pEnd) { if(pBegin == NULL || pEnd == NULL) return; while(pBegin < pEnd) { char temp = *pBegin; *pBegin = *pEnd; *pEnd = temp; pBegin ++, pEnd --; } } /////////////////////////////////////////////////////////////////////// // Reverse the word order in a sentence, but maintain the character // order inside a word // Input: pData - the sentence to be reversed /////////////////////////////////////////////////////////////////////// char* ReverseSentence(char *pData) { if(pData == NULL) return NULL;

char *pBegin = pData; char *pEnd = pData; while(*pEnd != '\0') pEnd ++; pEnd--; // Reverse the whole sentence Reverse(pBegin, pEnd); // Reverse every word in the sentence pBegin = pEnd = pData; while(*pBegin != '\0') { if(*pBegin == ' ') { pBegin ++; pEnd ++; continue; } // A word is between with pBegin and pEnd, reverse it else if(*pEnd == ' ' || *pEnd == '\0') { Reverse(pBegin, --pEnd); pBegin = ++pEnd; } else { pEnd ++; } } return pData; }

程序员面试题精选 100 题(08)－求 1+2+...+n
题目：求 1+2+…+n，要求不能使用乘除法、for、while、if、else、switch、case 等关键字以 及条件判断语句（A?B:C） 。 分析：这道题没有多少实际意义，因为在软件开发中不会有这么变态的限制。但这道题却能 有效地考查发散思维能力，而发散思维能力能反映出对编程相关技术理解的深刻程度。 通常求 1+2+…+n 除了用公式 n(n+1)/2 之外，无外乎循环和递归两种思路。由于已经明确限 制 for 和 while 的使用，循环已经不能再用了。同样，递归函数也需要用 if 语句或者条件判 断语句来判断是继续递归下去还是终止递归，但现在题目已经不允许使用这两种语句了。

我们仍然围绕循环做文章。循环只是让相同的代码执行 n 遍而已，我们完全可以不用 for 和 while 达到这个效果。比如定义一个类，我们 new 一含有 n 个这种类型元素的数组，那么该 类的构造函数将确定会被调用 n 次。 我们可以将需要执行的代码放到构造函数里。 如下代码 正是基于这个思路： class Temp { public: Temp() { ++ N; Sum += N; } static void Reset() { N = 0; Sum = 0; } static int GetSum() { return Sum; } private: static int N; static int Sum; }; int Temp::N = 0; int Temp::Sum = 0; int solution1_Sum(int n) { Temp::Reset(); Temp *a = new Temp[n]; delete []a; a = 0; return Temp::GetSum(); } 我们同样也可以围绕递归做文章。 既然不能判断是不是应该终止递归， 我们不妨定义两个函 数。一个函数充当递归函数的角色，另一个函数处理终止递归的情况，我们需要做的就是在 两个函数里二选一。从二选一我们很自然的想到布尔变量，比如 ture（1）的时候调用第一 个函数，false（0）的时候调用第二个函数。那现在的问题是如和把数值变量 n 转换成布尔 值。如果对 n 连续做两次反运算，即!!n，那么非零的 n 转换为 true，0 转换为 false。有了上 述分析，我们再来看下面的代码： class A; A* Array[2]; class A { public: virtual int Sum (int n) { return 0; } };

class B: public A { public: virtual int Sum (int n) { return Array[!!n]->Sum(n-1)+n; } }; int solution2_Sum(int n) { A a; B b; Array[0] = &a; Array[1] = &b; int value = Array[1]->Sum(n); return value; } 这种方法是用虚函数来实现函数的选择。当 n 不为零时，执行函数 B::Sum；当 n 为 0 时， 执行 A::Sum。我们也可以直接用函数指针数组，这样可能还更直接一些： typedef int (*fun)(int); int solution3_f1(int i) { return 0; } int solution3_f2(int i) { fun f[2]={solution3_f1, solution3_f2}; return i+f[!!i](i-1); } 另外我们还可以让编译器帮我们来完成类似于递归的运算，比如如下代码： template struct solution4_Sum { enum Value { N = solution4_Sum::N + n}; }; template struct solution4_Sum { enum Value { N = 1}; }; solution4_Sum::N 就是 1+2+...+100 的结果。当编译器看到 solution4_Sum时，就 是为模板类 solution4_Sum 以参数 100 生成该类型的代码。但以 100 为参数的类型需要得到 以 99 为参数的类型，因为 solution4_Sum::N=solution4_Sum::N+100。这个过程会

递归一直到参数为 1 的类型，由于该类型已经显式定义，编译器无需生成，递归编译到此结 束。由于这个过程是在编译过程中完成的，因此要求输入 n 必须是在编译期间就能确定，不 能动态输入。这是该方法最大的缺点。而且编译器对递归编译代码的递归深度是有限制的， 也就是要求 n 不能太大。 大家还有更多、更巧妙的思路吗？欢迎讨论^_^

程序员面试题精选 100 题(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) { pCur = pCur->m_pNext; nNum ++; } // if the number of nodes in the list is less than k // do nothing if(nNum < k) return NULL; // 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) { if(pListHead == NULL) return NULL; ListNode *pAhead = pListHead; ListNode *pBehind = NULL; for(unsigned int i = 0; i < k; ++ i) { if(pAhead->m_pNext != NULL) pAhead = pAhead->m_pNext; else

{ // if the number of nodes in the list is less than k, // do nothing return NULL; } } 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) { pAhead = pAhead->m_pNext; pBehind = pBehind->m_pNext; } return pBehind; } 讨论：这道题的代码有大量的指针操作。在软件开发中，错误的指针操作是大部分问题的根 源。 因此每个公司都希望程序员在操作指针时有良好的习惯， 比如使用指针之前判断是不是 空指针。这些都是编程的细节，但如果这些细节把握得不好，很有可能就会和心仪的公司失 之交臂。 另外， 这两种思路对应的代码都含有循环。 含有循环的代码经常出的问题是在循环结束条件 的判断。是该用小于还是小于等于？是该用 k 还是该用 k-1？由于题目要求的是从 0 开始计 数，而我们的习惯思维是从 1 开始计数，因此首先要想好这些边界条件再开始编写代码，再 者要在编写完代码之后再用边界值、边界值减 1、边界值加 1 都运行一次（在纸上写代码就 只能在心里运行了） 。 扩展：和这道题类似的题目还有：输入一个单向链表。如果该链表的结点数为奇数，输出中 间的结点；如果链表结点数为偶数，输出中间两个结点前面的一个。如果各位感兴趣，请自 己分析并编写代码。

程序员面试题精选 100 题(10)－在排序数组中查找和为给定 值的两个数字
题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和 正好是输入的那个数字。要求时间复杂度是 O(n)。如果有多对数字的和等于输入的数字， 输出任意一对即可。 例如输入数组 1、2、4、7、11、15 和数字 15。由于 4+11=15，因此输出 4 和 11。 分析：如果我们不考虑时间复杂度，最简单想法的莫过去先在数组中固定一个数字，再依次 判断数组中剩下的 n-1 个数字与它的和是不是等于输入的数字。 可惜这种思路需要的时间复 杂度是 O(n2)。

我们假设现在随便在数组中找到两个数。如果它们的和等于输入的数字，那太好了，我们找 到了要找的两个数字； 如果小于输入的数字呢？我们希望两个数字的和再大一点。 由于数组 已经排好序了， 我们是不是可以把较小的数字的往后面移动一个数字？因为排在后面的数字 要大一些，那么两个数字的和也要大一些，就有可能等于输入的数字了；同样，当两个数字 的和大于输入的数字的时候， 我们把较大的数字往前移动， 因为排在数组前面的数字要小一 些，它们的和就有可能等于输入的数字了。 我们把前面的思路整理一下： 最初我们找到数组的第一个数字和最后一个数字。 当两个数字 的和大于输入的数字时，把较大的数字往前移动；当两个数字的和小于数字时，把较小的数 字往后移动；当相等时，打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。 问题是这样的思路是不是正确的呢？这需要严格的数学证明。 感兴趣的读者可以自行证明一 下。 参考代码： /////////////////////////////////////////////////////////////////////// // Find two numbers with a sum in a sorted array // Output: ture is found such two numbers, otherwise false /////////////////////////////////////////////////////////////////////// bool FindTwoNumbersWithSum ( 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 second number, output ) { bool found = false; if(length < 1) return found; int ahead = length - 1; int behind = 0; while(ahead > behind) { long long curSum = data[ahead] + data[behind]; // if the sum of two numbers is equal to the input // we have found them if(curSum == sum) { num1 = data[behind]; num2 = data[ahead]; found = true; break;

} // if the sum of two numbers is greater than the input // decrease the greater number else if(curSum > sum) ahead --; // if the sum of two numbers is less than the input // increase the less number else behind ++; } return found; } 扩展：如果输入的数组是没有排序的，但知道里面数字的范围，其他条件不变，如和在 O(n) 时间里找到这两个数字？

程序员面试题精选 100 题(11)－求二元查找树的镜像
题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树 的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。 例如输入： 8 / \ 6 10 /\ /\ 5 7 9 11 输出： 8 / \ 10 6 /\ /\ 11 9 7 5 定义二元查找树的结点为： struct BSTreeNode // a node in the binary search tree (BST) { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 分析：尽管我们可能一下子不能理解镜像是什么意思，但上面的例子给我们的直观感觉，就 是交换结点的左右子树。 我们试着在遍历例子中的二元查找树的同时来交换每个结点的左右 子树。遍历时首先访问头结点 8，我们交换它的左右子树得到： 8 / \

6 /\ /\ 9 11 5 7 我们发现两个结点 6 和 10 的左右子树仍然是左结点的值小于右结点的值，我们再试着交换 他们的左右子树，得到： 8 / \ 10 6 /\ /\ 11 9 7 5 刚好就是要求的输出。 上面的分析印证了我们的直觉： 在遍历二元查找树时每访问到一个结点， 交换它的左右子树。 这种思路用递归不难实现，将遍历二元查找树的代码稍作修改就可以了。参考代码如下： /////////////////////////////////////////////////////////////////////// // Mirror a BST (swap the left right child of each node) recursively // the head of BST in initial call /////////////////////////////////////////////////////////////////////// void MirrorRecursively(BSTreeNode *pNode) { if(!pNode) return; // swap the right and left child sub-tree BSTreeNode *pTemp = pNode->m_pLeft; pNode->m_pLeft = pNode->m_pRight; pNode->m_pRight = pTemp; // mirror left child sub-tree if not null if(pNode->m_pLeft) MirrorRecursively(pNode->m_pLeft); // mirror right child sub-tree if not null if(pNode->m_pRight) MirrorRecursively(pNode->m_pRight); } 由于递归的本质是编译器生成了一个函数调用的栈， 因此用循环来完成同样任务时最简单的 办法就是用一个辅助栈来模拟递归。首先我们把树的头结点放入栈中。在循环中，只要栈不 为空，弹出栈的栈顶结点，交换它的左右子树。如果它有左子树，把它的左子树压入栈中； 如果它有右子树， 把它的右子树压入栈中。 这样在下次循环中就能交换它儿子结点的左右子 树了。参考代码如下： /////////////////////////////////////////////////////////////////////// // Mirror a BST (swap the left right child of each node) Iteratively // Input: pTreeHead: the head of BST ///////////////////////////////////////////////////////////////////////

10

void MirrorIteratively(BSTreeNode *pTreeHead) { if(!pTreeHead) return; std::stackstackTreeNode; stackTreeNode.push(pTreeHead); while(stackTreeNode.size()) { BSTreeNode *pNode = stackTreeNode.top(); stackTreeNode.pop(); // swap the right and left child sub-tree BSTreeNode *pTemp = pNode->m_pLeft; pNode->m_pLeft = pNode->m_pRight; pNode->m_pRight = pTemp; // push left child sub-tree into stack if not null if(pNode->m_pLeft) stackTreeNode.push(pNode->m_pLeft); // push right child sub-tree into stack if not null if(pNode->m_pRight) stackTreeNode.push(pNode->m_pRight); } }

程序员面试题精选 100 题(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 { int m_nValue; // value of node BTreeNode *m_pLeft; // left child of node BTreeNode *m_pRight; // right child of node }; /////////////////////////////////////////////////////////////////////// // Print a binary tree from top level to bottom level // Input: pTreeRoot - the root of binary tree /////////////////////////////////////////////////////////////////////// void PrintFromTopToBottom(BTreeNode *pTreeRoot) { if(!pTreeRoot) return; // get a empty queue deque dequeTreeNode; // insert the root at the tail of queue dequeTreeNode.push_back(pTreeRoot); while(dequeTreeNode.size()) { // get a node from the head of queue BTreeNode *pNode = dequeTreeNode.front(); dequeTreeNode.pop_front(); // print the node cout m_nValue m_pLeft) dequeTreeNode.push_back(pNode->m_pLeft); // print its right child sub-tree if it has if(pNode->m_pRight) dequeTreeNode.push_back(pNode->m_pRight); } }

程序员面试题精选 100 题(13)－第一个只出现一次的字符
题目：在一个字符串中找到第一个只出现一次的字符。如输入 abaccdeff，则输出 b。 分析：这道题是 2006 年 google 的一道笔试题。 看到这道题时， 最直观的想法是从头开始扫描这个字符串中的每个字符。 当访问到某字符时 拿这个字符和后面的每个字符相比较， 如果在后面没有发现重复的字符， 则该字符就是只出 现一次的字符。如果字符串有 n 个字符，每个字符可能与后面的 O(n)个字符相比较，因此 这种思路时间复杂度是 O(n2)。我们试着去找一个更快的方法。 由于题目与字符出现的次数相关， 我们是不是可以统计每个字符在该字符串中出现的次数？ 要达到这个目的， 我们需要一个数据容器来存放每个字符的出现次数。 在这个数据容器中可 以根据字符来查找它出现的次数，也就是说这个容器的作用是把一个字符映射成一个数字。 在常用的数据容器中，哈希表正是这个用途。 哈希表是一种比较复杂的数据结构。由于比较复杂，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, otherwise 0 /////////////////////////////////////////////////////////////////////// char FirstNotRepeatingChar(char* pString) { // invalid input if(!pString) return 0; // get a hash table, and initialize it constinttableSize =256;

unsignedinthashTable[tableSize]; for(unsignedinti = 0; i 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, // otherwise -1 /////////////////////////////////////////////////////////////////////// int LastRemaining_Solution1(unsigned int n, unsigned int m) { // invalid input if(n < 1 || m < 1) return -1; unsigned int i = 0;

// initiate a list with n integers (0, 1, ... n - 1) list integers; for(i = 0; i < n; ++ i) integers.push_back(i); list::iterator curinteger = integers.begin(); while(integers.size() > 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 == integers.end()) curinteger = integers.begin(); } // remove the mth integer. Note that std::list is not a circle // so we should handle it manually list::iterator nextinteger = ++ curinteger; if(nextinteger == integers.end()) nextinteger = integers.begin(); -- curinteger; integers.erase(curinteger); curinteger = nextinteger; } return *(curinteger); } 思路二的参考代码： /////////////////////////////////////////////////////////////////////// // 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, // otherwise -1 /////////////////////////////////////////////////////////////////////// int LastRemaining_Solution2(int n, unsigned int m) { // invalid input if(n 0) { data = new T[size]; for(int i = 0; i < size; ++ i) setValue(i, copy.getValue(i)); } }

const Array& operator = (const Array& copy) { if(this == ©) return *this; if(data != NULL) { delete []data; data = NULL; } size = copy.size; if(size > 0) { data = new T[size]; for(int i = 0; i < size; ++ i) setValue(i, copy.getValue(i)); } } 为了防止有多个指针指向的数据被多次删除，我们还可以保存究竟有多少个指针指向该数 据。 只有当没有任何指针指向该数据的时候才可以被删除。 这种思路通常被称之为引用计数 技术。在构造函数中，引用计数初始化为 1；每当把这个实例赋值给其他实例或者以参数传 给其他实例的构造拷贝函数的时候，引用计数加 1，因为这意味着又多了一个实例指向它的 data；每次需要调用析构函数或者需要把 data 赋值为其他数据的时候，引用计数要减 1，因 为这意味着指向它的 data 的指针少了一个。当引用计数减少到 0 的时候，data 已经没有任 何实例指向它了，这个时候就可以安全地删除。实现的代码如下： public: Array(unsigned arraySize) :data(0), size(arraySize), count(new unsigned int) { *count = 1; if(size > 0) data = new T[size]; } Array(const Array& copy) : size(copy.size), data(copy.data), count(copy.count) { ++ (*count); } ~Array() { Release();

} const Array& operator = (const Array& copy) { if(data == copy.data) return *this; Release(); data = copy.data; size = copy.size; count = copy.count; ++(*count); } private: void Release() { --(*count); if(*count == 0) { if(data) { delete []data; data = NULL; } delete count; count = 0; } } unsigned int *count;

程序员面试题精选 100 题(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) { int result[2] = {0, 1}; if(n < 2) return result[n]; return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2); } 但是，教科书上反复用这个题目来讲解递归函数，并不能说明递归解法最适合这道题目。我 们以求解 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) { int result[2] = {0, 1}; if(n < 2) return result[n]; long long fibNMinusOne = 1; long long fibNMinusTwo = 0; long long fibN = 0; for(unsigned int i = 2; i 0); Matrix2By2 matrix; if(n == 1) { matrix = Matrix2By2(1, 1, 1, 0); } else if(n % 2 == 0) { matrix = MatrixPower(n / 2); matrix = MatrixMultiply(matrix, matrix); } else if(n % 2 == 1)

{ matrix = MatrixPower((n - 1) / 2); matrix = MatrixMultiply(matrix, matrix); matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0)); } return matrix; } /////////////////////////////////////////////////////////////////////// // 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]; Matrix2By2 PowerNMinus2 = MatrixPower(n - 1); return PowerNMinus2.m_00; }

程序员面试题精选 100 题(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) { g_nStatus = kInvalid; longlongnum = 0; if(str != NULL) { const char* digit = str; // the first char in the string maybe '+' or '-' bool minus = false; if(*digit == '+') digit ++; else if(*digit == '-') { digit ++; minus = true; } // the remaining chars in the string while(*digit != '\0')

{ if(*digit >= '0' && *digit std::numeric_limits::max()) { num = 0; break; } digit++; } // if the char is not a digit, invalid input else { 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)。该函数就是用一个全局变量来标志输入是否合法的。

程序员面试题精选 100 题(18)－用两个栈实现队列
题目：某队列的声明如下： template class CQueue

{ public: CQueue() {} ~CQueue() {} void appendTail(const T& node); // append a element to tail void deleteHead(); // remove a element from head private: T>m_stack1; T>m_stack2; }; 分析：从上面的类的声明中，我们发现在队列中有两个栈。因此这道题实质上是要求我们用 两个栈来实现一个队列。 相信大家对栈和队列的基本性质都非常了解了： 栈是一种后入先出 的数据容器， 因此对队列进行的插入和删除操作都是在栈顶上进行； 队列是一种先入先出的 数据容器，我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。 我们通过一个具体的例子来分析往该队列插入和删除元素的过程。首先插入一个元素 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 如果 m_stack2 为空时， 我们把 m_stack1 中的栈顶元素是最先进入队列的元素， 可以 pop 出去。 中的元素逐个 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 m_stack1 {a} {a,b} m_stack2 {} {}

append c delete head delete head append d delete head

{a,b,c} {} {} {d} {d}

{} {b,c} {c} {c} {}

总结完 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_stack1.push(element); } /////////////////////////////////////////////////////////////////////// // Delete the head from the queue /////////////////////////////////////////////////////////////////////// template void CQueue::deleteHead() { // if m_stack2is empty, // and thereare some elements in m_stack1, push them in m_stack2 if(m_stack2.size()0) { T&data =m_stack1.top(); m_stack1.pop(); m_stack2.push(data); } } // push theelement into m_stack2 assert(m_stack2.size()>0); m_stack2.pop(); } 扩展：这道题是用两个栈实现一个队列。反过来能不能用两个队列实现一个栈。如果可以， 该如何实现？

程序员面试题精选 100 题(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 为空指针的结点。 基于上述分析，我们不难写出如下代码： /////////////////////////////////////////////////////////////////////// // Reverse a list iteratively // Input: pHead - the head of the original list // Output: the head of the reversed head /////////////////////////////////////////////////////////////////////// ListNode* ReverseIteratively(ListNode* pHead) { ListNode* pReversedHead = NULL; ListNode* pNode = pHead; ListNode* pPrev = NULL; while(pNode != NULL) { // get the next node, and save it at pNext ListNode* pNext = pNode->m_pNext; // if the next node is null, the currect is the end of original // list, and it's the head of the reversed list if(pNext == NULL) pReversedHead = pNode; // reverse the linkage between nodes

pNode->m_pNext = pPrev; // move forward on the the list pPrev = pNode; pNode = pNext; } return pReversedHead; } 扩展：本题也可以递归实现。感兴趣的读者请自己编写递归代码。

程序员面试题精选 100 题(20)－最长公共子串
题目： 如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中， 则字符 串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符 串二中。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子 串。 例如：输入两个字符串 BDCABA 和 ABCBDAB，字符串 BCBA 和 BDAB 都是是它们的最 长公共子串，则输出它们的长度 4，并打印任意一个子串。 分析： 求最长公共子串 （Longest Common Subsequence, LCS） 是一道非常经典的动态规划题， 因此一些重视算法的公司像 MicroStrategy 都把它当作面试题。 完整介绍动态规划将需要很长的篇幅， 因此我不打算在此全面讨论动态规划相关的概念， 只 集中对 LCS 直接相关内容作讨论。如果对动态规划不是很熟悉，请参考相关算法书比如算 法讨论。 先介绍 LCS 问题的性质：记 Xm={x0, x1,…xm-1}和 Yn={y0,y1,…,yn-1}为两个字符串，而 Zk={z0,z1,…zk-1}是它们的 LCS，则： 1. 如果 xm-1=yn-1，那么 zk-1=xm-1=yn-1，并且 Zk-1 是 Xm-1 和 Yn-1 的 LCS； 2. 如果 xm-1≠yn-1，那么当 zk-1≠xm-1 时 Z 是 Xm-1 和 Y 的 LCS； 3. 如果 xm-1≠yn-1，那么当 zk-1≠yn-1 时 Z 是 Yn-1 和 X 的 LCS； 下面简单证明一下这些性质： 1. 如果 zk-1≠xm-1，那么我们可以把 xm-1（yn-1）加到 Z 中得到 Z’，这样就得到 X 和 Y 的一个长度为 k+1 的公共子串 Z’。这就与长度为 k 的 Z 是 X 和 Y 的 LCS 相矛盾了。因此 一定有 zk-1=xm-1=yn-1。 既然 zk-1=xm-1=yn-1，那如果我们删除 zk-1（xm-1、yn-1）得到的 Zk-1，Xm-1 和 Yn-1， 显然 Zk-1 是 Xm-1 和 Yn-1 的一个公共子串，现在我们证明 Zk-1 是 Xm-1 和 Yn-1 的 LCS。 用反证法不难证明。假设有 Xm-1 和 Yn-1 有一个长度超过 k-1 的公共子串 W，那么我们把 加到 W 中得到 W’，那 W’就是 X 和 Y 的公共子串，并且长度超过 k，这就和已知条件相矛 盾了。 还是用反证法证明。假设 Z 不是 Xm-1 和 Y 的 LCS，则存在一个长度超过 k 的 W 是 2. Xm-1 和 Y 的 LCS，那 W 肯定也 X 和 Y 的公共子串，而已知条件中 X 和 Y 的公共子串的 最大长度为 k。矛盾。 3. 证明同 2。 有 了 上 面 的 性 质 ， 我 们 可 以 得 出 如 下 的 思 路 ： 求 两 字 符 串 Xm={x0, x1,…xm-1} 和 Yn={y0,y1,…,yn-1}的 LCS，如果 xm-1=yn-1，那么只需求得 Xm-1 和 Yn-1 的 LCS，并在其

后添加 xm-1（yn-1）即可；如果 xm-1≠yn-1，我们分别求得 Xm-1 和 Y 的 LCS 和 Yn-1 和 X 的 LCS，并且这两个 LCS 中较长的一个为 X 和 Y 的 LCS。 如果我们记字符串 Xi 和 Yj 的 LCS 的长度为 c[i,j]，我们可以递归地求 c[i,j]： / 0 if i=0 and xi≠xj 上面的公式用递归函数不难求得。 但从前面求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 decreaseDir {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 second string // Output: the length of two strings' LCSs ///////////////////////////////////////////////////////////////////////////// int LCS(char* pStr1, char* pStr2) { if(!pStr1 || !pStr2) return 0; size_t length1 = strlen(pStr1); size_t length2 = strlen(pStr2); if(!length1 || !length2) return 0; size_t i, j; // initiate the length matrix int **LCS_length; LCS_length = (int**)(new int[length1]); for(i = 0; i < length1; ++ i) LCS_length[i] = (int*)new int[length2];

for(i = 0; i < length1; ++ i) for(j = 0; j < length2; ++ j) LCS_length[i][j] = 0; // initiate the direction matrix int **LCS_direction; LCS_direction = (int**)(new int[length1]); for( i = 0; i < length1; ++ i) 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) { for(j = 0; j < length2; ++ j) { if(i == 0 || j == 0) { if(pStr1[i] == pStr2[j]) { LCS_length[i][j] = 1; LCS_direction[i][j] = kLeftUp; } else LCS_length[i][j] = 0; } // a char of LCS is found, // it comes from the left up entry in the direction matrix else if(pStr1[i] == pStr2[j]) { LCS_length[i][j] = LCS_length[i - 1][j - 1] + 1; LCS_direction[i][j] = kLeftUp; } // it comes from the up entry in the direction matrix else if(LCS_length[i - 1][j] > LCS_length[i][j - 1]) { LCS_length[i][j] = LCS_length[i - 1][j]; LCS_direction[i][j] = kUp; } // it comes from the left entry in the direction matrix else {

LCS_length[i][j] = LCS_length[i][j - 1]; LCS_direction[i][j] = kLeft; } } } LCS_Print(LCS_direction, pStr1, pStr2, length1 - 1, length2 - 1); return LCS_length[length1 - 1][length2 - 1]; } ///////////////////////////////////////////////////////////////////////////// // 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 second 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, char* pStr1, char* pStr2, size_t row, size_t col) { if(pStr1 == NULL || pStr2 == NULL) return; size_t length1 = strlen(pStr1); size_t length2 = strlen(pStr2); if(length1 == 0 || length2 == 0 || !(row < length1 && col < length2)) return; // kLeftUp implies a char in the LCS is found if(LCS_direction[row][col] == kLeftUp) { if(row > 0 && col > 0) LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col - 1); // print the char printf("%c", pStr1[row]); } else if(LCS_direction[row][col] == kLeft) { // move to the left entry in the direction matrix

if(col > 0) LCS_Print(LCS_direction, pStr1, pStr2, row, col - 1); } else if(LCS_direction[row][col] == kUp) { // move to the up entry in the direction matrix if(row > 0) LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col); } } 扩展： 如果题目改成求两个字符串的最长公共子字符串， 应该怎么求？子字符串的定义和子 串的定义类似，但要求是连续分布在其他字符串中。比如输入两个字符串 BDCABA 和 ABCBDAB 的最长公共字符串有 BD 和 AB，它们的长度都是 2。

程序员面试题精选 100 题(21)－左旋转字符串（同第 7 题）
题目：定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。如把字 符串 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 翻转后 记为 XT。显然有(XT)T=X。 我们首先对 X 和 Y 两段分别进行翻转操作，这样就能得到 XTYT。接着再对 XTYT 进行翻 转操作，得到(XTYT)T=(YT)T(XT)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) { 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; // reverse the first part of the string ReverseString(pFirstStart, pFirstEnd); // reverse the second part of the strint ReverseString(pSecondStart, pSecondEnd); // reverse the whole string ReverseString(pFirstStart, pSecondEnd); } } return pStr; } /////////////////////////////////////////////////////////////////////// // Reverse the string between pStart and pEnd /////////////////////////////////////////////////////////////////////// void ReverseString(char* pStart, char* pEnd) { if(pStart == NULL || pEnd == NULL) { while(pStart 1 F(m) = m 的最高位*G(n) + m 去了最高位后剩下的数字 + F(m 去了最高位后剩下的数字)， 若 m 最高位 n) { sum -= small; small ++; // we are lucky and find the sequence

if(sum == n) PrintContinuousSequence(small, big); } // move big forward big ++; sum += big; } } ///////////////////////////////////////////////////////////////////////// // Print continuous sequence between small and big ///////////////////////////////////////////////////////////////////////// void PrintContinuousSequence(int small, int big) { for(int i = small; i m_pLeft); // the depth of right sub-tree int nRight = TreeDepth(pTreeNode->m_pRight); // depth is the binary tree return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1); }

程序员面试题精选 100 题(28)-字符串的排列
题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串 abc，则输出 由字符 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。 分析： 这是一道很好的考查对递归理解的编程题， 因此在过去一年中频繁出现在各大公司的 面试、笔试题中。 我们以三个字符 abc 为例来分析一下求字符串排列的过程。首先我们固定第一个字符 a，求 后面两个字符 bc 的排列。当两个字符 bc 的排列求好之后，我们把第一个字符 a 和后面的 b 交换，得到 bac，接着我们固定第一个字符 b，求后面两个字符 ac 的排列。现在是把 c 放到 第一位置的时候了。记住前面我们已经把原先的第一个字符 a 和后面的 b 做了交换，为了保 证这次 c 仍然是和原先处在第一位置的 a 交换，我们在拿 c 和第一个字符交换之前，先要把 b 和 a 交换回来。在交换 b 和 a 之后，再拿 c 和处在第一位置的 a 进行交换，得到 cba。我 们再次固定第一个字符 c，求后面两个字符 b、a 的排列。 既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排 列，就是典型的递归思路了。 基于前面的分析，我们可以得到如下的参考代码： void Permutation(char* pStr, char* pBegin); ///////////////////////////////////////////////////////////////////////// // Get the permutation of a string,

// for example, input string abc, its permutation is // abc acb bac bca cba cab ///////////////////////////////////////////////////////////////////////// void Permutation(char* pStr) { Permutation(pStr, pStr); } ///////////////////////////////////////////////////////////////////////// // Print the permutation of a string, // Input: pStr - input string // pBegin - points to the begin char of string // which we want to permutate in this recursion ///////////////////////////////////////////////////////////////////////// void Permutation(char* pStr, char* pBegin) { if(!pStr || !pBegin) return; // if pBegin points to the end of string, // this round of permutation is finished, // print the permuted string if(*pBegin == '\0') { printf("%s\n", pStr); } // otherwise, permute string else { for(char* pCh = pBegin; *pCh != '\0'; ++ pCh) { // swap pCh and pBegin char temp = *pCh; *pCh = *pBegin; *pBegin = temp; Permutation(pStr, pBegin + 1); // restore pCh and pBegin temp = *pCh; *pCh = *pBegin; *pBegin = temp; } }

} 扩展 1：如果不是求字符的所有排列，而是求字符的所有组合，应该怎么办呢？当输入的字 符串中含有相同的字符串时，相同的字符交换位置是不同的排列，但是同一个组合。举个例 子，如果输入 aaa，那么它的排列是 6 个 aaa，但对应的组合只有一个。 扩展 2：输入一个含有 8 个数字的数组，判断有没有可能把这 8 个数字分别放到正方体的 8 个顶点上，使得正方体上三组相对的面上的 4 个顶点的和相等。

程序员面试题精选 100 题(29)-调整数组顺序使奇数位于偶数 前面
题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，所 有偶数位于数组的后半部分。要求时间复杂度为 O(n)。 分析： 如果不考虑时间复杂度， 最简单的思路应该是从头扫描这个数组， 每碰到一个偶数时， 拿出这个数字， 并把位于这个数字后面的所有数字往前挪动一位。 挪完之后在数组的末尾有 一个空位，这时把该偶数放入这个空位。由于碰到一个偶数，需要移动 O(n)个数字，因此 总的时间复杂度是 O(n２)。 要求的是把奇数放在数组的前半部分， 偶数放在数组的后半部分， 因此所有的奇数应该位于 偶数的前面。也就是说我们在扫描这个数组的时候，如果发现有偶数出现在奇数的前面，我 们可以交换他们的顺序，交换之后就符合要求了。 因此我们可以维护两个指针，第一个指针初始化为数组的第一个数字，它只向后移动；第二 个指针初始化为数组的最后一个数字，它只向前移动。在两个指针相遇之前，第一个指针总 是位于第二个指针的前面。 如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇 数，我们就交换这两个数字。 基于这个思路，我们可以写出如下的代码： void Reorder(int *pData, unsigned int length, bool (*func)(int)); bool isEven(int n); ///////////////////////////////////////////////////////////////////////// // Devide an array of integers into two parts, odd in the first part, // and even in the second part // Input: pData - an array of integers // length - the length of array ///////////////////////////////////////////////////////////////////////// void ReorderOddEven(int *pData, unsigned int length) { if(pData == NULL || length == 0) return; Reorder(pData, length, isEven); } ///////////////////////////////////////////////////////////////////////// // Devide an array of integers into two parts, the intergers which

// satisfy func in the first part, otherwise in the second part // Input: pData - an array of integers // length - the length of array // func - a function ///////////////////////////////////////////////////////////////////////// void Reorder(int *pData, unsigned int length, bool (*func)(int)) { if(pData == NULL || length == 0) return; int *pBegin = pData; int *pEnd = pData + length - 1; while(pBegin < pEnd) { // if *pBegin does not satisfy func, move forward if(!func(*pBegin)) { pBegin ++; continue; } // if *pEnd does not satisfy func, move backward if(func(*pEnd)) { pEnd --; continue; } // if *pBegin satisfy func while *pEnd does not, // swap these integers int temp = *pBegin; *pBegin = *pEnd; *pEnd = temp; } } ///////////////////////////////////////////////////////////////////////// // Determine whether an integer is even or not // Input: an integer // otherwise return false ///////////////////////////////////////////////////////////////////////// bool isEven(int n) {

return (n & 1) == 0; } 讨论： 上面的代码有三点值得提出来和大家讨论： １．函数 isEven 判断一个数字是不是偶数并没有用%运算符而是用&。理由是通常情况下位 运算符比%要快一些； ２．这道题有很多变种。这里要求是把奇数放在偶数的前面，如果把要求改成：把负数放在 非负数的前面等，思路都是都一样的。 ３． 在函数 Reorder 中， 用函数指针 func 指向的函数来判断一个数字是不是符合给定的条件， 而不是用在代码直接判断（hard code） 。这样的好处是把调整顺序的算法和调整的标准分开 了（即解耦，decouple） 。当调整的标准改变时，Reorder 的代码不需要修改，只需要提供一 个新的确定调整标准的函数即可， 提高了代码的可维护性。 例如要求把负数放在非负数的前 面，我们不需要修改 Reorder 的代码，只需添加一个函数来判断整数是不是非负数。这样的 思路在很多库中都有广泛的应用， 比如在ＳＴＬ的很多算法函数中都有一个仿函数 （functor） 的参数（当然仿函数不是函数指针，但其思想是一样的） 。如果在面试中能够想到这一层， 无疑能给面试官留下很好的印象。

程序员面试题精选 100 题(30)-异常安全的赋值运算符重载函 数
题目：类 CMyString 的声明如下： class CMyString { public: CMyString(char* pData = NULL); CMyString(const CMyString& str); ~CMyString(void); CMyString& operator = (const CMyString& str); private: char* m_pData; }; 请实现其赋值运算符的重载函数，要求异常安全，即当对一个对象进行赋值时发生异常，对 象的状态不能改变。 分析：首先我们来看一般 C++教科书上给出的赋值运算符的重载函数： CMyString& CMyString::operator =(const CMyString &str) { if(this == &str) return *this; delete []m_pData; m_pData = NULL;

m_pData = new char[strlen(str.m_pData) + 1]; strcpy(m_pData, str.m_pData); return *this; } 我们知道，在分配内存时有可能发生异常。当执行语句 new char[strlen(str.m_pData) + 1]发生 异常时，程序将从该赋值运算符的重载函数退出不再执行。注意到这个时候语句 delete []m_pData 已经执行了。也就是说赋值操作没有完成，但原来对象的状态已经改变。也就是 说不满足题目的异常安全的要求。 为了满足异常安全这个要求，一个简单的办法是掉换 new、delete 的顺序。先把内存 new 出 来用一个临时指针保存起来，只有这个语句正常执行完成之后再执行 delete。这样就能够保 证异常安全了。 下面给出的是一个更加优雅的实现方案： CMyString& CMyString::operator =(const CMyString &str) { if(this != &str) { CMyString strTemp(str); char* pTemp = strTemp.m_pData; strTemp.m_pData = m_pData; m_pData = pTemp; } return *this; } 该方案通过调用构造拷贝函数创建一个临时对象来分配内存。 此时即使发生异常， 对原来对 象的状态没有影响。 交换临时对象和需要赋值的对象的字符串指针之后， 由于临时对象的生 命周期结束， 自动调用其析构函数释放需赋值对象的原来的字符串空间。 整个函数不需要显 式用到 new、delete，内存的分配和释放都自动完成，因此代码显得比较优雅。

随机打印 1-100 的数，每个只能打印一次

（31）

貌似是一道微软笔试题： 问题的难点在于随机打，但是要求每次随机不能有重复，倘若有随机函数 random(int a, int b),代表随机打印 a 到 b 之间的数. 我们可以考虑偌随机出来的不是直接是 1-100 的数， 而是数组的下标是否可以实现随机数不 重复。 例如： int array[100],a[0] 到 a[99]分别是 1-100 random(0,99),得到一个随机数 x,打印出 a[x],然后将 a[x]与 a[99]交换 下次随机函数 random(0,98)，这样无论这次随机值是多少，a[x]都不在可得值的范围内了， 如此循环 99 次即可

代码如下： void randomPrint() { int array[100]; for(int i = 0; i < 100; i++) array[i] = i + 1; for( i = 99; i > 0; i--) { int x = rand() % (i + 1); swap(array, x, i); cout next = = pHead)//自环 return (true); Link *pTemp1 = pHead;//step 1

Link *pTemp = pHead->next;//step 2 while(pTemp != pTemp1 && pTemp != NULL && pTemp->next != NULL) { pTemp1 = pTemp1->next; pTemp = pTemp->next->next; } if(pTemp = = pTemp1) return (true); return (false); }
怎么找出这个链表循环部分的第一个节点 想了一下，似乎下面的算法可以：O(1)空间，O(n)时间。 两个额外指针 p1, p2，开始都指向头 S。设需要找到的循环部分第一个结点的位置为 A，S 到 A 的距离为 x (x 可能为 0） ，链表的循环部 分长度为 y (y > 0)。

算法开始和判断循环的方法一样：令 p1 每次走一步，p2 每次走两步，我们知道，如果链表有环，最后 p1 和 p2 一定在环上某个地方 B 相遇，我们设 A-B 之间的距离为 z (z 可能为 0)。

很显然，p1 走了 x+z 步，那么 p2 走了 2(x+z)步，由于 p1 和 p2 在这么多步后相遇，因此有 2(x+z) - (x+z) = K*y (K > 0 的整数)，因此我 们有 x+z = K*y。

假如我们能让 p1 在 B 点开始继续往前走 x 步的话，它一定会走到 A，因为 z+x 是 y 的倍数。有人会说，费话如果知道 x 的话，我只要让 p2 从起点 S 开始往前走 x 步，不就也能走到 A 吗？其实解法就是这么简单，让 p1 在刚刚相遇的地方 B 继续一次走一步，而 p2 从起点 S 开始一次走一步，那么它们第一次相遇的地方一定是 A，并且正好经过了 x 步（当然你不需要计数） 。

这就是算法。还是比如下面的例子：0->1->2->3->4->5->6->7->8->(3) 刚开始 p1, p2 都在 0，p1 一次走一步，p2 一次走两步，它们最终会在结点 6 相遇。这时候让 p1 继续从 6 开始往前走，而 p2 从 0 开始也 一次往前走 1 步，那么我么就会发现它们会相遇在 3，返回这个地址就是所需要的解。

来一个与众不同的，是在其它地方看到的。

原来链表 ->->-> x -> -> ^ |

| -> x y

显然，过程中可以统计出链表走过的节点数 L，不是环的部分走了 2 遍，也包括 进去了 然后从起点走 L/2 步，走到那个中间节点，就是 y，也是一边走一边反向 然后就是