[程序员面试题精选100题]10.排序数组中和为给定值的两个数字

[题目] 输入一棵二叉查找树,将该二叉查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向. 比如将二叉查找树                                            10                                          /    \                                        6       14                                      / 

[题目] 输入一个整数数组,判断该数组是不是某二叉查找树的后序遍历的结果.如果是返回true,否则返回false. 例如输入5.7.6.9.11.10.8,由于这一整数序列是如下树的后序遍历结果:           8         /    \       6    10      /   \   /   \    5    7 9 11 因此返回true. 如果输入7.4.6.5,没有哪棵树的后序遍历的结果是这个序列,因此返回false. [分析] 这是一道trilogy的笔试题,主要考

[题目] 输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印. 例如输入         8      /      \     6     10    /   \     /  \   5  7   9  11 输出8   6   10   5   7   9   11 [分析] 这曾是微软的一道面试题.这道题实质上是要求遍历一棵二元树,只不过不是我们熟悉的前序.中序或者后序遍历. 我们从树的根结点开始分析.自然先应该打印根结点8,同时为了下次能够打印8的两个子结点,

题目 输入一个单向链表,输出该链表中倒数第k个结点.链表的倒数第0个结点为链表的尾指针. 思路一 因为是单向链表,只有从前往后的指针而没有从后往前的指针.因此我们不能倒序遍历链表,只能正序遍历.假设整个链表有n个结点,那么倒数第k个结点是从头结点开始的第n-k-1个结点(从0开始计数).我们只需要得到链表中结点的个数n,那我们只要从头结点开始往后走n-k-1步就可以了. 因此这种方法需要遍历链表两次.第一次得到链表中结点个数n,第二次得到从头结点开始的第n-k-1个结点即倒数第k个结点.时间复杂

题目 输入两棵二叉树A和B,判断树B是不是A的子结构. 例如,下图中的两棵树A和B,由于A中有一部分子树的结构和B是一样的,因此B就是A的子结构. 思路 这是2010年微软校园招聘时的一道题目.二叉树一直是微软面试题中经常出现的数据结构.对微软有兴趣的读者一定要重点关注二叉树. 回到这个题目的本身.要查找树A中是否存在和树B结构一样的子树,我们可以分为两步: (1)树A中找到和B的根结点的值一样的结点N (2)再判断树A中以N为根结点的子树是不是包括和树B一样的结构. 第一步在树A中查找与根结点

题目 在8×8的国际象棋上摆放八个皇后,使其不能相互攻击,即任意两个皇后不得处在同一行.同一列或者同一对角斜线上.下图中的每个黑色格子表示一个皇后,这就是一种符合条件的摆放方法.请求出总共有多少种摆法. 思路 这就是有名的八皇后问题.解决这个问题通常需要用递归,而递归对编程能力的要求比较高.因此有不少面试官青睐这个题目,用来考察应聘者的分析复杂问题的能力以及编程的能力. 由于八个皇后的任意两个不能处在同一行,那么这肯定是每一个皇后占据一行.于是我们可以定义一个数组colIndex[8],colI

[题目] 在一个字符串中找到第一个只出现一次的字符.如输入abaccdeff,则输出b. [分析] [代码] /********************************* * 日期:2013-12-23 * 作者:SJF0115 * 题目: 13.第一个只出现一次的字符 * 来源:微软 * 分类:程序员面试题精选100题 **********************************/ #include <iostream> #include <cstring> us

题目 输入一个表示整数的字符串,把该字符串转换成整数并输出.例如输入字符串"345",则输出整数345. 分析 这道题尽管不是很难,学过 C/C++语言一般都能实现基本功能,但不同程序员就这道题写出的代码有很大区别,可以说这道题能够很好地反应出程序员的思维和编程习惯,因此已经被包括微软在内的多家公司用作面试题.建议读者在往下看之前自己先编写代码,再比较自己写的代码和下面的参考代码有哪些不同. 我们需要考虑一下几个方面的问题: (1)正负问题: 由于整数可能不仅仅之含有数字,还有可能以'

题目 输入一个链表的头结点,反转该链表,并返回反转后链表的头结点. 分析 假设经过若干操作,我们已经把结点 pre之前的指针调整完毕,这些结点的next指针都指向前面一个结点.现在我们遍历到结点cur.我们需要把调整结点的next指针让它指向前一个结点pre.注意一旦调整了指针的指向,链表就断开了,如下图所示: 因为已经没有指针指向结点nextNode,我们没有办法再遍历到结点nextNode 了.因此为了避免链表断开,我们需要在调整cur的next指针之前要把nextNode保存下来. 代码