1. 数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2
• 关键：数字都在0到n-1的范围内

2. 二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
• 思路：注意数组是有顺序的。从右上角开始比较，大于target就只可能在左边，小于就只能在下面。若从中间开始找就会很麻烦。

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
• O(n)复杂度，先遍历一遍根据空格数计算出替换后的字符串长度，再从后往前复制字符。

4. 从尾到头打印链表

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

6. 二叉树的下一个结点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
• 解法：分两种情况，有右节点和没有右节点。有右节点：下一个节点就是右子树的最左边的节点。没有右节点：下一个节点就是（是父亲节点左子树的节点）

7. 用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
• 思路：一个栈是先进后出，从一个栈出栈再入到第二个栈，第二个栈就是先进先出了，就完成了模拟队列。

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
• 解法：其实就是斐波那契数列，第n级台阶可以由第n-1级跳一步达到，也可以有第n-2级跳两步达到。

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n 的大矩形，总共有多少种方法？
• 解法：也是斐波那契数列

12. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
• 回溯法 -- 隐式图的深度优先搜索

14. 机器人的运动范围

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

15. 剪绳子（待定）

16. 二进制中1的个数

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
• 解法：从低位依次右移数一，不要从高位往低位数，因为负数的符号位右移一直是1。

17. 数值的整数次方

18. 调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
• 冒泡排序保持稳定性，插入排序也可以。注意，有没有黑体字的解法是不一样的。

19. 链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。
• 双指针，让一个指针先走k-1步，再两个指针一起走。简单题要考虑鲁棒性。

20. 链表中环的入口结点

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

输入一个链表，反转链表后，输出新链表的表头。

22. 合并两个排序的链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

• 题目描述: 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

操作给定的二叉树，将其变换为源二叉树的镜像。
• 扩展：用循环来做（模拟栈）。

由于递归的本质是编译器生成了一个函数调用的栈，因此用循环来完成同样任务时，最简单的办法就是用一个辅助栈来模拟递归。首先把树的头结点放入栈中。在循环中，只要栈不为空，弹出栈的栈顶结点，交换它的左右子树。如果它有左子树，把它的左子树压入栈中；如果它有右子树，把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

26. 顺时针打印矩阵

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

28. 栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

29. 从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

30. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
• 解法：后序遍历根节点在最后，根据根节点将数组分为左右两部分（若无法分成两部分，则不是搜索树），再递归检查左右子树。

31. 二叉树中和为某一值的路径

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

32. 复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
• 方法一：先按next复制节点，用哈希表将复制前后的节点一一对应起来，这样就可以用O(1)的时间复杂度找到random节点。
• 方法二：第一步，将复制节点连在旧节点后面；第二步，复制random节点；第三步，剪开。

33. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
• 众所周知，BST的中序遍历是顺序的。我想到的方法是：中序遍历，将树的节点依次存入一个数组，再把节点连起来。书上给的方法不需要额外的空间。

34. 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

35. 连续子数组的最大和

36. 整数中1出现的次数

• 题目描述: 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

38. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对取模的结果输出。 即输出P%
• 归并排序，时间复杂度O(logN).

39.两个链表的第一个公共结点

输入两个链表，找出它们的第一个公共结点。
• 解法：长的链表先走几步，然后找第一个公共节点

40. 数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。

• 这个也算后序遍历。。。树的深度等于左右子树深度加一。

输入一棵二叉树，判断该二叉树是否是平衡二叉树。
• 解法：用后序遍历的方式，先求出左右子树的高度，判断左右子树均为平衡二叉树后，再判断左右子树的高度差是否小于2

43. 数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
• 解法：因为有两个不同的数字，所有数字异或完后必不为0；再根据异或完的数某一位的1，将数组中的数分成两组，再分别异或。

44. 和为S的连续正数序列

输入一个正数s,打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15；所以打印出三个连续序列1~5 , 4~6, 7~8；

45. 翻转单词顺序列

• 解法：先翻转整个句子，再翻转每个单词

• 例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。

47. 滑动窗口的最大值

• 解法：deque双向队列

48. 二叉搜索树的第k个结点

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
• 思路：BST的中序遍历是顺序的。

49. 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
• 思路：不用加减乘除意思就是用位运算。用异或代替无进位的求和，用与运算代替进位。

• 思路：先累乘左边，再累乘右边。

51. 二叉树两结点的最低公共祖先结点

给定二叉树中的两个结点，输出这两个结点的最低公共祖先结点（LCA）。注意，该二叉树不一定是二叉搜索树。

一、单项选择题（每小题3分，共30分）

1、在有n 个叶子结点的哈夫曼树中，其结点总数为（）。

2、下列序列中，（）是执行第一趟快速排序得到的序列（排序的关键字类型是字符串）。

3、若线性表最常用的操作是存取第i 个元素及其前驱的值，则采用（）存储方式节省时间。

4、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是（）。

5、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。

6、下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（）。

7、快速排序算法在最好情况下的时间复杂度为（）。

8、已知数据表A中每个元素距其最终位置不远，则采用（）排序算法最省时间。

9、带权有向图G用邻接矩阵A存储，则顶点i的入度为A中（）。

A、第i行非∞的元素之和

B、第i列非∞的元素之和

C、第i行非∞且非0的元素之和

D、第i列非∞且非0的元素之和

10、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。

二、判断题（认为对的在题后的括号内打“√”，错的打“ⅹ”，每小题１分，

1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可

访问该图的每个顶点。( )

2. 在索引顺序表上实现分快查找，在等概率查找情况下，其平均查找长度不仅

与表的个数有关，而且与每一块中的元素个数有关。( )

3、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。( )

4、图G的最小生成树的代价一定小于其他生成树的代价。( )

5、已知一棵树的先序序列和后序序列，一定能构造出该树。( )

6、对一个堆按层次遍历，不一定能得到一个有序序列。( )