程序员面试题精选100题(经典!)

所需积分/C币:20 2013-03-19 15:49:18 11.41MB PDF

一份可以让大家在求职时更能自信的题解,经典的100题,让大家可以感受到算法的经典,当然,自己要更加努力,要懂得举一反三才能更上一层楼!
f(arIght) while(pTemp->m pLeft) prer p pfemp->m pLeft //If the current node is the left child of its parent // return the greatest node ir the tree whose root is the current node Ise while(p'lemp->m pRight pTemp= pTemp->m pRighti return pTeropi ////// / Covert a binary search tree into a sorted double-linked list // Input: the head of tree // Outout: the head of sorted double-linked list ESTreeNode* Convert(BSTreeNcCe* pHeadofTree) // As we want o 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 //工aput: pNode the head of the sub tree lastNodelnlist he tail of the double-linked 七 ///////// vcid ConvertNode(3sTreeNode* pNode, BSTreeNode*& pLastNodeinList) if(pNode = NULL) return BSTreeNode * pcurrent= pNodei // Convert he left sub-tree if (pCurren-->m pleft ! NULL) ConvertNode(pcurrent->m pleft, plastNodeInList)i Put the current node into the double-linked lis- pCurrent->m pLeft= pLastNodeInlisti if(pLastNodeInList != NUlL LastNodeInList->m pRight Current pLastNodeInlist pCurrenti // Convert he right sub-tree if (pCurren-->m pRight ! NULL onvertNode(pCurrent->m pRight, plastNodeinlist)i / Covert a binary search tree into a sorted double-linked list / Input: pHeadofTree -the head of tree // Outout: the head of sorted double-linked list ESTreeNodex Convert solutionl(3STreeNode* pHeadofrree BSTreeNode pLastNodeInList NUlLi ConvertNode(pHeadofrree, pLastNodelnList)i // Get the head of the double-linked list BSTreeNode *pHeadoflist. plastNodeinlisti while(pHeadoflist & pHeadoflist->m pLeft pHeadofList= pHeadoflist->m plefti return pHeacoflisti 程序员面试题精选100题(02)-设计包含mn函数的栈 题日:定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及 pop的时间复杂度都是O(1) 分析:这是去年 google的道血试题。 我看到这道题目时,第一反应就是每次push一个新元素时,将栈里所有逆序元素排序。这样栈顶元素将 是最小元素。但由于不能保证最后push进栈的元素最先H栈,这和思路设计的数据结构已绎不是一个栈 在栈里添加一个成员变量存放最小元素(或最小元素的位置)。每次push一个新元素进栈的时候,如果 该元素比当前的最小元素还要小,则更新最小元素。 乍一看这样思路挺好的。但仔细一想,该思路存在一个重要的问题:如果当前最小元素被pop出去,如何 才能得到下一个最小元素? 因此仅仅只添加一个成员变量存放最小元紊(或最小元素的位置〕是不够的。我们需要一个辅助栈。每次 push一个新元素的时候,同时将最小元素(或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结 构,用最小元素的位置将能减少空间消耗)push到辅助栈中;每次pop一个元素出栈的时候,同时pop 辅助栈。 参考代码: include <deque> include <asser=.h> template <typename T> class cstackWithMin public CStackWithMir(void)[] virtual -CS-ackwithMin(vcid)I T& top (void)i const T& tcp(void)consti void push (const T& value )i void pop (vcid)i const T'& min(void) const private: T>m datai// theelements of stack size t>m minIndexi// the indicesof mir imum elements }; // get the last element of mutable stack template < typename T> T& CStackwithMin<I>:: top( return m data pack(i // get the last element of non-mutable stack template <typename T> const T& CStackWithMin<T>:: top()const eturn m data back( // insert an elment at the end of stack temp late <typename T> void CStackiithMin<T>:: push(const T& value) append the data into he end of m data m data push back(value) se- the index of minimum e lment in m data a- the end of m mintndex if (im ImLinIndex size(==0 m minindex. push back(0); lse if(value m data lm mintndex back()j In minIndex push kack(in data size()-1)i else m minIndex. push back(m minIndex back())i // erease the element at the end of stack temp late <typename T> void CStackwithMin<T>:: pop( pop m daza ta pop back()i // pop m mindex In ninIndex pop back()i // cet the minimum element of stack template <typename T> const. T& CStackWithMin<T>:: in() const ssert(m daca size(>0)i ssert(m minIndex. return m data[m minIndex back(li 举个例子演示上述代码的运行过程: 步骤 数据栈辅助栈 最小值 1. push 3 2. push 4 3,4 3. push 2 3,4,2 3321 4. push 1 3,4 7. push 0 3,4,0 讨论:如果思路正确,编写上述代码不是一件很难的事情。但如果能注意一些细芍无疑能在面试屮加分。 比如我在上面的代码中做∫如下的工作: 用模板类实现。如果别人的元素类型只是int类型,模板将能给面试官带来好印象 两个版本的top函数。在很多类中,都需要提供 const和非 const版本的成员访问函数 min函数中 assert。把代码写的尽量安全是每个软件公司对程序员的要求; 添加一些注释。注释既能提高代码的可读性,乂能增加代码量,何乐而个为? 总之,在面试时如果时间允许,尽量把代码写的漂亮一些。说不定代码中的几个小亮点就能让自己轻松拿 到心仪的Ofer PS:每当push进一个新元素,若比当前最小元素小,则将它进栈,并将它的 index 进最小辅助栈;若大于当前最小元素,则将它进栈,并将当前最小元素 index 进最小辅助栈(可以重复进栈多次)! 程序员面试题精选100题(03)-求子数组的最大和 题日:输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个 子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n) 例如输入的数组为1,-2,3,10,-4,7,2,-5和最大的子数组为3,10,-4,7,2因此输出为该子数维的和18 分析:本题最初为2005年浙江大学计算机系的考研题的最后一道程序设计题,在2006年里包括 google 在内的很多知名公司都把本题当作面试题。由于本题在网络中广为流传,本题也顺利成为2006年程序员 面试题中经中的经典 如果不考虑时间复杂度,我们可以枚举出所有子数组并求出他们的和。不过非常遗憾的是,由于长度为n 的数组有O(n)个子数组;而求一个长度为n的数组的和的时间复杂度为on)。因此这种思路的时间是 o(n3) 很容易理解,当我们加上一个正数时,和会增加;当我们加上一个负数时,和会减少。如果当前得到的和 是个负数,那么这个和在接卜来的累力中应该抛弃并重新清零,不然的话这个负数将会减少接下来的和。 基于这样的思路,我们可以写出如下代码 参考代码 ////// / Find the greatest sun of all sub-arrays /7 Return value: if the input is valid, return true, cherise return false //////////// /////// bcol FindGreatestsumofSubArray int *pData /an array unsigned in= 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 nt nCur Su. nGreatestsum =0 for(unsigned int i=0i i nLength; ++i) nCurSum + oData] // if the current su. is negative, discard it if(ncurSum 0) n CurSum =0 if a greater sum is found, update the greatest sum if(nCur Sum nGreates-Sum nGreatestsum nCursumi //if all data are negative, find the greatest element in the array f(nGreates-sL nGreates-Sum pDataloji for(unsigned int i =l; i s nLength; ++i) if(pData[i] > gReatest Sum nGreatestsum pData[ili return true; 讨论:上述代码中有两点值得和大家讨论一下 函数的返回值不是子数组和的最大值,而是一个判断输入是否有效的标志。如果函数返回值的是子数 组和的最人值,那么当输入一个空指针是应该返回什么呢?返回0?那这个函数的用户怎么区分输入无效 和子数组和的最大值刚好是0这两中情况呢?基于这个考虑,本人认为把子数组和的最大值以引用的方式 放到参数列表中,同时让函数返回一个函数是否正常执行的标志。 输入有一类特殊情况需要特殊处理。当输入数组中所冇整数都是负数时,子数组和的最大值就是数组 中的最大元素。 《编程珠机》第八章,8.4扫描算法。 采用类似分治算法的道理:前i个元素中,最大综合子数组要么在i-1 个元素中( maxsofar),要么截止到位置i( maxendinghere)。 程序员面试题精选100题(04)一在二元树中找出和为某一值 的所有路径 题日:输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条 眳径。打印出和与输入整薮相等的所有路径。 例如输入整数22和如下二元树 10 512 47 则打印出两条路径:10,12和10,5,7。 二元树结点的数据结构定义为 struct BinaryTreeNode / a ncde in the binary tree nt In nValue;// value of node BinaryTreeNode *m pLeft; / left child of node BinaryTreeNode *m pRighti / right child of node 分析:这是百度的一道笔试题,考查对树这种基本数据结构以及递归函数的理解。 当访问到某一结点时,把该结点添加到路径上,并累加当前结点的值。如果当前结点为叶结点并且当前路 径的和刈好等于输入的整数,则当前的路径符合要求,我们把它打印出来。如果当前结点不是叶结点, 继续访问它的子结点。当前结点访问结束后,递归函数将自动叫到父结点。因此我们在函数退出之前要在 路径上删狳当前结点并諴去当前结点的值,以确保返回父结点酎路径刚好是根结点到父结点的路径」我们 不难看岀保存路径的数据结构实际上是一个栈结构,因为路径要与递归调用状态一致,而递归调用本质就 是一个压栈和出栈的过程。 参考代码: / Find paths whose sun equal to expected sum vcid findpath BinaryTreeNode* pTreeNode, / a node cf binary tree int expectedsum, / the expected sum std:: vector<int>&path /,/ a pathfrom roct to current node int∝ current Sun / the sun of path if(! pTreeNcde) return currentsum + oTreeNode->m nValue

