4.在二元树屮找出和为某一值的所有路径 题日:输入一个整数和一棵二元树、 从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径 打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 10 512 47 则打印出两条路径:10.12和10,5, 元树节点的数据结构定义为 struct Binary TreeNode 'a node in the binary tree int m nvalue://value of node Binary TreeNode *m pLeft; //left child of node Binary TreeNode *m pRight; right child of node 5查找最小的k个元素 题目:输入n个整数,输出其中最小的k个。 例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4 第6题 腾讯面试题 给你10分钟时间,根据上排给出十个数,在共下排填出对应的十个数 要求下排每个数都是先前上排那十个数在下排出现的次数。 上排的十个数如下 0,1,2,3,4,5,6,7,8,9】 初看此题,貌似很难,10分钟过去了,可能有的人,题目都还没看懂。 举一个例子, 数值:0,1,2,34,5,6,7,8,9 分配:6,2.,1,0,0,0,1,0.,0,0 0在下排出现了6次,1在下排出现了2次, 2在下排出玩了1次,3在下排出现了0次 以此类推. 第7题 微软业院之编程判断俩个链表是否相交 给出俩个单向链表的头指针,比如h,h2,判断这俩个链表是否相交。 为了简化问题,我们假设俩个链表均不带环。 问题扩展 1如果链表可能有环列? 2如果需要求出俩个链表相交的第一个节点列? 第8题 此贴选一些比较怪的题,,由于其屮题目本身与算法关系不大,仅考考思维。特此并作一题。 1有两个房间,一间房里冇三盏灯,另一间房有控制着三盏灯的三个开关,这两个房间是分 割开的, 从一间里不能看到另一间的情况。 现在要求受训者分別进这两房间一次,然后判断出这三盏灯分别是由哪个开关控制的。 有什么办法呢? 2你让一些人为你工作了七大,你要用一根金条作为报酬。金条被分成七小块,每大给出 块 如果你只能将金条切割两次,你怎样分给这些工人? ★用一种算法来颠倒一个链接衣的顺序。现在在不用递归式的情况下做一遍 ★用一种算法在一个循环的链接表里插入一个节点,但不得空越链接表。 ★用一种算法整理一个数组。你为什么选择这种方法? ★用一种算法使通用字符串相匹配。 ★颠倒一个字符串。优化速度。优化空间: ★颠倒一个句子中的词的顺序,比如将“我叫克丽丝”转换为“克丽丝叫我”,实现速度最 快,移动最少。 ★找到一个子字符串。优化速度。优化空间。 ★比较两个字符串,用O(n)时间和恒量空间 ★假设你有一个用1001个整数组成的数组,这些整数是仟意排列的,但是你知道所有 的整数都在1到1000(包括1000)间。此外,除一个数字出现两次外,其他所有数字只出 现一次 。假设你只能对这个数红做一次处理,用一种算法找出重复的那个数字。 如果你在运算中使用了辅助的存储方式,那么你能找到不用这和方式的算法吗? ★不用乘法或加法增加8倍。现在用冋样的方法增加7倍。 第9题 判断整数序列是不是二元查找树的后序遍历结果 题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。 如果是返回true,否则返回fase 例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序谝历结果 610 / 57911 因此返回true 如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回 false。 第10题 翻转句」中单词的顺序。 题目:输入一个英文句了,翻转句子中单词的顺序,但单词内字符的顺序不变。句子中单词 以空格符隔开。 为简单起见,标点符号和普通字母一样处理 例如输入“ aa student”,则输出“ student.aamr'。 第11题 求二叉树中节点的最大距离. 如果我们把二叉树看成一个图, 父子节点之间的连线看成是双向的 我们姑且定义"距离"为两节点之间边的个数。 写一个程序 求一棵二叉树屮相距最远的两个节点之间的距离。 第12题 题目:求1+21. 要求不能使用乘除法、for、whle、i、else、 switc h、case等关键字以及条件判断话句(A?B:C)。 第13题: 题目:输入一个单链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的 尾指针。 链表结点定义如下 struct listnode int m nKey ListNode*m pNext; 第14题 题目:输入一个已经按升序排序过的数组和一个数字 在数组中查找两个数,使得它们的和正好是输入的那个数字。 要求时间复杂度是O(n)如果有多对数字的和等于输入的数字,输出任意一对即可 例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。 第15题: 题目:输入一颗二元查找树,将该树转换为它的镜像, 即在转换后的二元查找树中,左子树的结点都大于右子树的结点。 用递归和循环两和方法完成树的镜像转换。 例如输入: 610 7911 输出 l06 ∧A 11975 定义二元杳找树的结点为: struct BSTreeNode/a node in the binary search tree (BST) int m nAlle.i/ value of node BSTrccNodc-m pLcft; /i Ift child of nodo BSTreeNode m pRight; //right child of node 第16题: 题目(微软): 输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。 例如输入 610 579I1 输出861057911。 第17题: 趣目:在一个字符串中找到第一个只出现一次的字符。如输入 abac cde,则输出b 分析:这道题是2006年 googl的一道笔试题。 第18题: 题日:n个数字(0,1,,n-1)形成一个圆圈,从数字0开始, 每次从这个圆圈中删除第m个数字(第一个为当前数字本身,第二个为当前数字的下一个 数字)。 个数字删除后,从被刑除数字的下一个继续朋除第m个数字。 求出在这个圆圈中剩下的最后一个数字 July:我想,这个题目,不少人已经见认过了 第19题: 题目:定义 Fibonacci数列如下 0n=0 f(nI n=I f(n-1)+f(n-2)n=2 输入n,用最快的方法求该数列的第n项。 分析:在很多C语言教科书中讲到递归函数的时候,都会用 Fibonacci作为例子。 因此很多程序员对这道题的递归解法非常熟悉,但.呵呵,你知道的。。 第20题: 趣目:输入一个表示整数的字符串,把该宇符串转换成整薮并输出 例如输入字符串"345",则输出整数345。 第21题 2010年中兴面试题 编程求解 输入两个整数n和m,从数列1,2,3.n中随意取几个数, 使其和等于m,要求将其中所有的可能组合列出来 第22题 有4张红色的牌和4张蓝色的牌,主持人先拿任意两张,再分别在A、B、C三人额头上贴 任意两张牌 A、B、C人都可以看见其余两人额头上的牌,看完后让他们猜自己额头上是什么颜色的 牌 A说不知道,B说不知道,C说不知道,然后A说知道了 请教如何推理,A是怎么知道的 如果用程序,又怎么实玑呢? 第23题 用最筲单,最快速的方法计算出下面这个圆形是否和正方形相交。" 3D坐标糸原点(00,0.0,00) 员形 半径r=3.0 圆心o=(**,0.0,**) 正方形 4个角坐标; 1:(*,*,0.0,*,*) (**,0.0,**) 3:*,*,0.0,*,) 4:(*,*,0.0,*,*) 第24题 链表操作 (1)单链表就地逆置, (2)合并链表 第25题 写一个函数它的原形是 Int continumax(char* outputs;char+ intputstr)) 功能: 在字符串中找出连续最长的数字串,并把这个串的长度返回, 并把这个最长数字串付给其中一个函数参数 outputs所指内存。 例如:" abcd2345cd125ss123456789"的首地址传给 Intputstr后,函数将返回9 outputstr所指的倌为123456789 26左旋转字符串 题目 定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。 如把字符串 abc def左旋转2位得到字符串 defat。请实现字符串左旋转的函数。 要求时间对长度为n的字符串操作的复度为O(n),辅助内存为O(1) 27跳台阶问题 题日:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。 求总共有多少总跳沄,并分析算法的时间复杂度。 这道题最近经常出现,包括 Micro Strategy等比较重视算法的公司都 曾先后选用过个这道题作为面试题或者笔试题。 28整数的二进制表示中1的个数 题目:输入一个整数,求该整数的二进制表达中有多少个1 例如输入10,由于其二进制表示为1010,有两个1,因此输出2。 分析: 这是一道很基本的考杳位运算的面试题。 包括微软在內的很多公司都曾采用过这道题。 29栈的push、pop序列 题目:输入两个整数序列。其中一个序列表小栈的push顺序, 判断另一个序列有没有可能是对应的pop顺序 为了简单起见,我们假设push序列的任意两个整数都是不相等的 比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。