程序员面试题精选 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<<*iter<<'\t'; std::cout<m_pLeft) FindPath(pTreeNode->m_pLeft, expectedSum, path, currentSum); if(pTreeNode->m_pRight) FindPath(pTreeNode->m_pRight, expectedSum, path, currentSum); // 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; path.pop_back(); } 程序员面试题精选 100 题(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 中的 set 和 multiset 为我们做了很好的堆的实现，我们 可以拿过来用。既偷了懒，又给面试官留下熟悉 STL 的好印象，何乐而不为之？ 参考代码： #include #include #include using namespace std; typedef multiset > IntHeap; /////////////////////////////////////////////////////////////////////// // find k least numbers in a vector /////////////////////////////////////////////////////////////////////// void FindKLeastNumbers ( const vector& data, // a vector of data IntHeap& leastNumbers, // k least numbers, output unsigned int k ) { leastNumbers.clear(); if(k == 0 || data.size() < k) return; vector::const_iterator iter = data.begin(); for(; iter != data.end(); ++ iter) { // if less than k numbers was inserted into leastNumbers if((leastNumbers.size()) < k) leastNumbers.insert(*iter); // leastNumbers contains k numbers and it's full now else { // first number in leastNumbers is the greatest one IntHeap::iterator iterFirst = leastNumbers.begin(); // if is less than the previous greatest number if(*iter < *(leastNumbers.begin())) { // replace the previous greatest number leastNumbers.erase(iterFirst); leastNumbers.insert(*iter); } } } } 程序员面试题精选 100 题(06)－判断整数序列是不是二元查 找树的后序遍历结果 题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回 true，否则返回 false。 例如输入 5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果： 8 / \ 6 10 / \ / \ 5 7 9 11 因此返回 true。 如果输入 7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回 false。 分析：这是一道 trilogy 的笔试题，主要考查对二元查找树的理解。 在后续遍历得到的序列中，最后一个元素为树的根结点。从头开始扫描这个序列，比根结点 小的元素都应该位于序列的左半部分；从第一个大于跟结点开始到跟结点前面的一个元素为 止，所有元素都应该大于跟结点，因为这部分元素对应的是树的右子树。根据这样的划分， 把序列划分为左右两部分，我们递归地确认序列的左、右两部分是不是都是二元查找树。 参考代码： using namespace std; /////////////////////////////////////////////////////////////////////// // Verify whether a squence of integers are the post order traversal // of a binary search 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, // otherwise, return false /////////////////////////////////////////////////////////////////////// bool verifySquenceOfBST(int squence[], int length) { if(squence == NULL || length <= 0) return false; // root of a BST is at the end of post order traversal squence int root = squence[length - 1]; // the nodes in left sub-tree are less than the root int i = 0; for(; i < length - 1; ++ i) { if(squence[i] > root) break; } // 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 false; } // verify whether the left sub-tree is a BST bool left = true; if(i > 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<1> { enum Value { N = 1}; }; solution4_Sum<100>::N 就是 1+2+...+100 的结果。当编译器看到 solution4_Sum<100>时，就 是为模板类 solution4_Sum 以参数 100 生成该类型的代码。但以 100 为参数的类型需要得到 以 99 为参数的类型，因为 solution4_Sum<100>::N=solution4_Sum<99>::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 / \ 10 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 /////////////////////////////////////////////////////////////////////// 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 << pNode->m_nValue << ' '; // print its left child sub-tree if it has if(pNode->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 || m < 0) return -1; // if there are only one integer in the circle initially, // of course the last remaining one is 0 int lastinteger = 0; // find the last remaining one in the circle with n integers for (int i = 2; i <= n; i ++) lastinteger = (lastinteger + m) % i; return lastinteger; } 如果对两种思路的时间复杂度感兴趣的读者可以把 n 和 m 的值设的稍微大一点，比如十万 这个数量级的数字，运行的时候就能明显感觉出这两种思路写出来的代码时间效率大不一 样。 程序员面试题精选 100 题(15)－含有指针成员的类的拷贝 题目：下面是一个数组类的声明与实现。请分析这个类有什么问题，并针对存在的问题提出 几种解决方案。 template class Array { public: Array(unsigned arraySize):data(0), size(arraySize) { if(size > 0) data = new T[size]; } ~Array() { if(data) delete[] data; } void setValue(unsigned index, const T& value) { if(index < size) data[index] = value; } T getValue(unsigned index) const { if(index < size) return data[index]; else return T(); } private: T* data; unsigned size; }; 分析：我们注意在类的内部封装了用来存储数组数据的指针。软件存在的大部分问题通常都 可以归结指针的不正确处理。 这个类只提供了一个构造函数，而没有定义构造拷贝函数和重载拷贝运算符函数。当这个类 的用户按照下面的方式声明并实例化该类的一个实例 Array A(10); Array B(A); 或者按照下面的方式把该类的一个实例赋值给另外一个实例 Array A(10); Array B(10); B=A; 编译器将调用其自动生成的构造拷贝函数或者拷贝运算符的重载函数。在编译器生成的缺省 的构造拷贝函数和拷贝运算符的重载函数，对指针实行的是按位拷贝，仅仅只是拷贝指针的 地址，而不会拷贝指针的内容。因此在执行完前面的代码之后，A.data 和 B.data 指向的同一 地址。当 A 或者 B 中任意一个结束其生命周期调用析构函数时，会删除 data。由于他们的 data 指向的是同一个地方，两个实例的 data 都被删除了。但另外一个实例并不知道它的 data 已经被删除了，当企图再次用它的 data 的时候，程序就会不可避免地崩溃。 由于问题出现的根源是调用了编译器生成的缺省构造拷贝函数和拷贝运算符的重载函数。一 个最简单的办法就是禁止使用这两个函数。于是我们可以把这两个函数声明为私有函数，如 果类的用户企图调用这两个函数，将不能通过编译。实现的代码如下： private: Array(const Array& copy); const Array& operator = (const Array& copy); 最初的代码存在问题是因为不同实例的 data 指向的同一地址，删除一个实例的 data 会把另 外一个实例的 data 也同时删除。因此我们还可以让构造拷贝函数或者拷贝运算符的重载函 数拷贝的不只是地址，而是数据。由于我们重新存储了一份数据，这样一个实例删除的时候， 对另外一个实例没有影响。这种思路我们称之为深度拷贝。实现的代码如下： public: Array(const Array& copy):data(0), size(copy.size) { if(size > 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 <= n; ++ i) { fibN = fibNMinusOne + fibNMinusTwo; fibNMinusTwo = fibNMinusOne; fibNMinusOne = fibN; } return fibN; } 这还不是最快的方法。下面介绍一种时间复杂度是 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 次 运算，并不比前面的方法要快。但我们可以考虑乘方的如下性质： / an/2*an/2 n为偶数时 an= \ 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 { Matrix2By2 ( long long m00 = 0, long long m01 = 0, long long m10 = 0, long long m11 = 0 ) :m_00(m00), m_01(m01), m_10(m10), m_11(m11) { } long long m_00; long long m_01; long long m_10; long long m_11; }; /////////////////////////////////////////////////////////////////////// // Multiply two matrices // Input: matrix1 - the first matrix // matrix2 - the second matrix //Output: the production of two matrices /////////////////////////////////////////////////////////////////////// Matrix2By2 MatrixMultiply ( const Matrix2By2& matrix1, const Matrix2By2& matrix2 ) { 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, 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) { assert(n > 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 <= '9') { num = num * 10 + (*digit - '0'); // overflow if(num>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 中的栈顶元素是最先进入队列的元素，可以 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。不会出现任何矛盾。 我们用一个表来总结一下前面的例子执行的步骤： 操作 m_stack1 m_stack2 append a {a} {} append b {a,b} {} append c {a,b,c} {} delete head {} {b,c} delete head {} {c} append d {d} {c} 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_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) { while(m_stack1.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，这就和已知条件相矛 盾了。 2. 还是用反证法证明。假设 Z 不是 Xm-1 和 Y 的 LCS，则存在一个长度超过 k 的 W 是 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 or j<0 c[i,j]= c[i-1,j-1]+1 if i,j>=0 and xi=xj \ max(c[i,j-1],c[i-1,j] if i,j>=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 <= pEnd) { char temp = *pStart; *pStart = *pEnd; *pEnd = temp; pStart ++; pEnd --; } } } 程序员面试题精选 100 题(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) { int count = 0; while(i) { if(i & 1) count ++; i = i >> 1; } return count; } 可能有读者会问，整数右移一位在数学上是和除以 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 /////////////////////////////////////////////////////////////////////// int NumberOf1_Solution2(int i) { int count = 0; unsigned int flag = 1; while(flag) { if(i & flag) count ++; flag = flag << 1; } return count; } 另外一种思路是如果一个整数不为 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) { int count = 0; while (i) { ++ count; i = (i - 1) & i; } return count; } 扩展：如何用一个语句判断一个整数是不是二的整数次幂？（return !(n&(n-1)）） 程序员面试题精选 100 题(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 题，这里就不在赘述了。 程序员面试题精选 100 题(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. // Otherwise return false ///////////////////////////////////////////////////////////////////////////// bool IsPossiblePopOrder(const int* pPush, const int* pPop, int nLength) { bool bPossible = false; if(pPush && pPop && nLength > 0) { const int *pNextPush = pPush; const int *pNextPop = pPop; // ancillary stack std::stackstackData; // 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(stackData.empty() || stackData.top() != *pNextPop) { // pNextPush == NULL means all integers have been // pushed into the stack, can't push any longer if(!pNextPush) break; stackData.push(*pNextPush); // if there are integers left in pPush, move // pNextPush forward, otherwise set it to be NULL if(pNextPush - pPush < nLength - 1) pNextPush ++; else pNextPush = NULL; } // After pushing, the top of stack is still not same as // pPextPop, pPextPop is not in a pop sequence // corresponding to pPush if(stackData.top() != *pNextPop) break; // Check the next integer in pPop stackData.pop(); pNextPop ++; } // if all integers in pPop have been check successfully, // pPop is a pop sequence corresponding to pPush if(stackData.empty() && pNextPop - pPop == nLength) bPossible = true; } return bPossible; } 程序员面试题精选 100 题(25)-在从 1 到n的正数中 1 出现的 次数 题目：输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。 例如输入 12，从 1 到 12 这些整数中包含 1 的数字有 1，10，11 和 12，1 一共出现了 5 次。 分析：这是一道广为流传的 google 面试题。用最直观的方法求解并不是很难，但遗憾的是 效率不是很高；而要得出一个效率较高的算法，需要比较强的分析能力，并不是件很容易的 事情。当然，google 的面试题中简单的也没有几道。 首先我们来看最直观的方法，分别求得 1 到n中每个整数中 1 出现的次数。而求一个整数的 十进制表示中 1 出现的次数，就和本面试题系列的第 22 题很相像了。我们每次判断整数的个 位数字是不是 1。如果这个数字大于 10，除以 10 之后再判断个位数字是不是 1。基于这个 思路，不难写出如下的代码： int NumberOf1(unsigned int n); ///////////////////////////////////////////////////////////////////////////// // Find the number of 1 in the integers between 1 and n // Input: n - an integer // Output: the number of 1 in the integers between 1 and n ///////////////////////////////////////////////////////////////////////////// int NumberOf1BeforeBetween1AndN_Solution1(unsigned int n) { int number = 0; // Find the number of 1 in each integer between 1 and n for(unsigned int i = 1; i <= n; ++ i) number += NumberOf1(i); return number; } ///////////////////////////////////////////////////////////////////////////// // Find the number of 1 in an integer with radix 10 // Input: n - an integer // Output: the number of 1 in n with radix ///////////////////////////////////////////////////////////////////////////// int NumberOf1(unsigned int n) { int number = 0; while(n) { if(n % 10 == 1) number ++; n = n / 10; } return number; } 这个思路有一个非常明显的缺点就是每个数字都要计算 1 在该数字中出现的次数，因此时间 复杂度是 O(n)。当输入的 n 非常大的时候，需要大量的计算，运算效率很低。我们试着找 出一些规律，来避免不必要的计算。 我们用一个稍微大一点的数字 21345 作为例子来分析。我们把从 1 到 21345 的所有数字分成 两段，即 1-1345 和 1346-21345。 先来看 1346-21345 中 1 出现的次数。1 的出现分为两种情况：一种情况是 1 出现在最高位 （万位）。从 1 到 21345 的数字中，1 出现在 10000-19999 这 10000 个数字的万位中，一共 出现了 10000（104）次；另外一种情况是 1 出现在除了最高位之外的其他位中。例子中 1346-21345，这 20000 个数字中后面四位中 1 出现的次数是 2000 次（2*103，其中 2 的第一 位的数值，103 是因为数字的后四位数字其中一位为 1，其余的三位数字可以在 0 到 9 这 10 个数字任意选择，由排列组合可以得出总次数是 2*103）。 至于从 1 到 1345 的所有数字中 1 出现的次数，我们就可以用递归地求得了。这也是我们为 什么要把 1-21345 分为 1-1235 和 1346-21345 两段的原因。因为把 21345 的最高位去掉就得 到 1345，便于我们采用递归的思路。 分析到这里还有一种特殊情况需要注意：前面我们举例子是最高位是一个比 1 大的数字，此 时最高位 1 出现的次数 104（对五位数而言）。但如果最高位是 1 呢？比如输入 12345，从 10000 到 12345 这些数字中，1 在万位出现的次数就不是 104 次，而是 2346 次了，也就是除 去最高位数字之后剩下的数字再加上 1。 基于前面的分析，我们可以写出以下的代码。在参考代码中，为了编程方便，我把数字转换 成字符串了。 #include "string.h" #include "stdlib.h" int NumberOf1(const char* strN); int PowerBase10(unsigned int n); ///////////////////////////////////////////////////////////////////////////// // Find the number of 1 in an integer with radix 10 // Input: n - an integer // Output: the number of 1 in n with radix ///////////////////////////////////////////////////////////////////////////// int NumberOf1BeforeBetween1AndN_Solution2(int n) { if(n <= 0) return 0; // convert the integer into a string char strN[50]; sprintf(strN, "%d", n); return NumberOf1(strN); } ///////////////////////////////////////////////////////////////////////////// // Find the number of 1 in an integer with radix 10 // Input: strN - a string, which represents an integer // Output: the number of 1 in n with radix ///////////////////////////////////////////////////////////////////////////// int NumberOf1(const char* strN) { if(!strN || *strN < '0' || *strN > '9' || *strN == '\0') return 0; int firstDigit = *strN - '0'; unsigned int length = static_cast(strlen(strN)); // the integer contains only one digit if(length == 1 && firstDigit == 0) return 0; if(length == 1 && firstDigit > 0) return 1; // suppose the integer is 21345 // numFirstDigit is the number of 1 of 10000-19999 due to the first digit int numFirstDigit = 0; // numOtherDigits is the number of 1 01346-21345 due to all digits // except the first one int numOtherDigits = firstDigit * (length - 1) * PowerBase10(length - 2); // numRecursive is the number of 1 of integer 1345 int numRecursive = NumberOf1(strN + 1); // if the first digit is greater than 1, suppose in integer 21345 // number of 1 due to the first digit is 10^4. It's 10000-19999 if(firstDigit > 1) numFirstDigit = PowerBase10(length - 1); // if the first digit equals to 1, suppose in integer 12345 // number of 1 due to the first digit is 2346. It's 10000-12345 else if(firstDigit == 1) numFirstDigit = atoi(strN + 1) + 1; return numFirstDigit + numOtherDigits + numRecursive; } ///////////////////////////////////////////////////////////////////////////// // Calculate 10^n ///////////////////////////////////////////////////////////////////////////// int PowerBase10(unsigned int n) { int result = 1; for(unsigned int i = 0; i < n; ++ i) result *= 10; return result; } 我的做法： 把位数填满对应的 1 的个数是确定的，记为 G(n)，n 指的是位数. 首先计算出 G（n），当 n=1 时，G(n)=1.当 n=2 时，G(n)=20 G(n) = G(n-1)*10 + 10^(n-1) 其中第一项指最高位任意取，后面位中 1 的数是 G(n-1)，后一项指最高位是 1，后面位数字 任意取，则只算最高位的 1 时，1 的总数 则数字 0~m 中 1 的个数可以这样计算： F(m) = m 的最高位*G(n) + 10^(m-1) + F(m 去了最高位后剩下的数字)，若 m 最高位>1 F(m) = m 的最高位*G(n) + m 去了最高位后剩下的数字 + F(m 去了最高位后剩下的数字)， 若 m 最高位<=1 式子中第一项指最高位取数字 0 到最高位-1，其它位数任意取时的 1 的个数 第二项最高位是 1 时的个数 最高位取目前最高位时后面数字为 1 的个数 程序员面试题精选 100 题(26)-和为n连续正数序列 题目：输入一个正数 n，输出所有和为 n 连续正数序列。 例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以输出 3 个连续序列 1-5、4-6 和 7-8。 分析：这是网易的一道面试题。 这道题和本面试题系列的第 10 题有些类似。我们用两个数small和big分别表示序列的最小值和 最大值。首先把small初始化为 1，big初始化为 2。如果从small到big的序列的和大于n的话， 我们向右移动small，相当于从序列中去掉较小的数字。如果从small到big的序列的和小于n 的话，我们向右移动big，相当于向序列中添加big的下一个数字。一直到small等于(1+n)/2， 因为序列至少要有两个数字。 基于这个思路，我们可以写出如下代码： void PrintContinuousSequence(int small, int big); ///////////////////////////////////////////////////////////////////////// // Find continuous sequence, whose sum is n ///////////////////////////////////////////////////////////////////////// void FindContinuousSequence(int n) { if(n < 3) return; int small = 1; int big = 2; int middle = (1 + n) / 2; int sum = small + big; while(small < middle) { // we are lucky and find the sequence if(sum == n) PrintContinuousSequence(small, big); // if the current sum is greater than n, // move small forward while(sum > 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 <= big; ++ i) printf("%d ", i); printf("\n"); } 程序员面试题精选 100 题(27)-二元树的深度 题目：输入一棵二元树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、 叶结点）形成树的一条路径，最长路径的长度为树的深度。 例如：输入二元树： 10 / \ 6 14 / / \ 4 12 16 输出该树的深度 3。 二元树的结点定义如下： struct SBinaryTreeNode // a node of the binary tree { int m_nValue; // value of node SBinaryTreeNode *m_pLeft; // left child of node SBinaryTreeNode *m_pRight; // right child of node }; 分析：这道题本质上还是考查二元树的遍历。 题目给出了一种树的深度的定义。当然，我们可以按照这种定义去得到树的所有路径，也就 能得到最长路径以及它的长度。只是这种思路用来写程序有点麻烦。 我们还可以从另外一个角度来理解树的深度。如果一棵树只有一个结点，它的深度为 1。如 果根结点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加 1；同样如果根 结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加 1。如果既有右子树 又有左子树呢？那该树的深度就是其左、右子树深度的较大值再加 1。 上面的这个思路用递归的方法很容易实现，只需要对遍历的代码稍作修改即可。参考代码如 下： /////////////////////////////////////////////////////////////////////// // Get depth of a binary tree // Input: pTreeNode - the head of a binary tree // Output: the depth of a binary tree /////////////////////////////////////////////////////////////////////// int TreeDepth(SBinaryTreeNode *pTreeNode) { // the depth of a empty tree is 0 if(!pTreeNode) return 0; // the depth of left sub-tree int nLeft = TreeDepth(pTreeNode->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 << array[i] << "; "; } } 求两个整数的最大公约数（最小公倍数）--（辗转相除法） 1: 求两个整数的最大公约数，算法原理辗转相除法 原理： GCD (x,y) = GCD(y,x%y) 当 x%y == 0 时候返回 y 代码如下： int gcd(int A, int B) { if( A % B == 0 ) return B; else gcd(B, A % B); } 2:最小公倍数=A * B / AB 的最大公约数 根据上面求出最大公约数即可求出最小公倍数 判断单向链表中是否存在环(不一定是首尾相连) 基本思想就是使用两个指针~~~~这个在前步进为 2,一个在后步前为 1,如果前面的指针可以 追到后面的指针表明有环 bool CircleInList(Link* pHead) { if(pHead = = NULL || pHead->next = = NULL)//无节点或只有一个节点并且无自环 return (false); if(pHead->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，也是一边走一边反向 然后就是 <-<-<- x <- <- y' | | | <- <- y 然后两个指针都从 y 和 y'开始走，各走一步，交点就是 x，环起点 至于要还原链表，从 y'走向头，反向一次就好了 时间复杂度 O(n)，空间复杂度 O(1)， 方法如下： 设环的长度为 Y 用两个步长分别为1和2的指针前进，第一次相遇之后再前进，第二次相遇时停 止。 记下从第一次相遇到第二次相遇，步长为 1 的指针走过的步数 S，则 S＝＝Y。环 的长度就知道了 用两个指针，一个在链头，一个走到链头后第 Y 个位置上 判断两个指针是否相等，如果是就是环的起始位置了 否则两个指针各自前进一步，再判断 计算∏---数值概率算法 用数值概率算法计算 PI: 单位正方形的内切圆的面积比上正方形的面积： (pi)r*r/ 4 r*r 所以对于一个点，其落在圆内比上落在正方形内的概念为： P= (pi)/4 n 次投点，当 n 足够大时 P= 落在圆内的点的个数/n pi = 4P 代码如下： public static double PI(double n) { Random r = new Random(); double count = 0; //计算落在圆内的次数 double x, y; for( int i = 0; i < n; i++ ) { x = r.nextFloat(); y = r.nextFloat(); if( (Math.pow(x, 2) + Math.pow(y, 2)) <= 1 ) count++; } return (count / n) * 4; //pi = 4P (P 为点在一个单位正方形中，落在其内切圆内的概率) } 全国青少年信息学联赛 Chap2 数学方法与计算 素数，筛法求素数 辗转相除法求最大公约数 一元三次方程求解。先粗略估计根的范围。以 1 为区间扫描值的定义域。设 x1=x,x2=x+1. 找 到这样一个区间，使 f(x1)f(x2)<0. 那么，取 x3 =(x1+x2)/2，若 f(x1)f(x3)<0，则取此区间继 续二分查找，否则取另一半区间。直到区间的范围足够小为止。 不定二元一次方程求解：枚举。 矩阵：基本操作：判等，加减，乘，转置，求逆和初等变换。 设数列 fi 为 Fibonacci 数列。输入 n，求 fn mod q，其中 1(0,1,...n-1) 对开放地址法来说，探查序列 h(k,0),h(k,1)...h(k,n-1)必定是 0,1,...n-1 的一个排列。 HASH)INSERT(T,k) i=0; repeat j = h(k,i) if T[j] = NIL then T[j] = k return j; else i ++; until i =m error "hash overflow" 查找和加入的原理相似。 删除比较复杂：从槽 i 中删除数值时，不能简单的置其为 NIL，否则在 i 后插入的 数值 k 就无法被检索了。所以必须设为 DELETED。但是这样删除的代价就会越来越大。 所以，当元素必须被删除时，多用拉链法解决碰撞。 线性探查：h(k,i) = (h'(k)+i) mod m,i=0,1,...m-1 群集现象严重。 二次探查：h(k,i) = (h'(k)+c1i+c2i^2) mod m c1，c2 不等于 0，为辅助常数。 如果两个关键字初始值相同，探查序列也相同 这样虽使得群集现象有所减少。但是不能很好改善性能。 双重杂凑：h(k,i) =（h1(k)+ih2(k)) mod m 其中 h1，h2 为辅助杂凑函数。 为能查找到整个杂凑表，值 h2(k)要与表的大小 m 互质，否则，如果对关键字 j,m 与 h2(k) 有最大公约数 d>1，那么查找 k 就仅能检查到杂凑表的 1/d 简单的办法就是取 m 为 2 的幂，并设计一个总产生奇数的 h2。 因为初始偏移位置和偏移量都能独立的变化，因此朝理想的杂凑又进了一步。 定理：给定一个装载因子 a 的杂凑表一次不成功查找的探查数最多为 1/(1-a) 假设杂凑是一致的。 证明：第一次探查访问一个被占用槽的概率为 q1 = n/m 当第一次探查访问到被占用槽时才进行第二次探查。 q2 = (n/m)*(n-1)/(m-1) qi = (n/m)*((n-1)/(m-1))*((n-i+1)/(m-i+1)) < (n/m)^i =a^i 因此，一次不成功查找中的平均探查数为： 1 + Eipi = 1+a+a^2+a^3....=1/(1-a) 推论：平均情况下，向一个装载因子为 a 的杂凑表中插入一个元素至多要做 1/(1-a)次探查。 定理：给定一个装载因子 a 的开放地址杂凑表，一次成功查找的期望探查次数 (1/a)*ln((1/(1-a))+(1/a) 假设杂凑是一致的，每个关键字被查到的几率是相同的。 设 k 是第 i+1 个插入到表中的关键字，则对 k 的查找期望次数最多 1/(1-i/m)=m/(m-i)，对表 中所有 n 个 关键字求平均。 1/n(sum(m/(m-i)) i=0~n = m/n*sum(1/(m-i))= 1/a(Hm-Hm-n) 其中 Hi = sum(1/j) j=1~i.为第 i 级调和级数。 1/a(Hm-Hm-n) <= 1/a*(lnm+1-ln(m-n)) = 1/aln(m/(m-n))+1/a = 1/a*(ln(1/(1-a))+1/a 算法导论CHAP13 二叉查找树 二叉查找树的执行效率取决于树的构建方式。 基本操作的时间都和树高成正比。 有些二叉查找树的变形其基本操作的最坏情况性能是很好的。 基础操作：Inorder(T) InOrder(x) if x != NIL InOrder(left(x)); print(key(x)); InOrder(right(x)); endif 基础操作：Search(x,k) if k < key(x) return Search(left(x),k); else return Search(right(x),k); 改用迭代也是很好的想法： while( x!= NIL) { if k < key(x) x = left(x); else x = right(x); } 基础操作：Minimum(x) while left(x)!= NUL do x = left(x); return key(x); 基础操作：Maximum(x) 与上面类似。 进阶操作：Successor(x)：中序遍历的后继。 Successor(x) if right(x) != NIL return Minimum(right(x)); y = p[x]; while ( y != NIL and x = right(y) ) x = y; y = p(y); return y; 若 y 有右子树，那后继即为 y 的右子树的最小值。 否则，向上追溯：直到第一个满足以下条件的节点： 该节点的左子树是 y 的祖先。若有，返回之；否则，返回 NIL。 进阶操作：Insert(T,z); Insert(T,z) y = NIL x = root(T) while x != NIL do y = x if key[z] < key[x] then x = left[x] else x = right[x] p[z] = y if y = NIL then root[T] = z else if key[z] < key[y] then left[y] = z else right[y] = z 复杂度 O(h) 复杂操作：Delete(T,z) 如果 z 没有子女，直接删除 z，并且把其父亲相应的域置成 NIL。 如果 z 有一个子女，将其父亲的相应的域置成其子女。 如果 z 有两个子女，删除其后继，让其代替 z 的位置。 Delete(T,z) if left(z) =NIL and right(z) = NIL if z = left(p(z)) left(p(z)) = NIL else right(p(z)) = NIL else if left(z) = NIL and right(z) != NIL if z = left(p(z)) left(p(z)) = left(z) else right(p(z)) = right(z) else if left(z) != NUL and right(z) = NIL if z = left(p(z)) right(p(z)) = left(z) else right(p(z)) = right(z) else k = Successor(z) if k = left(p(k)) left(p(k)) = NIL else right(p(k)) = NIL if z = left(p(z)) left(p(z)) = k else right(p(z)) = k 定理：对高度为 h 的二叉查找树，INSERT 和 DELETE 的时间都是 O(h) 在 n 个关键字上随机构造的二叉查找树的期望高度为 O(lgn) 引理：设 T 为通过将 n 个不同的关键字 k1，k2，。。。kn 按序插入一棵初始为空的二叉查找 树而构成的树。对 1<=ikj} 或 ki = max{ kz:1<=z<=i 且 kzki>kj,对所有满足 kz>kj 的 z=1 bn = sum(bk*b(n-1-k)) [0<=k=2^(h/2)-1 两边取对数可得 h<=2lg(n+1) 红黑树的旋转：要求保持中缀遍历顺序。 左旋和右旋可以视为逆操作。 y x / \ 右旋(T,y) / \ x c ----------> a y / \ <---------- / \ a b 左旋（T,y) b c LEFT_ROTATE(T,x) y = right(x) right(x) = left(y) if left(y) != NIL then p(left(y)) = x p(y) = p(x) if p(x) = NIL then root(T) = y else if x = left(p(x)) = y then left(p(x)) = y else right(p(x)) = y left(y) = x p(x) = y 向一棵含 n 个节点的红黑树中插入一个新节点的操作可在 O(lgn)时间内完成。先调用 Tree_Insert 过程将 x 插入 T，然后将 X 着为红色。为保证红黑性质能继续保持，再对有关节点重新着 色并旋转。 RB_INSERT(T,x) TREE_INSERT(T,x) color(x) = RED while x!=root(T) and color(p(x))=RED do if p(x)=left(p(p(x))) then y = right(p(p(x))) if color(y) = RED then color(p(x)) = BLACK color(y) = BLACK color(p(p(x))) = RED x = p(p(x)) else if x = right(p(x)) then x = p(x) LEFT_ROTATE(T,x) color(p(x)) = BLACK color(p(p(x))) = RED RIGHT_ROTATE(T,p(p(x))) else ( 同 then 子句，交换 right 和 left） color(root(T)) = BLACK 当情况 1 出现时，才会做若干次循环，且 X 沿树上升 一旦进入情况 2 或 3，迭代停止，一次旋转后整个调整过程结束。 复杂操作：删除 RB_DELETE(T,z) if left(z) =nil(T) or right(z) = nil(T) then y = z else y = TREE_SUCCESSOR(z) if left(y) != nil(T) then x = left(y) else x = right(y) p(x) = p(y) if p(y) = nil(T) then root(T) = x else if y = left(p(y)) then left(p(y)) = x else right(p(y)) = x if y != z then key(z) = key(y) if color(y) = BLACK then RB_DELETE_FIXUP(T,x) return y 以上代码和 RB_DELETE 之间有三点不同。 首先，TREE_DELETE 中对 NIL 的引用被替换成对哨兵 nil(T)的引用， 第二，TREE_DELETE 中不再判断 x 是否为 NIL,而是无条件执行 p(x)=p(y) 第三，如果 y 是黑色的，则调用 RB_DELETE_FIXUP 恢复红黑性质。 RB_DELETE_FIXUP(T,x) while x != root(T) and color(X) = BLACK do if x = left(p(x)) then w = right(p(x)) if color(w) = RED then color(w) = BLACK color(p(x)) = RED w = right(p(x)) //以上是情况 1 if color(left(w)) = BLACK and color(right(w)) = BLACK then color(w) = RED x = p(x) else if color(right(w)) = BLACK then color(left(w)) = BLACK color(w) = RED RIGHT_ROTATE(T,w) w = right(p(x)) color(w) = color(p(x)) color(p(x)) = BLACK color(right(w)) = BLACK LEFT_ROTATE(T,p(x)) x = root(T) else （同then只是呼唤right和left） color(x)=BLACK 可以利用前面介绍的二叉查找树的插入操作Insert将元素插入到红-黑树中. 当把一个元素插 入到树中后，需要为该新增加的结点涂色，如果插入前是空树，则新结点是根结点，颜色为 黑色；假设插入前树非空，新结点的颜色如果涂成黑色，则树不符合定义中的条件 3；如果 新结点涂成红色，则可能不满足条件 2. 这种情况下，我们倾向于把新结点涂成红色. 如果新结点的颜色为红色而导致红-黑树不满足条件 2，树的平衡性被破坏. 我们可以通过 检查新结点u，其父结点pu以及它的颜色为黑色的祖先结点gu（pu的父亲结点），显 然pu的颜 色为红色（否则不破坏条件 2），因此pu不可能是根，所以pu必然存在一个父亲结点gu，其 颜色为黑色. 我们把造成的不平衡分成八种情况考虑：LLb,LRb,RLb,RRb;(即当pu是gu的左 儿子，u是pu的左儿子且gu的右儿子为黑色时，不平衡属于LLb类型.) LLr,LRr,RLr,RRr.(即pu 是gu的左儿子，u是pu的左儿子且gu的右儿子为红色时，不平衡属于LLr型) X 不平衡需要通过转动（或旋转）来解决. 图 10.20 给出了 LLr和LRr不平衡类型的颜色变化， 图中黑色结点用深色阴影表示，红色结点用浅色阴影表示，本图中，gu是黑色结点，u和pu 是红色结点，gu 的两个儿子结点都是红色的. 两种情况解决不平衡都是把pu和gu 的另一个 儿子结点（gu 的两个儿子结点）的颜色改为黑色，并且，如果gu不是根，则把gu的颜色改 为红色，否则gu颜色不变. 从图中很容易看出，如果gu是根，则经过颜色变换后红-黑树的 阶增加了 1 . Yr（X和Y既可以是L，也可以是R）类型的不平衡可以通过改变颜色来解决，而XYb型的 heng/41.JPG 的不平衡，则gu变成了新的结点u，重复上述过程，直 转操作. 类似于动态平衡树中的单一转动和 http://foto.yculblog.com/jic 如果gu的颜色改为红色后，引起了新 到访问到根结点或者没有不平衡现象为止. 图 10.21 给出了处理LLb和LRb类型不平衡的旋 双重转动，所不同之处在于需要调整结点的颜色值. 通过检查图 10.21 中结点的颜色取值， 从根结点到所有外结点的路径上，黑色指针的数量都没有改变. 因此结点插入后，一次旋转 操作就可以使红-黑树恢复平衡. http://foto.yculblog.com/jicheng/42.JP 对于删除操作，我们可以使用二叉查 果需要，还要进行一次单旋转. 考虑图 10.22a中的树，如果删除结点 70，将得到图 10.22b 所示的树（注意指针颜色变化）；如果从a中删除结点 90，将得到图 10.22c所示的树. 设y是 代替被删除结点的结点，如图 10.22b，结点 90 的左儿子结点被删除了，它的新的左儿子结 点是外结点y . G 找树中的Delete操作删除结点，然后进行颜色调整，如 om/jicheng/43.JPG 图 10.22b 的情况，由于删除结点 70 是红色的，删除它不会影响从根到外结点的路径中黑 当不平衡发生后，以结点 y 为根的子树形缺少一个黑色结点，因此从根经过 y 到外结点的 b 类型的不平衡（Lb 同理）. 根据结点 v 的红色儿子结点的数目，把 Rb 类型的 当不平衡是 Rb0 时，需要改变颜色，图 10.23 给出了 py 颜色的两种可能改变. 分两种情 当不平衡类型是 Rb1 和 Rb2 时，需要进行旋转，如图 10.24 所示，图中非阴影结点表示该 http://foto.yculblog.c 如 色结点的数量，所以不需要任何处理. 在 10.22c 中，被删除结点 90 是黑色的，从根经过 y 到某些外结点的路径上的黑色结点个数比原来减少了 1，如果替换结点 90 的结点 y 是根结 点，则树仍然是红-黑树，只是阶减少了 1，否则不满足条件 3，需要进行调整. 通过上述分 析我们可以看出，仅当被删除结点是黑色结点并且替换结点 y 不是根结点的情况下，删除操 作后需要进行平衡化处理. 路径上的黑色结点数比到其他外结点的路径上的黑色结点少一个. 通过观察结点y的父亲结 点 py 和兄弟结点 v 来区分不平衡的类型. 当 y 是 py 的右儿子结点，不平衡是 R 类型的，否 则是 L 类型的. 显而易见，如果 y 子树中缺少一个黑色结点，那么 v 肯定不是一个外结点， 如果 v 是黑色结点，那么不平衡是 Lb 或 Rb 类型的；而当 v 是红色结点时，不平衡是 Lr 或 Rr 类型的. 首先观察 R 不平衡分为三种情况：Rb0，Rb1，Rb2 . 况讨论：第一种情况，如果 py 原来是黑色的，则由 a 到 b 后，导致以 py 为根的子树缺少 一个黑色结点，如果 py 是整个红-黑树的根，则处理过程结束，树的阶减少了 1；否则 py 成为新的 y，重复上述处理过程. 第二种情况如果 py 原来是红色的，则从根经过 y 到外结点 的路径上黑色结点增加了 1 个，从根经过 v 到外结点的路径上黑色结点数目没有改变，红- 黑树达到了平衡. 结点既可能是黑色结点也可能是红色结点，而且这种结点的颜色在旋转后不会发生变化. 旋 转后，从根经过 y 到外结点路径上的黑色结点数增加了 1 个，而从根到其他外结点路径上的 黑色结点数没有改变，旋转使红-黑树恢复了平衡. 接下来我们继续分析 Rr（Lr 同理）型的不平衡，由于 y 中缺少一个黑色结点并且 v 是红色 的，v 的左右儿子结点中至少有一个黑色结点不是外部结点，从而 v 的儿子结点都是内结点， 根据 v 的右儿子结点的红色儿子结点的数量（0，1，2），可以进一步把 Rr 类型的不平衡分 为三种情况 Rr0，Rr1，Rr2，这三种情况都需要用旋转来处理，如图 10.25 和 10.26 所示， 可以验证其中的旋转使红-黑树恢复了平衡. 插入和删除操作后，由于颜色的改变是沿着向根结点的方向进行的，因此需要的时间是 O(logn)；另一方面需要旋转的情况，每次最多需要一次旋转和部分颜色改变操作，所需要 的时间是Θ(1) . 算法导论CHAP16 动态程序设计(DP) 设计一个动态程序设计算法的过程可分为 4 个步骤： 1 刻划最优解的结构 2 递归定义最优解的值 3 按自底向上的方式计算最优解的值 4 由计算出的结果构造一个最优解 基本问题：矩阵链乘法 任意加括号对矩阵链乘的结果不会有影响，但是对运算量有很大影响。 解：考虑到穷尽所有可能的括号化方案是不会产生一种有效的算法的。 用 P(n)表示一列 n 个矩阵可能的括号化方案数。 因为我们可将一列 n 个矩阵从第 k 个和第 k+1 个处分裂开，k＝1，2，。。。，n-1 然后对两个子序列分别加括号，可得递归式 / 1 n =1 P(n) = < \ sum( P(k)*P(n-k) [k=1~n-1] n>=2 这个递归式的解是 Catalan 数序列 P(n) = C(n-1) C(n) = (1/(n+1))*c(2n,n) = O(4^n / n^(3/2)) 为 n 的指数，无法搜索。 最优化思想：DP。 A(i,j)代表 AiAi+1...Aj 求值的结果。 A(i,j) = min( A(i,k)+A(k,j) )+这两个矩阵相乘的代价 ii then X = MATRIX_CHAIN_MULTIPLY(A,s,i,s[i,j]) Y = MATRIX_CHAIN_MULTIPLY(A,s,s[i,j]+1,j]) return MATRIX_MULTIPLY(X,Y) else return A1 最优子结构：一个问题的最优解中包含了其子问题的最优解（可以使用贪心或 DP）。 重叠子问题：将子问题的最优解存起来以备查。 基本问题：最长公共子序列 LCS 是典型的 DP。 设有子串 x 和 y。 x1，x2，。。。xm 定义为 x 的第 n 个前缀。 定理：设 X＝和 Y=是两个序列。 并设 Z=为 x 和 y 的 LCS。 1。如果 xm=yn，则 Zk=Xm=Y 且 Zk-1 是 Xm-1 和 Yn-1 的一个 LCS。 2。如果 xm!=yn,则 Zk!=xm 蕴含 Z 是 Xm-1 和 Y 的一个 LCS。 3。如果 xm!=yn,则 Zk!=yn 蕴含 Z 是 X 和 Yn-1 的一个 LCS。 所以，以 C[i,j]代表 Xi 和 Yj 的 LCS 长度。可得递归式： / 0 i=0||j=0 c[i,j] = < c[i-1][j-1]+1 xi=yj , i&&j \ max(c[i-1][j],c[i][j-1] xi!=yj, i&&j 判断子问题求值的顺序，改用迭代求值。 跟踪在哪个方向上执行第二个式子可以求得子序列。占用 O(mn)空间，O(mn)时间。 改进：c 只需两行就可以进行交替计算了。 基本问题：最优多边形三角剖分 n 个端点的多边形，都有 n-3 根弦，将多边形划分为 n-2 个三角形。 要求一个三角剖分，使得所产生的所有三角形的权函数最小。 一个权函数就是： w(△vivjvk)=|vivj|+|vjvk|+|vivk| 最优三角剖分的子结构： 定义 t[i,j]是多边形[vi,...vj]的三角剖分中的三角形之权的和。 一个递归解： / 0 i=j t[i,j] = 0 < \ min(t[i,k]+t[k,j]+w(△vi-1vkvj) i!= j 思考：欧几里得货郎担问题 这个问题的描述：对于平面上 n 个点，确定一条连接各点的，闭合的游历路线的问题。 利用 bitonic 类算法（严格从左向右）实质是为 v1,v2...vn 定序，这样就可以用 dp 解决： 设 t[i,j]是 ti,ti+1...tj 的最小路径。 用类似三角剖分的方法解决。 优美打印 考虑在一台打印机上优美地打印一段文章的问题。输入的正文是长度为 I1,I2,…,In 的 n 个单 词构成的序列。我们希望将这段文章在几行上打印出来，每行的最大长度为 m，且“优美” 度的标准如下: 如果某一行包含从 i 到 j 的单词，且每两个单词间留一空，则在行末多余的空格为 m-j+i-sum(Ik) [i~j] 我们希望除最后一行的所有行中，行末多余空格的总和最小。请给出一个算法来优美地打印 出一段有 n 个单词的文章。 解：由于单词填人的方式是按单词序号递减的顺序进行的，因此填入单词 i…单词 n 后的行 末空格数的总和应为当前行的行末空格数+前面行的行末空格数的和。我们的目标是使它最 小。 设 r[i] -- 填入单词 i…单词 n 后，所有被填行的行末空格数总和的最小值。显然，r[i]的递归 式如下： r[i] = min(m-((j-i)+sum(Ik)[i~j])+r[j+1]) [1并产生相应声音的可能性。这种图是一个人说一种有限语言的形式模型。 现指定一个开始顶点 V0，规定从 V0 出发的边的概率之和为 1，另外指定声音集 S=<&1， &2，…,&k>。请描述一个有效算法，求一条开始于 V0 的具有标记 S 的一条最有可能的路 径，即路径上的边依次标识&1，&2，…,&k，且其上所有边的概率积最大。如果不存在这 样的路径，返回"No_Such_Path"信息。 设 Li(0≤i≤K)链——存储所有标以声音&i 的边的终点 V，且 V0 通向每个 V 有一条路 径，这条路径上的边顺序标记&1，&2，…,&i ，且这 i 条边的概率之积在所有这样的路径 中是最大的。 我们首先将 V0 放入 L0 链，设 V0 出发的边的概率之积为 1。然后按下述方法依次扩展 L1 链，L2 链，…,LK 链: 扩展 Li 链的当前顶点时检查 Li-1 链中的所有顶点。若与 Li-1 链中某顶点 U 相连的边 上的声音为&i，则再依次检查 Li 链的每一顶点：若 V 末在 Li 链中，则 V 进入 Li 链和 V0 至 U 的路径；若 V 在 Li 链中且 V0 出发、经过的路径概率为目前最大，则修正 Li 链 中 V 的概率积，使得 V0 至 V 的路径经过。 显然这条路径具备最优子结构：即 V0 至路径上每顶点的概率积最大；同时具有重叠子问题 的性质：扩展 Li 链的子问题包含了扩展 Li-1,Li-2,…,L1 链的子子问题。因此，我们可以使 用动态规划的方法，自下而上地顺序扩展 L1,L2,…,Lk 链。在扩展出 Lk 链后，V0 与 Lk 链 中每一顶点 Vk 间都有一条标记 S 的、最可能(相对其它通往它的路径而言)的路径。Lk 链中 概率积最大的一个顶点所对应的一条路径即为问题的解。 算法导论CHAP17 贪心算法 贪心思想：利用局部最优解生成全局最优解。 基本问题：活动选择问题。 假设有一个由需要使用某一资源的 n 个活动集合 S={1,2,...,n} 该资源一次只能被一个活动占用。每个活动 i 有个开始时间 si 和结束时间 fi，且 si<=fi。一 旦被选择活动 i 就占据半开时间区间[si,fi)。这个问题是要选择一个由互相兼容的问题组成的 最大集合。 算法：在挑选下一个活动时，总是挑选具有最早结束时间的那个。 定理：上述算法能产生活动选择问题的最大规模解。 关键：每次选定一个活动后，剩下的就是和原问题性质相同，规模略小的问题。 适合贪心策略解题的性质：贪心选择性质和最优子结构。 贪心选择性质：一个全局最优解可以通过局部最优（贪心）选择来达到。贪心算法的当前选 择可能要依赖于已经做出的所有选择，但不依赖于有待于做出的选择或子问题的解。 最优子结构是指问题的解包含了其子问题的最优解。 贪心和 DP 的区别：考察 0－1 背包问题。 0－1 背包问题：n 件物品，第 i 件物品值 vi 元，重 wi 磅，此处 vi 和 wi 都是整数。背包容 量为 W，每个物品只有一件。求带走物品的集合。 另一种变种问题是：可以带走物品的一部分，称为部分背包问题。 部分背包问题可以贪心解决。但 0－1 背包就只能用 DP。 DP 和贪心的区别在于是否有大量重叠子问题。 基本问题：哈夫曼编码 哈夫曼编码是非常有效的数据压缩技术。 前缀编码：哈夫曼编码中，没有任何的编码是其它编码的前缀。 哈夫曼算法：贪心法思想 Huffman(C) 将森林中最小的两个频度组成树，放回森林。直到森林中只有一棵树。 证明哈夫曼算法的正确性 引理：设 C 为一字母表，其中每个字符 c 具有频度 f[c]。设 x 和 y 为 C 中具有最低频度的两 个字符，则存在 C 的一种最优前缀编码，其中 x 和 y 的编码长度相同但最后一位不同。 证明：根据构造过程证明：交换任意一个节点与叶子节点计算代价来说明最优。 引理：设 T 为表示字母表 C 上一种最优前缀代码的满二叉树。对 C 中每个字符定义有频度 f[c]。考虑 T 中任意两个为兄弟叶节点的字符 x 和 y，并设 z 为他们的父节点。那么，若认 为 z 是一个频度为 f[z]＝f[x]+f[y]的字符的话，树 T'＝T－｛x,y｝就表示了字母表 C'=C-{x,y} 并{z}上的一种最优前缀编码。 去掉 x,y 后计算各部分代价： f[x]dT(x) + f[y]dT(y) = (f[x]+f[y])(dT'(z)+1) = f[z]dT'(z) + (f[z]+f[y]) 所以根据此式：B(T) = B(T') + f[z] + f[y] 如果 T'代表 C'上一种非最优前缀代码，则存在叶节点为 C'中的字符的树 T''，将 x 和 y 插入 T''中使它们称为 z 的子结点，可以得到 C 的一种前缀代码，使得 B(T'') + f[x] + f[y] < B(T)， 和 T 的最优性矛盾。 定理：过程 HUFFMAN 可产生一种最优的前缀编码。 思考题： 找换硬币：考虑用最少的硬币数来找 n 分钱的问题。 算法导论CHAP18 平摊分析 聚集方法：证明对所有的 n，n 个操作构成的序列在最坏情况下总时间是 T(n)。最坏情况下 每个操作的平摊代价是 T(n)/n。这个代价当序列中存在集中类型的操作时仍然成立。 栈操作：下列操作的代价都是 O(1) push(s,x)，pop(s) 每个操作的代价可视为 1。n 个 push 和 pop 的序列的总代价为 n，实际运行时间是 O(n) 增加动作 MULTIPOP(s,k)，从栈里弹出 n 个对象，不足 n 个对象时清空整个栈。 MultiPOP(s,k) while not STACK-EMPTY(S) and k != 0 do POP(S) k-- 这个操作的代价为 min(s,k)。实际运行时间为这个代价的一个线性函数。 对作用于一个初始为空的栈上的 n 个 push，pop 和 multipop 操作构成的序列做个分析。 序列中一次 Multipop 的操作最坏情况代价为 O(n)，任意栈操作最坏 O(n)mn 个操作的总代价 就是 O(n^2) 这个结论是不够精确的。 考虑到，虽然某一次 Multipop 的操作代价较高，但作用于初始为空栈的任意一个包含 n 个 PUSH， pop，multipop 的操作序列代价至多为 O(n)。一个对象被压入栈后至多被弹出 1 次。因此， 在一个非 空栈上调用 POP 和 multipop 的次数至多等于 PUSH 的次数，即至多为 n。对任意的 n，包 含 n 个 push，pop，和 multipop 的序列总代价为 O(n)。据此每个操作的平摊代价是 O(1). 例子：二进制计数器 共 length 位的计数器增 1 函数 INCREMENT(A) i = 0 while i < length[A] and A[i] = 1 do A[i] = 0 i ++ if i < length[A] then A[i]=1 大致分析，最坏情况下，INCREMENT 每次执行要花 O(k)时间，此时数组 A 中包含全 1。 这样，n 个 INCREMENT 操作的时间就是 O(nk) 若分析的更精确，可得 n 次 INCREMENT 操作的序列最坏情况代价是 O(n) 作用于初始为 0 的计数器的 n 次 INCREMENT 使 A[1]变化了 n/2 次，A[2]变化了 n/4 次对第 i 位， n 次 INCREMENT 使其翻转 n/(2^i)次。对 i>lgn，位 A[i]始终不发生变化。 所以翻转总次数为 sum(n/(2^i)) [i=0~lgn] < n*sum(1/(2^i)) [i=0~INFINITE] = 2n 所以总共的代价为 O(n) 会计方法：对不同的操作赋予不同的费值，某些操作的费值比他们的实际代价或多或少。 对每一操作所计的费值即其平摊代价。当一个操作的平摊代价超过了它的实际代价时，两者 的 差值就被作为存款赋给数据结构中一些特殊的对象。 存款可以在以后补偿那些平摊代价低于其实际代价的操作。 所以可以将平摊代价分为实际代价和存款。 必须时刻注意数据结构中的总存款不能是负的。 以栈为例，各栈操作的实际代价为 push 1 pop 1 multipop min(k,s) 现对它们赋予以下的平摊代价： push 2 pop 0 multipop 0 只需要支付 push 的费用，就可以对 pop 和 multipop 免费，并且任何时候存款都不会为负。 二进制计数器的会计方法： 设对某一位置置 1 收取 2 元的平摊费用。当某数位被置顶后，用 2 元中的 1 元来支付置位操 作的实际代价 ，另 1 元存在该位作为余款。这样在某位复位成 0 时不用支付任何费用。 ××这种方法让编程者专注于某些主要动作，便于估计代价。 势能方法：将已预付的工作表示成一种“势能”，必要时可以释放出来支付后面操作的代价。 势是与整个数据结构而不是和其中个别对象联系的。 开始先对一个初始数据结构 D0 执行 n 个操作。对每个 i=1,2,...,n，设 ci 为第 i 个操作的实际 代价，Di 为对数据结构 Di-1 作用的第 i 个操作的结果。势函数 T 将每个数据结构 Di 映射为一个实数 T(Di)，即 与数据结构 Di 相联系的势。第 i 个操作的平摊代价 ci~定义为 ci~ = ci + T(Di)-T(Di-1) 从这个式子可以看出，每个操作的平摊代价为其实际代价加上由于该操作所增加的势。 不同的势函数可能会产生不同的平摊代价，但是它们都是实际代价的上界。 栈操作：以栈中元素个数作为势的评价标准。 T(D0) ＝0（起始为空栈） 栈中对象个数非负，所以第 i 个操作之后栈 Di 就具有非负的势。 且有 T(D1)>=0=T(D0) push 形成的势差为 1，实际代价为 1，势代价为 2。 pop 和 multipop 的势差为-1 和-k,实际代价为 1 和 k，势代价都为 0。 三种栈操作的每一种的平摊代价都是 O(1)。所以包含 n 个操作的序列的总平摊代价 就是 O(n)。 同理，二进制计数器可以将第 i 次操作后计数器中 1 的个数作为势。 进阶问题：动态表 证明表的插入和删除的平摊代价是 O(1)，即使它们引起了表的扩张和收缩时具有较大的实 际代价也一样。 一种常用的启发式扩充方法是：当表满了之后，扩充到当前容量的两倍 考察一个初始为空的表上的 n 次 TABLE_INSERT 操作，每次操作的最坏情况代价为 O(n) 由此可得 n 次操作的总得运行时间的上界 O(n^2) 但这个界并不精确，仅当 i－1 为 2 的整数幂时第 i 次操作才会引起一次表的扩张。实际上， 每一次操作的平摊代价为 O(1)。 ci= i (如果 i-1 为 2 的一个整数幂） 1 其它情况 sum(ci)[1~n] <= n+sum(2^j) [0~lgn] =1/2 size[T]/2-num[T] 若 a[T]<1/2 注意，空表势为 0，势总是非负的。以 D 表示的一列操作的总平摊代价即为其实际代价的一 个上界。 由此可以评价出，一次 TABLE_INSERT 的代价至多为 3。TABLE_DELETE 的代价至多为 2。 所以可以总结出动态表 INSERT 和 DELETE 的平均代价是 O(1) 思考题： 1。按位反序二进制计数器 执行对长度为 n=2^k 的输入数组 A[0..n-1]的按位反序排列。这种排列将某些元素进行交换， 这些 元素的下标的二进制表示正好相反。 算法导论CHAP19 B-树 B-树是辅存上的数据结构。 原理：磁头读取的特征：定位耗时，之后的读取则相对省时 一个 B-树算法主要由它执行的 DISK-READ 和 DISK-WRITE 决定。 B-树的分支因子一般为 50－2000。具体要取决于关键字相对于 1 页的大小。 一棵 B-树 T 具有如下性质： 1。每个节点 x 有以下这些域： a.n[x]：当前存储在 x 内的关键字数。 b.n[x]个关键字：以非降序存放 c.leaf[x]，是一个布尔值，如果 x 为叶子时它为 true，否则为 false 2。如果 x 是内节点，还包含 n[x]＋1 个指向其子女的指针。 3。每个叶结点的深度相同。 4。每个节点能包含的关键字数有着下界和上界。这些界可由一称为 B-树最小度数的整数 t>=2 表示。 每个非根的节点至少应有 t-1 个关键字 每个节点最多可包含 2t-1 个关键字。所以，一个内节点最多可有 2t 的子女。 t=2 时的 B-树最简单，其中每个内节点有 2 个，3 个或 4 个子女。也称为 2－3－4 树。 定理：如果 n>=1，则对任意一棵包含 n 个关键字的，高度为 h 的，最小度数 t>=2 的 B-树 T, h<=log(t,(n+1)/2) 深度少，查找次数减少，意味着读取磁盘的次数也减少了，节省了时间。 在 B-树中查找： B-TREE_SEARCH(x,k) i=1 while i<=n[x] and k>keyi[x] i++ if i < n[x] and k=keyi[x] then return (x,i) if leaf[x] then return NIL else DISK_READ(ci[x]) return B-TREE_SEARCH(ci[x],k) 创造一棵空 B-树。 用 B-TREE_CREATE 创建新根节点，再用 B-TREE_INSERT 加入新关键字。 其中用到 ALLOCATE_NODE，在 O(1)时间内为新节点分配一个磁盘页。 B-TREE_CREATE(T) x = ALLOCATE_NODE() leaf[x] = TRUE n[x] =0 DISK_WRITE(x) root[T] = x O(1)次磁盘操作 O(1)时间。 B-树节点的分裂：将满的节点 y（2t-1 个关键字）按其中间关键字 keyt[y]分裂成两个各含 t-1 关键字的节点。 假设 y 是 x 的第 i 个孩子，也是要被分裂的节点。开始时节点 y 有 2t－1 个子女，在分裂后 减少至 t－1。 z 则收养了 y 的其它孩子。 向 B-树中插入节点 关键：利用 B-TREE_SPLIT 使新加节点不会降落在满节点上。 B-TREE_INSERT(T,k) r=root[T] if n[r] = 2t-1 then s = ALLOCATE-NODE() root[T] = s leaf[s] = FALSE n[s] = 0 c1[s] = r B-TREE_SPLIT(s,1,r) B-TREE_INSERT_NONFULL(s,k) else B-TREE_INSERT_NONFULL(r,k) B-树的高度增加总是在顶部发生的。 B-TREE_INSERT_NONFULL 插入节点，保证它所在的节点是非满的。 B-TREE_INSERT_NONFULL 的实现是，如果 k 降落叶子节点，则插入，否则，判断将要降 落的 节点是否为满，满则 B-TREE_SPLIT 分裂之，再递归向下寻找叶子节点。 删除一个关键字 B-TREE_DELETE 从以 x 为根的子树中删除关键字 k。保证无论对何节点 x 递归调用 B-TREE_DELETE，x 中的 关键字数都至少等于最小度数 t。这个加强条件使得绝大多数情况不用回溯，一次就可删掉 k。 流程 如果根节点 x 会称为一个含任何关键字的内节点，则 x 要被删除，x 仅有的孩子 c1[x]就称 为树的新根。 这是使树高度下降的惟一办法。 1 如果关键字 k 在节点中，且 x 为叶节点，则从 x 中删除 k。 2 如果 k 在内节点中，则 a 如果节点 x 中前于 k 的子节点 y 包含至少 t 个关键字，则找出 k 在以 y 为根的子树中的 前驱 k'。 递归的删除 k'，并在 x 中用 k'取代 k。 b 对称的，如果节点 x 中后于 k 的子节点 z 包含至少 t 个关键字，则找出 k 在以 z 为根的 子树中的后继 k'。递归的删除 k'，并在 x 中用 k'取代 k。 c 否则，如果 y 和 z 都只有 t-1 个关键字，则将 k 和 z 的所有关键字合并进 y。这时 y 包 含 2t-1 个关键字 然后释放 z 并将 k 从 y 中删除。 3 如果 k 不在内节点中。则确定 k 在根 c 中。如果 c 只有 t-1 个关键字，执行步骤 3a 或 3b 以保证我们降至一个至少包含 t 个关键字的节点，然后，通过对 x 的某个子节点递归而结束。 a 如果 c 只包含 t-1 个关键字，但其一个兄弟包含至少 t 关键字则通过将 x 中的某一个关 键字降至 c 中 将 c 的仅左或仅右兄弟中某一关键字升至 x。 b 如果 c 和所有兄弟包含 t-1 关键字，则将 c 和一个兄弟合并。 插入和删除 CPU 时间为 O(tlogtN),读取磁盘为 O(h) 算法导论CHAP22 用于分离集合的数据结构(并查集) 分离数据集合记录一组分离的动态集合 S。 每个集合通过一个代表加以识别。在某些应用中哪一个成员被选作代表无所谓，但 要求取某一代表两次且在两次请求中不修改集合，则两次得到的答案应该是相同的。 支持的操作： MAKE_SET(x)：建立一个新的集合，其仅有的成员由 x 指向。 UNION(x,y)：将包含 x 和 y 的动态集合（比如说 Sx 和 Sy）合并为新的集合。结果的集合代 表是 Sx 并 Sy 的某个成员。 FIND_SET(x）：返回一个指向包含 x 的惟一集合代表的指针。（用于判等） 分析集合数据结构的运行时间：n，即执行 MAKE_SET 操作的次数。m，即执行 MAKE_SET,UNION 和 FIND_SET 的总次数。 分离集合数据结构的一个应用：确定无向图中连通子图的个数。 最简单的分离集合数据结构实现：链表。每个链表代表一个集合。集合中每个元素含有指向 链表头 （即代表元素）的指针。 MAKE_SET 和 FIND_SET 只需要 O(1)的时间，但 UNION 需要 O(n)的时间。 可以轻易的找出一种方式使得一系列操作的平摊时间达到 O(m)。 一种加权启发方式： 假设每个代表中还维护表的长度，总是将较短的表拼到较长的表上。同时可以任意打断链接 关系。 定理 1 ：利用分离集合的链表表示和加权合并启发式，一个包括 m 个 MAKE_SET,UNION,FIND_SET（其中 n 个是 MAKE_SET 操作）的序列的时间为 O(m+nlgn)。 证明：考虑 x 的代表指针第一次更新后，集合中至少含 2 个元素。下一次则是 4 个。继续下 去，在 x 的代表指针被更新 lgk 次后，集合中必至少含有 k 个元素。又由于最大的集合至多 包含 n 个元素。所以每个 对象的代表指针至多被更新了 lgn 次。所以更新 n 个对象所用的总时间为 O(nlgn)。 分离集合森林： 改进：改用树来存储集合。 采用启发式算法：按秩合并 合并时具有较小度的树要被合并到大树上。 启发式方法：路径压缩 UNION 时不更新集合元素的 p 域。 FIND_SET 时，置该域。 带路径压缩的 FIND_SET FIND_SET(x) if x != p[x] then p[x] = FIND_SET(p[x]) return p[x] 单独使用按秩合并，可以获得 O(mlgn)的运行时间。 同时使用按秩合并和路径压缩，最坏运行时间为 O(ma(m,n))。a(m,n)为 Ackerman 函数 增长极慢的逆函数。所以，可以将运行时间视为 m 的线性。 思考题： 1。脱机最小值： 该问题是对 INSERT 和 EXTRACT-MIN 操作的序列做存储。 例如：该序列为 4 8 E 3 E 9 2 6 E E E 1 7 E 5 将正确的值填入 extracted 数组。 解：将 S 分为若干同构的子序列，即 I1,E,I2,E,I3,...,Im,E,Im+1 每个 Ij 表示一个可能为空的 INSERT 调用序列。 将这些操作的关键字放入一个集合 Kj。如果 Ij 为空则它也是空的。 OFFLINE_MINIMUM(m,n) for i = 1 to n do 确定 j 使 i 属于 Kj if j!= m+1 then extracted[j] = i 对每个存在的集合 Kl，使 l 为大于 j 的最小值 Kl = Kj 并 Kl，破坏 Kj return extracted 2.Tarjan 的脱机最小公共祖先算法 在一棵树 T 中，两个节点 u 和 v 的最小公共祖先是这样的一个节点 w，它是 u 和 v 的祖先， 并且具有最大 的深度。 给定一棵树 T 和一个由 T 中节点的无序对构成的集合 P。希望确定 P 中每个对的最小公共 祖先。 LCA(u) { Make-Set(u) ancestor[Find-Set(u)]=u 对于 u 的每一个孩子 v { LCA(v) Union(u) ancestor[Find-Set(u)]=u } checked[u]=true 对于每个(u,v)属于 P { if checked[v]=true then { 回答 u 和 v 的最近公共祖先为 ancestor[Find-Set(v)] } } } Tarjan 算法基于深度优先搜索的框架，对于新搜索到的一个结点，首先创建由这个结点 构成的集合，再对当前结点的每一个子树进行搜索，每搜索完一棵子树，则可确定子树 内的 LCA 询问都已解决。其他的 LCA 询问的结果必然在这个子树之外，这时把子树所形 成的集合与当前结点的集合合并，并将当前结点设为这个集合的祖先。之后继续搜索下 一棵子树，直到当前结点的所有子树搜索完。这时把当前结点也设为已被检查过的，同 时可以处理有关当前结点的 LCA 询问，如果有一个从当前结点到结点 v 的询问，且 v 已被 检查过，则由于进行的是深度优先搜索，当前结点与 v 的最近公共祖先一定还没有被检 查，而这个最近公共祖先的包涵 v 的子树一定已经搜索过了，那么这个最近公共祖先一定 是 v 所在集合的祖先。 由于是基于深度优先搜索的算法，只要调用 LCA(root[T])就可以回答所有的提问了，这 里 root[T]表示树 T 的根，假设所有询问(u,v)构成集合 P。 算法导论CHAP23 图的基本算法 邻接阵：表示稀疏图比较紧凑 邻接表：要求速度，或稠密图（|E|接近|V|^2) BFS：证明 BFS 寻找最短路的正确性（344 页） DFS：时间戳 DFS 为每个节点加盖时间戳。每个节点 v 有两个时间戳：当节点 v 第一次被发现（并置为 灰色） 时记录下第一个时间戳 d[v]，当结束检查 v 的邻接表时（并置 v 为黑色）记录第二个时间戳 f[v]。 定理 6（括号定理）在对有向图或无向图 G=(V,E)的任何深度优先搜索中，对于图中任意两 节点 u 和 v 下述三个条件中有且仅有一条成立 区间[d[u],f[u]]和区间[d[v],f[v]]完全分离 区间[d[u],f[u]]完全包含于区间[d[v],f[v]]中且在深度优先树中 u 是 v 的后裔。 区间[d[v],f[v]]完全包含于区间[d[u],f[u]]中且在深度优先树中 v 是 u 的后裔。 推论 7（后裔区间的嵌入） 在有向或无向图 G 的深度优先森林中，节点 v 是节点 u 的后裔当且仅当 d[u]R。 设 p为结点 v1 到 vk 的一条最短路。对任意 i,j 有 1<=i<=j<=k，设 pij＝ 从 vi 到 vj 的 p 的子路径，则 pij 是从 vi 到 vj 的一条最短路径。 推论 2：设 G=(V,E)是有向加权图，其加权函数为 w:E->R。假设对某结点 u 和路径 p'从源 s 到结点 v 的一条 最短路径 p 可以分解为 s-p'-u->v，则从 s 到 v 的最短路径的权为 Q(s,v) = Q(s,u)+w(u,v) 松弛技术 INIT-SingleSource(G,s) for 每个顶点 v 属于 V[G] do d[v] = inf pai[v] = nil d[s] = 0 对 u,v 的松弛过程： Relax(u,v,w) if d[v] > d[u] +w(u,v) then d[v] = d[u] + w(u,v) pai[v] = u; 引理 3：设 G=(V,E)是一有向加权图，其加权函数为 w:E->R，源结点为 s。则对所有边（u,v） 属于 E 有 Q(s,v)<=Q(s,u)+w(u,v) 引理 4：设 G=(V,E)为一有向加权图，其加权函数为 w:E->R，设（u,v)属于 E，则一旦 执行 Relax（u,v,w)对边（u,v)进行松弛之后，有 d[v]<=d[u]+w(u,v)成立。 证明：显然。 引理 5：设 G=(V,E)是一有向加权图，其加权函数为 w：E->R，设 s 属于 V 为源结点，且图 G 已被过程 Init－SingleSource 初始化。则对所有 v 属于 V 有 d[v]>=Q(s,v)并且对 G 的边进行任意序列的 松弛 操作，该不等式仍成立。再者，一旦 d[v]取得了它的下限 Q(s,v)的值后，其值不会再变化。 证明：因为 d[u] +w(u,v) = d[v] < Q(s,v) <= Q(s,u)+w(u,v) 因为松弛（u,v)不改变 d[u]，故 d[v]>Q(s,v)成立。 推论 6：假设某加权函数为 W:E->R 的有向加权图中，在源结点 s 属于 V 和某指定结点 v 属 于 V 之间无路径相通。则在 Init-SingleSource(G,s)对图进行初始化后，有 d[v]=Q(s,v)。在任 意松弛操作后，等式始终成立。 重要引理：引理 7：设 G=(V,E)是一有向加权图，其加权函数为 w：E->R。设 s 属于 V 为源 结点，且对于某些结点 u，v 属于 V，设 s：u->v 是 G 的一条最短路径。假设过程 Init-SingleSource （G,s)已对 G 进行了 初始化，且随即对 G 的边执行了包含调用 Relax(u,v,w)的一个松弛操作序列。如果在调用前 的任何时刻 d[u]=Q(s,u)，则调用以后 d[v]=Q(s,v)始终保持成立。 意义：部分最优到全局最优的跳板。 Dijkstra 算法：设置结点集合 s，从源结点 s 到集合中结点最终最短路径权已确定。算法反复 挑出其最 短路径估计为最小的结点 u 属于 V-S。把 u 插入集合 S 中，并对离开 u 的所有边进行松弛。 Dijkstra(G,w,s) Init-Singlesource(G,s) s = empty Q = V[G] while ( Q != empty) do u = extract-min(Q) s = s and {u} for 每个顶点 v 属于 Adj[u] do Relax(u,v,w) 定理 10：Dijkstra 算法的正确性证明 证明：将证明对每一结点 u 属于 V，当 u 被插入集合 S 时有 d[u]＝Q(s,u)成立，且此后该等 式一直保持成立。 设 u 为插入集合 S 中的第一个满足 d[u]!=Q(s,u)的结点。 可知 u!=s，可知 u 被插入集合 S 前 S!=空。从 s 到 u 必存在某条通路，否则 d[u]=Q(s,u)＝inf， 与 d[u]!=Q(s,u)矛盾。 因为存在一条通路，所以存在一条最短路 p。路径 p 联结集合 S 中的结点 S 到 V-S 的结点 u。 考察沿 路径 p 的第一个属于 V-S 的结点 y。设 x 属于 V 是 y 的先辈。路径 p 可以分解为 s~p->x 和 y~p2->u。 （若第一个点为 u，则 d[u]=Q(s,u)，已得证） 因为 s 到 u 的最短路径上 y 出现在 y 之前且所有边的权均为非负，我们有 Q(s,y)<=Q(s,u) 因而 d[y] = Q(s,y) <= Q(s,u) <=d[u] 但因为在第 5 行选择 u 时结点 u 和 y 都属于 V-S，所以有 d[u]<=d[y]。因此 d[u]=d[y]。 最后得出结论 d[u]=Q(s,u)，这与我们对 u 的假设矛盾。 Dijkstra 算法效率：若用线性数组实现优先队列：每次 Extract_Min 为 O(v)，存在 V 次，则 为 O(v^2)。 for 中有 E 次迭代。所以整个算法运行时间 O(V^2)。 稀疏图用二叉堆比较合适。Extract_Min 需要 O(lgv)，建立需要 O(V)。更改权值用 Decrease_key。 总时间为 O((V+E)lgV)。 如果用斐波那契堆可以进一步提高效率至 O(VlgV+E)。 Bellman-Ford 算法： 负权最短路，可检测负权环，若没有可返回路径。 当图中没有由带负权值的边组成的回路时，有 n 个顶点的图中任意两个顶点之间如果存在最 短路径，此路径最多有 n-1 条边。 我们将以此为依据考虑计算从源点 v 到其它顶点 u 的最短路径的长度 dist[u]。 Bellman-Ford 方法构造一个最短路径长度数组序列 dist1 [u]，dist2 [u]，…，distn-1 [u]。其中， dist1 [u]是从源点 v 到终点 u 的只经过一条边的最短路径的长度，dist1 [u] = Edge[v][u]；dist2 [u]是从源点 v 最多经过两条边到达终点 u 的最短路径的长度，dist3 [u]是从源点 v 出发最多 经过不构成带负长度边回路的三条边到达终点 u 的最短路径的长度，…，dist n-1[u]是从源 点 v 出发最多经过不构成带负长度边回路的 n-1 条边到达终点 u 的最短路径的长度。 可以用递推方式计算 distk [u]。 dist1 [u] = Edge[v][u]； distk [u] = min { distk-1 [u], min { distk-1 [j]+ Edge[j][u] } } 设已经求出 distk-1 [j], j = 0, 1, …, n-1, 此即从源点 v 最多经过不构成带负长度边回路的 k-1 条边到达终点 j 的最短路径的长度。 从图的邻接矩阵中可以找到各个顶点 j 到达顶点 u 的距离 Edge[j][u]，计算 min { distk-1 [j]+ Edge[j][u] }，可得从源点 v 绕过各个顶点，最多经过不构成带负长度边回路的 k 条边 到达终点 u 的最短路径的长度。 Bellman-Ford(G,w,s) Init_singlesource(G,s) for i =1 to |V(G)-1| do for 每条边(u,v)属于 E(G) do RELAX(u,v,w) for 每条边(u,v)属于 E(G) do if d[v]>d[u]+w(u,v) then return FALSE return TRUE DAG_Shortest_Path(G,w,s) 对 G 进行拓扑排序 Init-singlesource(G,s) 对于拓扑排序中的每一点 u do for 每个结点 v 属于 Adj[u] do Relax(u,v,w) 用途：Pert 图分析关键路径 差分约束系统和最短路 线性程序设计：给定 m*n 矩阵 A，m 维向量 b 和 n 维向量 c，我们希望找出由 n 个元素组成 的向量 x，在由 Ax<=b 所给出的 m 个约束条件下，使目标函数 sum（cixi） [i=1~a]达到最大值 差分约束系统是线性程序设计的一个特例。 其矩阵每一行包含一个 1 和一个-1，A 的所有其它元素为 0。因此，Ax<=b 给出的约束条件 是 m 个差分 约束的集合，其中包含 n 个未知元。每个约束条件为如下形式的简单线性不等式 xj-xi<=bk. 引理 16：设 x=(x1,x2,...xn)是差分约束系统 Ax<=b 的一个解，d 为任意常数，则 x+d 也是该 系统的解。 在差分约束系统中，n×m 线性规划矩阵 A 可以被看做 n 个结点与 m 条边的图的一个关联矩 阵。 对于 i=1,2....n，图中每个结点对应于 n 个未知变量中的每一个 xi。每条有向边对应于 m 个 由两 未知数组成的不等式中的每一个不等式。 更形式化，已知某差分约束系统 Ax<=b，相应的约束图为一有向加权图 G=(V,E)，其中 V= {vo,v1,...,vn} E={(vi,vj):xj-xi<=bk 是一约束条件} 并 {(v0,v1),(v0,v2),(v0,v3).....(v0,vn)} 如果 xj-xi 是一个差分约束，则边（vi,vj)的权 w(vi,vj)=bk。从 v0 出发的每条边的权均为 0。 定理 17：已知差分约束系统 Ax<=b，设 G=(V,E)为其相应的约束图，如果 G 中不包含权为 负的回路，则 x={Q(v0,v1),Q(v0,v2),Q(v0,v3)....Q(v0,vn)} 是该系统的可行解。若 G 包含权为负的回路，则该系统不存在可行解。 证明：对于任意边 vi，vj，有 Q(v0,vj)<=Q(v0,vi)+w(vi,vj) 因此 xi＝Q(v0,vi),xj=Q(v0,vj)满足对应于边（vi,vj)的差分约束条件 xj-xi<=w(vi,vj) 思考题 对 Bellman-Ford 算法得 Yen 氏改进 在第一趟迭代之前，将一任意线性序列 v1,v2....v|v|赋值给输入图 G=(V,E)的各个结点 然后把边的集合 E 分为 Ef 和 Eb ，其中 Ef={(vi,vj) ， ij| 定义 Gf=(V,Ef),Gb=(V,Eb) 每一趟算法如下实现：按 v1,v2...v|v|的顺序访问结点，同时对从该结点出发的 Ef 中边进行 图松弛。 然后按 V|V|，。。。v1 的顺序访问结点，同时对从该结点出发的 Eb 中边进行松弛。 嵌套框序列：给定一系列框，每框有 n 个系数。满足 x1 int a[11], ans[11]; int b[1001]; int n, m, max; int dp(int i) { int j, k; for (j = 1; j < 1001; j++) b[j] = 9999; for (j = 1; j <= i; j++) b[a[j]] = 1; j = 0; do { j++; for (k = 1; k <= i; k++) if (j > a[k] && b[j - a[k]] + 1 < b[j]) b[j] = b[j - a[k]] + 1; }while (b[j] <= m); return j; } void search(int i) { int j, k; if (i > n) { if (dp(i - 1) - 1 > max) { for (j = 1; j <= 10; j++) ans[j] = a[j]; max = dp(i - 1) - 1; } return; } j = dp(i - 1); for (k = j ; k >= a[i - 1] + 1; k--) { a[i] = k; search(i + 1); } } int main() { int i; scanf("%d%d", &m, &n); max = 0; a[1] = 1; search(2); for (i = 1; i <= n; i++) printf("%d ", ans[i]); printf("\n"); printf("MAX=%d\n", max); return 0; } 2．设有 n 个正整数（n≤20），将它们联接成一排，组成一个最大的多位整数。 例如：n=3 时，3 个整数 13，312，343 联接成的最大整数为：34331213 又如：n=4 时，4 个整数 7，13，4，246 联接成的最大整数为：7424613 程序输入：n n个数 程序输出：联接成的多位数 [分析]这是一道比较成功的题目。 极易想到的算法是贪心法 - 按整数对应的字符串大到小连接，因为题目的 例子都符合，但是不难找到反例：12 121 应该组成 12121 而非 12112,那么是不 是相互包含的时候就从小到大呢？也不一定，如：12 123 就是 12312 而非 1211 2,那么情况就多了。其实本题就是用贪心法，但是贪心标准不是上述那种，而是： 如果a后接b比b后接a大，就说"a>b"。直接输出排序结果。 题目：现在小明一家过一座桥，过桥的时候是黑夜，所以必须有灯。现在小明过 桥要 1 分钟，小明的弟弟要3 分钟，小明的爸爸要6 分钟，小明的妈妈要8 分钟， 小明的爷爷要求 12 分钟。每次此桥最多可过两人，而过桥的速度依过桥最慢者 而定，而且灯在点燃 30 分钟后就会熄灭。问：小明一家如何过桥？ 参考答案：1小明与弟弟过桥，小明回来，耗时4 分钟；2小明与爸爸过河， 弟弟回来，耗时 9 分钟；3 妈妈与爷爷过河，小明回来，耗时 13 分钟；最后， 小明与弟弟过河，耗时 3 分钟，总耗时 29 分钟，多么惊险！！ Ø 复赛试题分析 1.递推（2002 年初中组 4：过河卒） [问题描述] 棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下、或者向右。同 时在棋盘上的任一点有一个对方的马（如 C 点），该马所在的点和所有跳跃一步可达的点称 为对方马的控制点，如图中的 C 点和 P1，……，P8，卒不能通过对方马的控制点。棋盘用 坐标表示，A 点(0,0)、B 点(n, m) (n,m 为不超过 20 的整数),同样马的位置坐标是需要 给出的，C≠A 且 C≠B。现在要求你计算出卒从 A 点能够到达 B 点的路径的条数。 [问题分析] 跳马是一道老得不能再老的题目，我想每位编程初学者都学过，可能是在学回溯或搜索等算 法的时候，很多书上也有类似的题目，一些比赛中也出现过这一问题的变形（如NOIP1997 初中组的第三题）。有些同学一看到这条题目就去搜索，即使你编程调试全通过了，运行时你 也会发现：当n,m=15 就会超时。 其实，本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边过来（我们称之为左点） 或是从上面过来（我们称之为上点），所以根据加法原理，到达某一点的路径数目，就等于 到达其相邻的上点和左点的路径数目之和，因此我们可以使用逐列（或逐行）递推的方法来 求出从起点到终点的路径数目。障碍点（马的控制点）也完全适用，只要将到达该点的路径 数目设置为 0 即可。 用 F[i,j]表示到达点(i,j)的路径数目，g[i,j]表示点(i, j)有无障碍，g[i,j]=0 表示无障碍， g[i,j]=1 表示有障碍。 则，递推关系式如下： F[i,j] = F[i-1,j] + F[i,j-1] {i>0 且 j>0 且 g[x, y] = 0} 递推边界有 4 个： F[i,j] = 0 { g[x,y] = 1 } F[i,0] = F[i-1,0] {i > 0 且 g[x,y] = 0} F[0,j] = F[0,j-1] {j > 0 且 g[x,y] = 0} F[0,0] = 1 考虑到最大情况下：n=20,m=20，路径条数可能会超过 MaxLongInt,所以要用高精度（使 用 Comp 类型计数即可）。 程序：见文件夹。 例 1、递推举例：储油点 [问题描述] 一辆重型卡车欲穿过 1000 公里的沙漠，卡车耗油为 1 升/公里，卡车总载油能力为 500 公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立几个贮油点，使卡 车能顺利穿越沙漠，试问司机如何建立这些贮油点？每一贮油点应存多少汽油，才能使卡车 以消耗最少汽油的代价通过沙漠？ 编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量。 No． distance(k．m．) oil(litre) 1 ×× ×× 2 ×× ×× 3 ×× ×× [问题分析] 设 dis[i]─第 i 个贮油点至终点(i=0)的距离；oil[i]─第 i 个贮油点的存贮油量。 我们可以用倒推法来解决这个问题。从终点向始点倒推，逐一求出每个贮油点的位置及 存油量。下图表示倒推时的返回点。 终点 始点 └───────────┬──┬──────────────┬┘ i=0 i=1 i=2 … …i=n 从贮油点 i 向贮油点 i+1 倒推的策略是，卡车在点 i 和点 i+1 间往返若干次。卡车每次 返回 i+1 处时正好耗尽 500 公升汽油，而每次从 i+1 处出发时又必须装足 500 公升汽油。 两点之间的距离必须满足在耗油最少的条件下使 i 点贮足 i*500 公升汽油的要求 (0≤i≤n-1)。具体地讲，第一个贮油点 i=1 应距终点 i=0 处 500km 且在该处贮藏 500 公升汽油，这样才能保证卡车能由 i=1 处到达终点 i=0 处，这就是说：dis[1]=500； oil[1]=500。为了在 i=1 处贮藏 500 公升汽油，卡车至少从 i=2 处开两趟满载油的车至 i=1 处。所以 i=2 处至少存贮 2*500 公升汽油，即 oil[2]=500*2=1000。另外，再加 上从 i=1 返回至 i=2 处的一趟空载，合计往返 3 次。三次往返路程的耗油量按最省要求只 能为 500 公升，即 d1,2 = km。 dis[2]=dis[1]+d1,2 =dis[1]+ 为了在 i=2 处贮存 1000 公升汽油，卡车至少从 i=3 处开三趟满载油的车至 i=2 处。所以 i=3 处至少存贮 3*500 公升汽油，即 oil[3]=500*3=1500。加上 i=2 至 i=3 处的二趟 返程空车，合计 5 次。路途耗油量亦应 500 公升，即 d2,3 = km。 dis[3]=dis[2]+d2,3 =dis[2]+ 依次类推，为了在 i=k 处贮藏 k*500 公升汽油，卡车至少从 i=k+1 处开 k 趟满载车至 i=k 处，即 oil[k+1]=(k+1)*500=oil[k]+500，加上从 i=k 返回 i=k+1 的 k-1 趟返程空车， 合计 2*k-1 次。这 2*k-1 次总耗油量按最省要求为 500 公升，即 dk, k+1= km。 dis[k+1]=dis[k]+dk,k+1 =dis[k]+ 最后， i=n 至始点的距离为 1000-dis[n]，oil[n]=500*n。为了在 i=n 处取得 n*500 公升汽油，卡车至少从始点开 n+1 次满载车至 i=n，加上从 i=n 返回始点的 n 趟返程空车， 合计 2*n+1 次，2*n+1 趟的总耗油量应正好为(1000-dis[n])*(2*n+1)，即始点藏油 为 oil[n]+(1000-dis[n])*(2*n+1)。 由此得出如下的程序框架（程序略）： begin k：=1；d：=500； { 从 i=1 处开始向始点倒推} dis[1]：=500；oil[1]：=500； repeat k：=k+1；d：=d+500/(2*k-1)； dis[k]：=d； oil[k]：=oil[k-1]+500； until d>=1000； dis[k]：=1000； {置始点至终点的距离值} d1：=1000-dis[k-1]； {求贮油点 k 处至始点的距离} oil[k]：=d1*(2*k+1)+oil[k-1]； {求始点藏油量} for i：=0 to k do 输出第 i 个贮油点的距离为 1000-dis[k-i]，藏油量为 oil[k-i]； end. 程序：见文件夹。 2. 动态规划（2000 年初中组 3/高中组 2: 乘积最大） [问题描述] 今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞 辰 90 周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动， 你的一个好朋友 XZ 也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道 题目： 设有一个长度为 N 的数字串，要求选手使用 K 个乘号将它分成 K+1 个部分，找出一种分 法，使得这 K+1 个部分的乘积能够为最大。 同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子： 有一个数字串：312， 当 N=3，K=1 时会有以下两种分法： 3*12=36 31*2=62 这时，符合题目要求的结果是：31*2=62 现在，请你帮助你的好朋友 XZ 设计一个程序，求得正确的答案。 [输入] 程序的输入共有两行： 第一行共有 2 个自然数 N，K（6≤N≤40，1≤K≤6） 第二行是一个长度为 N 的数字串。 [输出] 结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。 [样例输入] 4 2 1231 [样例输出] 62 [问题分析] 首先，由于问题的规模为 6<=N<=40，1<=K<=6，要在长为 N 的数字串中插入 K 个乘 号使得乘积最大，显然将会超出长整数的范围，所以运算要用高精度乘法。 其次，让我们考虑穷举的方法行不行，由组合数学知识知道：在长为 N 的数字串中插入 K 个乘号的方案有 C（N-1,K）种，极限数据等于 6500000 种插入方案，而高精度本身也很 费时间，所以穷举算法肯定会超时。看来只有找动态规划这样的高效算法了！！！ 那么如何使用动态规划呢？分析发现：问题中只有乘号插入的位置是变化的，取数字串中的 任意一段（P1 到 P2）来考虑，若能求出在其中插入 K-1 个乘号的最大乘积，则只需穷举 第 K 个乘号的插入位置 P（P 从初始的 P1+K-1 开始插入，最多插入到 P2-1 后）。该乘号 把数字串分成了两段，前半段包含 K-1 个乘号（其最大值已经算出），将它的值与后半段的 值相乘得到第 K 个乘号在位置 P 时的最大乘积。打擂台选出 P 在各个位置时得到的最大乘 积即为问题的解。 依此类推，把 K-1 的问题归结为 K-2 的情况，……，直到求在任意一段中插入 1 个乘号的 最大乘积时，需预先算出在任意一段中插入 0 个乘号时的最大乘积。而此时的值是已知的 （即为该段的数值）。假 设 C[p1,p2,K]表示在长为 N 的数字串中，从第 p1 个数字到第 p2 个数字之间插入 K 个乘号的最大乘积，动态转移方程如下： p2-1 C[p1,p2,k] = MAX （C[p1,p,k-1] * C[p+1,p2,0]） P=p1+k-1 假设输入的数字已保存在 d[1..n]中（n<=maxn=40），定义三维数组 max 存放结果， 即： var max:array[1..maxn,1..maxn,0..maxn-1] of byte; 其中 max[i,j,0] 到 max[i,j,maxn-1]存放任意一段的最大乘积。则，动态规划的初始化工作如下： for i:=1 to n-1 do for j:=i to n do begin for m:=0 to maxn-1 do max[I,j,m]:=0; {清 0} w:=0; {记录高精度数的有效位数} for m:=j downto I do begin {高精度数的初始化} max[I,j,w]:=d[m]; w:=w+1; end; end; 程序：见文件夹。 例 2.动态规划举例（2001 年高中 3：统计单词个数） [问题描述] 给出一个长度不超过 200 的由小写英文字母组成的字母串（约定：该字串以每行 20 个字 母的方式输入，且保证每行一定为 20 个）。要求将此字母串分成 k 份（1B，所以 A+B > B+A ，而实际上’32132’< ’32321’。 所以，自定义一种字符串的比较规则：即如果 A+B>B+A,则我们认为 A>B。且可以证明： 如果 A+B>=B+A,B+C>=C+B,则一定有：A+C>=C+A。 这样一来，程序就很简单了。分 3 步，先把 n 个数字转换成字符串存储；再按照自定义 的规则把 n 个字符串排序；最后按照从大到小的顺序输出这些字符串。 小结：有些问题看起来是数学问题，认真分析会发现用字符串处理很简单。另外，一定 要掌握有关字符串的各种函数，以免用到时自己编子程序。 程序：略。 4.贪心（删数问题） [问题描述] 键盘输入一个高精度的正整数 n（小于等于 240 位），去掉其中任意 s 个数字后，剩下的数 字按原次序将组成一个新的正整数。编程对给定的 n 和 s，寻找一种方案，使得剩下的数字 组成的新数最小。 [输入格式] n s [输出格式] 顺序列出 s 个被删去的数字。 [算法分析] 首先，这是一个高精度数。但是否一定用数组存放这个数呢？这要看具体的算法实现。 由于正整数 n 的有效数位为 240 位，因此我们采用字符串类型存贮 n。 为了尽可能逼近目标，我们的“贪心策略”是：每一步总是选择一个使剩下的数最小的数字删 去，即按高位到低位的顺序搜索，若各位数字递增，则删最大（最后）的数字；否则删第一 个递减区间的首字符，这样便形成了一个新数串。然后回到串首，按上述规则删下一个数 字，……，依次类推，直到删除了 s 个数字为止，输出剩余部分即可。 例如：n=‘1 7 8 5 4 3’ s=4 删数过程如下： n=‘1 7 8 5 4 3’ 删‘8’ ‘1 7 5 4 3’ 删‘7’ ‘1 5 4 3’ 删‘5’ ‘1 4 3’ 删‘4’ ‘1 3’ 这样删数问题与“如何寻找递减区间首字符”这样一个简单的问题对应起来。按贪心策略编制 的程序框架为： begin 输入 n,s； while s>0 do begin i：=1； {从串首开始找} while (i1)and (n[1]=‘0’) do delete(n，1，1)； {删去串首的无用零} 输出 n； end. 程序：略。 例 3、贪心举例：取数游戏 [问题描述] 给出 2*n个自然数。游戏双方分别为A方（计算机方）和B方（对奕的人）。只允许从数列两 头取数。A先取，然后双方依次轮流取数。取完时，谁取得的数字总和最大为取胜方；双方 和相等，属于A胜。试问A方可否有必胜的策略 [输入] 2*n 个自然数 [输出] 前 2*n 行为游戏经过。每两行分别为 A 方所取的数和 B 方所取的数，其中 B 方取数时应给 予提示，让游戏者选择取哪一头的数（L/R—左端或右端）。最后一行分别为 A 方取得的数 和和 B 方取得的数和。 [问题分析] 设自然数列:7 9 3 6 4 2 5 3 我们设计一种方案，从数大的一头让 A、B 轮流取两个连续数： A 方：7 3 4 5 B 方：9 6 2 3 由此得出： A 方取得的数和为 7+3+4+5=19 B 方取得的数和为 9+6+2+3=20 按照规则，判定 A 方输。虽然 A 方败给 B 方，但是我们却发现了一个有趣的事实：A 方取 走偶位置的数后，剩下两端数都处于奇位置；反之，若 A 方取走奇位置的数后，剩下两端 数都处于偶位置。即无论 B 方如何取法，A 方即可以取走奇位置的所有数，亦可以取走偶 位置的所有数。由此萌发一种“贪心策略”：让 A 方取走“数和较大的奇（或偶）位置上的所 有数”，则 A 方必胜。这样，取数问题便对应于一个简单问题：让 A 方取奇偶位置中数和较 大的一半数。设 j 为 A 取数的奇偶位置标志，则： 设 SA，SB 分别表示 A 方取数和，B 方取数和（SA≥SB）；a 存储 2*n 个自然数序列； lp，rp 为序列的左端位置和右端位置；ch 为 B 方取数的位置信息（’L’或’R’）；则，程序框 架如下： begin SA：=0；SB：=0； {计算 A 方取数和、B 方取数和，A 方取数的位置标志} for i：=1 to n do begin SA：=SA+a[2*i-1]；SB：=SB+a[2*i]； end； if SA>=SB then j:=1 else begin j:=0；交换 SA 和 SB；end； lp：=1；rp：=2*n； for i：=1 to n do {A 方和 B 方依次进行 n 次对奕} begin if ((j=1) and (lp mod 2=1)) or ((j=0)and (lp mod 2=0)) {若 A 方应取奇位置数且左端位置为奇， 或者 A 方应取偶位置数且左端位置为偶， 则 A 方取走左端位置的数} then begin 输出 A 方取 a[lp]；lp：=lp+1；end else begin 输出 A 方取 a[rp]；rp：=rp-1；end；{否则 A 方取走右端位置的数} 输出提示信息：B 方的取数位置（L/R）； repeat 读 ch； if ch=‘L’ then begin 输出 B 方取 a[lp]；lp：=lp+1；end； if ch=‘R’ then begin 输出 B 方取 a[rp]；rp：=rp-1；end； until ch {‘L’，’R’}； end； 输出 A 方取数的和 SA 和 B 方取数的和 SB； end. 程序：略。 5．穷举（2000 年高中组 1：进制转换） [问题描述] 我们可以用这样的方式来表示一个十进制数： 将每个阿拉伯数字乘以一个以该数字所处位 置的（值减１）为指数，以１０为底数的幂之和的形式。例如：１２３可表示为１＊１０２ ＋２＊１０１＋３＊１００这样的形式。 与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置 的（值－１）为指数，以２为底数的幂之和的形式。一般说来，任何一个正整数Ｒ或一个负 整数－Ｒ都可以被选来作为一个数制系统的基数。如果是以Ｒ或－Ｒ为基数，则需要用到的 数码为０，１，．．．．Ｒ－１。例如，当Ｒ＝７时，所需用到的数码是０，１，２，３，４， ５和６，这与其是Ｒ或－Ｒ无关。如果作为基数的数绝对值超过１０，则为了表示这些数码， 通常使用英文字母来表示那些大于９的数码。例如对１６进制数来说，用Ａ表示１０，用Ｂ 表示１１，用Ｃ表示１２，用Ｄ表示１３，用Ｅ表示１４，用Ｆ表示１５。 在负进制数中是用－Ｒ作为基数，例如－１５（十进制）相当于１１０００１（－２进制）， 并且它可以被表示为２的幂级数的和数： 110001＝1*（-2）５ + 1*（-2）４ + 0*（-2）３ + 0*（-2）２ + 0*（-2）１ + 1* （-2）０ [问题求解] 设计一个程序，读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制 下的数： －Ｒ∈｛－２，－３，－４，．．．，－２０｝ [输入] 输入的每行有两个输入数据。 第一个是十进制数Ｎ（－32768＜＝Ｎ＜＝32767）； 第二个是负进制数的基数－Ｒ。 [输出] 结果显示在屏幕上，相对于输入，应输出此负进制数及其基数，若此基数超过１０，则参照 １６进制的方式处理。 [样例输入] ３００００ －２ －２００００ －２ ２８８００ －１６ －２５０００ －１６ [样例输出] ３００００＝１１０１１０１０１０１１１００００（ｂａｓｅ －２） －２００００＝１１１１０１１０００１０００００ （ｂａｓｅ －２） ２８０００＝１９１８０ （ｂａｓｅ －１６） －２５０００＝７ＦＢ８ （ｂａｓｅ －１６） [问题分析] 其实，本题拿到手的第一个想法是进制转换的常规方法“除 R 取余，除尽为止，倒取输出”， 但当你用一个样例去试的时候，发现毫无规律（如果有的人习惯不好，拿到手自以为是，不 喜欢用草稿纸，则会沿着死路往前走）。 其实，分析一下问题的规模 N（注意这是第 1 题），-32767-32768！！！穷举。对任一个-R 进制数 k(从 0 开始)，计算它对应的十进制数是多少，如果等于 N，则输出这个-R 进制数， 否则继续找下一个-R 进制数。 思考：-R 进制数好象没有符号位哎：） 程序：见文件夹。 6．简单搜索、回溯（1999 年高中组 4：邮票面值设计） [问题描述] 给定一个信封，最多只允许粘贴 N 张邮票，计算在给定 K（N+K≤40）种邮票的情况下（假 定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值 MAX，使在 1～MAX 之 间的每一个邮资值都能得到。 例如，N=3，K=2，如果面值分别为 1 分、4 分，则在 1 分～6 分之间的每一个邮资值 都能得到（当然还有 8 分、9 分和 12 分）；如果面值分别为 1 分、3 分，则在 1 分～7 分 之间的每一个邮资值都能得到。可以验证当 N=3，K=2 时，7 分就是可以得到的连续的邮 资最大值，所以 MAX=7，面值分别为 1 分、3 分。 样例输入与输出： INPUT OUTPUT N=3 K=2 1 3 MAX=7 [问题分析] 首先，看数据规模 n+k<=40，显然很大，所以有的选手想用动态规划，但注意本题具有 明显的后效性（前面方案的不同使得构成某面值的邮票数不同），所以不满足动态规划的条 件。 那么，解决这类问题只能用递归搜索了。但很快有人发现：搜索所能解决的问题规模远远达 不到题目的要求，一般搜索到 n,k 同时超过 6，就不行了。而实际的测试数据也就到 n=10,k=5,且 n+k<13。 所以，我们总结出分区联赛的题目难易程度，其实和数据规模（尤其是实际测试数据）息息 相关。有的题目很难，但实际的测试数据很简单（小）；而有的题目算法和思想很简单，但 数据规模巨大。如果题目难度大且测试数据很刁钻、很大，那么得分率就会极低，这时就相 当于去掉这一题比赛（比如 2002 高中组的矩形覆盖问题）。这种题目这几年基本上是用搜 索！所以，选手做题时应充分估计 4 个题目的难度和命题人的命题动机。对难度小的、有 把握的要拿满分；对于难度大，但小数据能很容易算出的要把该拿的分拿住；对于自己能力 以外的，不要浪费宝贵的时间（记住：评奖的原则是名次，而不是分数和哪一条题目）。 回到原题中来，首先面值为 1 的邮票是必须的；此后每加进一种面值都要把当前所能取得 的金额记下来。通过 k-1 次添加得到一种方案。穷举所有的方案得到最优解。 在搜索的过程中，对数据的记录方式很关键。如果仅仅记录一个金额能否被达到，则这样的 记录基本上没有用，因为下一次添加邮票时，不知能否从这个金额出发再加上新邮票，推导 出达到哪些新面值，必须全部重算，浪费了大量时间；所以，我们记录最少要用几张邮票达 到一个面值，这样有利于添加新邮票时迅速判断可行性。 搜索一种新邮票面值的起点（即新邮票的选择策略）应该是：从上一个面值加 1 开始，直 到当前连续取得的最大金额加 1。因为过大会造成不连续，过小得不到最优解。 程序：见文件夹。 7．搜索+剪枝优化+构造（1997 年高中组 1：素数方阵） [问题描述] 在 N*N 的棋盘上（1≤N≤10），填入 1，2，…，N*N 共 N*N 个数，使得任意两个相邻的 数之和为素数。 其相邻数的和为素数的有： 1+2，1+4，4+3，2+3 例如：当 N=2 时，有： 1 2 4 3 当 N=4 时，一种可以填写的方案如下： 1 2 11 12 16 15 8 5 13 4 9 14 6 7 10 3 在这里我们约定：左上角的格子里必须填数字 1。 程序要求： 输入：N； 输出：如有多种解，则输出第一行、第一列之和为最小的排列方案；若无解，则输出 “NO！”。 [问题分析] 由于素数的变换是没有规律的，本题只能搜。因为 N 的值是从 1 到 10 的之间的任意一个 自然数，每个方格中的数字不相同，所以采用递归回溯的方法实现。具体讲，就是将所有方 格编一个次序，根据“如有多种解，则输出第一行、第一列之和为最小的排列方案“这句话， 填数的顺序应是先填第一行第一列（1），以后选择填入的数应该从小到大依次选择，首先 选一个 2 到 N*N 之间的自然数填入第一行第二列，要求填入的数与已填的相邻方格中的数 之和为素数；然后再用相同的方法填第一行的第三列到第 N 列，填完第一行后，再依次填 第一列中的第二行到第 N 行。依此类推，再填第二行的第二列到第 N 列，再填第二列的第 三行到第 N 行，……，直到右下角最后一个数填好为止（再按要求输出）。 在填数的过程中有几个要求：一要保证填入的数没用过（很简单，设一个 used[1..n*n]， 值为布尔型）；二是当前格子选不到数填时要回溯，……，直到所有情况都搜索到了（回溯 的控制）；三是判断填入的数是否合法（类似于 N 皇后问题的判断合法性）。 对于第三个问题，如果每填入一个数，都要判断它与上方和左方的格子中的数之和是否为素 数，效率会很低。所以想到了用构造（查表）法判断素数。因为任意一个格子的最大数为 N*N，所以相邻两个格子的数之和最大为 2N*N。即把 1 到 2N*N 中的素数求出来保存好 （200 以内的素数太简单了），然后每次判断只要查表了。 小结：1.素数总是一奇一偶的和，所以，行列上肯定是奇数偶数相隔的，优化？ 2.如果去掉 a[1,1]=1 这个约定，则发现：只有当 a[1,1]中填奇数时问题才有可能有 解，为什么？因为 1..n*n 个数中奇数的个数一定大于等于偶数的个数，再结合 1。 3.求所有解及总数。 程序：见文件夹。 发表于 dayu ( 2007 年 11 月 13 日, 08:31:10 AM CST ) Permalink 评论 [0] WEDNESDAY 2007 年 10 月 24 日 初赛题 10. 一位艺术史学家有 20000 幅 1024 * 768 的真彩色图像，如果将这些图像以 位图形式保存 在 CD 光盘上（一张 CD 光盘的容量按 600M 计算），大约需要（ ）张 CD 光盘。 A. 1 B. 10 C. 100 D. 1000 E. 10000 <7> 为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为前缀{运 算符在前，如 X/Y 写为/XY} 和后缀 { 运算符在后，如 X/Y 写为 XY/}的表达形式。 在这样的表示中可以不用括号即可确定求值的顺序，如： （P+Q）*（R-S）→*+PQ-RS 或 → PQ + RS -* ① 试将下面的表达式改写成前缀与后缀的表示形式： A+B*C/D A-C*D+B∧E ② 试将下面的前缀表示还原成中缀的表示形式，同时写出后缀表示： +△A *B△C {前缀式中△表示一元运算符取负号，如△A 表示（-A）} 设数组 A[10..100,20..100] 以行优先的方式顺序存储，每个元素占 4 个字节， 且已知 A[10，20]的地址为 1000，则 A[50，90]的地址是 一个向量第一个元素的存储地址是 100，每个元素的长度是 2，则地 5 个元素的 地址是（ ）。 A）110 B）108 C）100 D）109 15．已知 A = 35H，A /\ 05H \/ A /\ 30H 的结果是：（ ）。 A）30H B）05H C）35H D）53H 17．按照二叉数的定义，具有 3 个结点的二叉树有（ ）种。 A）3 B）4 C）5 D）6 4.满二叉树的叶结点个数为 N，则它的结点总数为（ ）。 A. N B. 2 * N C. 2 * N – 1 D. 2 * N + 1 E. 2N – 1 20．设栈 S 和队列 Q 的初始状态为空，元素 e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6 依次通过栈 S，一个元素出栈后即进入队列 Q，若出队的顺序为 e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈 S 的容量至少应该为（ ）。 A）2 B）3 C）4 D）5 设有一棵 k 叉树，其中只有度为0和k两种结点，设 n 0 ，n k ，分别表示度 为 0 和度为 k 的结点个数，试求出 n 0 和 n k 之间的关系（n 0 = 数学表达式， 数学表达式仅含 n k 、k 和数字）。 在 Pascal 语言中，表达式 (21 xor 2)的值是（ ） A. 441 B. 42 C.23 D.24 E.25 4. 完全二叉树的结点个数为 4 * N + 3，则它的叶结点个数为（ ）。 A. 2 * N B. 2 * N - 1 C. 2 * N + 1 D. 2 * N - 2 E. 2 * N + 2 13. 二叉树 T 的宽度优先遍历序列为 A B C D E F G H I，已知A是C的父结点， D 是 G 的 父结点，F 是 I 的父结点，树中所有结点的最大深度为 3（根结点深度设为 0）， 可知 E 的父结点可能是（ ）（多）。 A. A B. B C. C D. D E. F 14. 设栈 S 的初始状态为空，元素 a, b, c, d, e, f, g 依次入栈，以下出栈序 列不可能出现的有 （ ）。（多） A. a, b, c, e, d, f, g B. b, c, a, f, e, g, d C. a, e, c, b, d, f, g D. d, c, f, e, b, a, g E. g, e, f, d, c, b, a 发表于 dayu ( 2007 年 10 月 24 日, 11:14:17 AM CST ) Permalink 评论 [0] 题 1、 计算 ex，lnx。X=1，2，3…..10 2、 计算 ex，lnx。X=1.1，1.2，1.3…..2.0 3、 计算 10 个数的和、平均值、积 4、 输入 n，计算 n 的阶乘(n!) 5、 计算 1！，2！….20! 6、 求两个数的最大公约数和最小公倍 数 7、 输入字母 a、b….z，反序输出 8、 求菲波拉切数 发表于 dayu ( 2007 年 10 月 24 日, 11:13:23 AM CST ) Permalink 评论 [0] jinming const m=40; type yu= array[1..m] of integer; yu1=array[1..4,1..m] of integer; var v,w,q:yu; e,i,j,k,t,n,l:integer; f:array[0..40,0..80]of longint; p,v1:yu1; {function fla(var r:yu;f:integer):boolean; var flag:boolean; i:integer; begin flag:=true; for i:=1 to 40 do if (r[i]=f) then begin flag:=false; break;end; fla:=flag; end;} begin readln(t,n); for i:=1 to n do readln(v[i],w[i],q[i]); i:=1; j:=1; while i<=n do begin if q[i]=0 then begin v1[j][1]:=v[i];p[j][1]:=v[i]*w[i]; inc(j); end else begin e:=q[i]; v1[e][2]:=v[e]+v[i];v1[e][3]:=v[e]+v[i+1];v1[e][4]:=v[e]+v[i]+v[i+1]; p[e][2]:=v[e]*w[e]+v[i]*w[i];p[e][3]:=v[e]*w[e]+v[i+1]*w[i +1];p[e][4]:=v[e]*w[e]+v[i]*w[i]+v[i+1]*w[i+1]; inc(i); end ; inc(i); end; for i:=1 to t do f[0][i]:=0; for i:=1 to j-1 do for l:=0 to t do for k:=1 to 4 do begin if (l>v1[i][k]) and ((f[i-1][l-v1[i][k]]+p[i][k])>f[i-1][l]) then begin f[i][l]:=(f[i- 1][l-v1[i][k]]+p[i][k]); end else f[i][l]:=f[i-1][l]; end; writeln(f[j-1][t]); for i:=1 to j-1 do for l:=1 to 4 do writeln(p[i][l]); end. 发表于 dayu ( 2007 年 10 月 24 日, 11:12:00 AM CST ) Permalink 评论 [0] 金明的预算方案 明的预算方案 (budget.pas/c/cpp) 【问题描述】 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专 用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪 些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。今天一早，金明就开 始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的， 下表就是一些主件与附件的例子： 主件 附件 电脑 打印机，扫描 仪 书柜 图书 书桌 台灯，文具 工作椅 无 如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、1 个或 2 个附件。附件不再有从属于自己的附件。金明想买的东西很多， 肯定会超过妈妈限定的 N 元。于是，他把每件物品规定了一个重要度，分为 5 等：用整数1~5 表示，第5 等最重要。他还从因特网上查到了每件物品的价格（都 是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件 物品的价格与重要度的乘积的总和最大。 设第 j 件物品的价格为 v[j]，重要度为 w[j]，共选中了 k 件物品，编号依 次为 j1，j2，……，jk，则所求的总和为： v[j1]*w[j1]+v[j2]*w[j2]+ …+v[jk]*w[jk]。（其中*为乘号） 请你帮助金明设计一个满足要求的购物单。 【输入文件】 输入文件 budget.in 的第 1 行，为两个正整数，用一个空格隔开： N m （其中 N（<32000）表示总钱数，m（<60）为希望购买物品的个数。） 从第 2 行到第 m+1 行，第j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q （其中 v 表示该物品的价格（v<10000），p 表示该物品的重要度（1~5）， q 表示该物品是主件还是附件。如果 q=0，表示该物品为主件，如果 q>0，表示 该物品为附件，q 是所属主件的编号） 【输出文件】 输出文件 budget.out 只有一个正整数，为不超过总钱数的物品的价格与重 要度乘积的总和的最大值（<200000）。 【输入样例】 1000 5 800 2 0 400 5 1 300 5 1 400 3 0 500 2 0 【输出样例】 2200 发表于 dayu ( 2007 年 10 月 24 日, 11:11:22 AM CST ) Permalink 评论 [0] 算法实例－关于旅行者的背包问题 算法实例－关于旅行者的背包问题 基本问题： 0/1 背包问题中，需要对容量为 C 的背包进行装载。从 N 个物品中选取装入 背包的物品，每件物品 I 的重复为 W(I)，价值为 P(I)。如何装入价值最大的物 品？ 算法： 贪心准则 1－从剩余的物品中找出一个可以装入背包的价值最大的物品。 贪心准则 2－从剩余的物品中找出可以装入背包的重量最小的物品。 贪心准则 3－计算价值密度 P(I)/W(I)。从剩余的物品中选择可装入包的 P/W(I) 物品。 贪心算法之 K 阶优化－从答案中取出 K 件物品，并放入另外K 件，获得的结 果不会比原来的差。这样优化整个放入物品的序列。 动态规划－用递归进行计算求解。每一步求出基于现在状况下的最优解。（特 点－计算复杂） 回溯算法－首先形成一个递归算法，去找到可获得的最大收益。即列出所有 的候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找出所需 要的解。（特点－候选解数量庞大） 变形问题： ·货郎的背包 ·野外生存者的背包 ·公司经理（？）的背包。