...展开详情
试读 96P 程序员面试题精选100题(经典!)

评论 下载该资源后可以进行评论 17

foreverusr 资料不太全,只有40道
2017-06-17
回复
h81_ming 终于找到了,CSDN很强大,看完后,面试信心大增。
2015-03-28
回复
cybersword 内容很好,对笔试帮助很大,只是题目大概只有四十道左右。。不全
2014-10-01
回复
xmqs0503 资料很有用 谢谢分享
2014-08-25
回复
山地上的垂钓者 内容很好,值得学习,不过不全
2014-08-01
回复
lr0316 挺好的,很有帮助的一个资料,多谢啦
2014-07-06
回复
DavinaT91 资料很有用 谢谢分享
2014-05-20
回复
kevinyao0126 试题没有100道,不过有用的还不少!
2014-03-26
回复
chengtao786 题目不全,但是帮助还是很大的
2014-03-13
回复
fighting-冲 题目不错。题目不到100题
2014-02-18
回复
img
flydingdang

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    程序员面试题精选100题(经典!) 20积分/C币 立即下载
    1/96
    程序员面试题精选100题(经典!)第1页
    程序员面试题精选100题(经典!)第2页
    程序员面试题精选100题(经典!)第3页
    程序员面试题精选100题(经典!)第4页
    程序员面试题精选100题(经典!)第5页
    程序员面试题精选100题(经典!)第6页
    程序员面试题精选100题(经典!)第7页
    程序员面试题精选100题(经典!)第8页
    程序员面试题精选100题(经典!)第9页
    程序员面试题精选100题(经典!)第10页
    程序员面试题精选100题(经典!)第11页
    程序员面试题精选100题(经典!)第12页
    程序员面试题精选100题(经典!)第13页
    程序员面试题精选100题(经典!)第14页
    程序员面试题精选100题(经典!)第15页
    程序员面试题精选100题(经典!)第16页
    程序员面试题精选100题(经典!)第17页
    程序员面试题精选100题(经典!)第18页
    程序员面试题精选100题(经典!)第19页
    程序员面试题精选100题(经典!)第20页

    试读已结束,剩余76页未读...

    20积分/C币 立即下载 >