剑指offer面试题笔记11~20题（Java实现）
一、面试题1：复制运算符函数(P24)
题目：如下为类型CMString的声明，请为该类型添加赋值运算符函数。
class CMyString
{
public:
CMyString(Char* pData = NULL);
CMyString(const CMyString& str);
~CMyString(void);
private:
char* m_pData;
}
解题思路：
二、面试题2：实现Singleton模式（P31）
题目：设计一个类，我们只能生成该类的一个实例。
解题思路：
三、面试题3：二维数组中的查找（P38)
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解 题思路：根据二维数组的特点，从最后一列的第一个数字开始，若该数字大于那个整数，则该列中数字都大于该整数，因此可以排除该列。一直排除到某列第一个数 字小于该整数为止。从剩下的数组第一行的最后一个数字开始与整数进行比较，若该数字小于整数，表明该行中的数字都小于该整数，可以将该行排除，依此类推， 直到寻找到该整数为止。
public static boolean find(int[][] matrix, int rows, int columns, int number) {
boolean found = false;
if(matrix != null && rows >0 && columns >0) {
int row = 0;
int column = columns - 1;
while (row < rows && column >= 0) {
if (matrix[row][column] == number) {
found = true;
break;
}
else if (matrix[row][column] > number)
column -- ;
else
row ++;
}
}
return found;
}
四、面试题4：替换空格（P44)
题目：请实现一个函数，把字符串中的每个空格替换成“%20”。例如输入“We are happy."，则输出”We%20are%20happy."。
解题思路：若从前往后查找并替换，每替换一个空格，均需要将之后的字符向后移动，最后的“happy.”会移动两次。因此对含有O(n)个空格字符的字符串而言，总的时间效率是O(n2)。将从前往后替换变成从后往前替换，时间复杂度为O(n)。
解题思路：首 先遍历一次，统计出字符串中空格数n，则替换后字符串的长度为之前长度加2n。准备两个指针，P1和P2。1指向原字符串的末尾，2指向替换之后的字符串 的末尾。向前移动指针1，逐个将字符复制到2指向的位置，直到碰到第一个空格为止。将1前移一格，在2的前面插入字符串“%20”。继续循环该操作。
五、面试题5：从尾到头打印链表（P51)
题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
}
解题思路一：先进后出，可以用栈来实现这种顺序，每当经过一个结点，就将该节点放入栈中，遍历完整个链表后，从栈顶开始逐个输出结点的值。
public static Stack<ListNode> reverseList_2(ListNode node) {
Stack stack = new Stack();
while (node != null) {
stack.push(node);
node = node.next;
}
return stack;
}
解题思路二：动态规划逐步将大问题拆解成小问题，当开始返回结果时，正好实现倒置功能。
public static ListNode reverseList_1(ListNode node) {
if(node == null || node.next == null)
return node;
ListNode listNode = reverseList_1(node.next);
node.next.next = node;
node.next = null;
return listNode;
}
六、面试题6：重建二叉树(P55)
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
二叉树结点的定义如下：
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
}
解题思路：根据前序遍历找到根节点，在中序遍历中，在该根节点前的节点为该根节点的左子树，在该根节点后的节点为该根节点的右子树。采用递归的方法完成。
public static BinaryTreeNode construct(int[] preOrder,
int beginP,
int endP,
int[] inOrder,
int beginI,
int endI) {
if (beginP > endP || beginI > endI)
return null;
int rootData = preOrder[beginP];
BinaryTreeNode head = new BinaryTreeNode();
head.value = rootData;
int divider = findIndexInArray(inOrder, rootData, beginI, endI);
int offSet = divider - beginI - 1;
BinaryTreeNode left = construct (preOrder, beginP + 1, beginP + 1 + offSet, inOrder, beginI, beginI + offSet);
BinaryTreeNode right = construct (preOrder, beginP + offSet + 2, endP, inOrder, divider + 1, endI);
head.left = left;
head.right = right;
return head;
}
public static int findIndexInArray(int[] a, int x, int begin, int end) {
for (int i = begin; i <= end; i ++)
if (a[i] == x)
return i;
return -1;
}
public static void preOrder(BinaryTreeNode n){
if(n!=null){
System.out.print(n.value+",");
preOrder(n.left);
preOrder(n.right);
}
}
public static void inOrder(BinaryTreeNode n){
if(n!=null){
inOrder(n.left);
System.out.print(n.value+",");
inOrder(n.right);
}
}
public static void afterOrder(BinaryTreeNode n){
if(n!=null){
afterOrder(n.left);
afterOrder(n.right);
System.out.print(n.value+",");
}
}
七、面试题7：用两个栈实现队列(P59)
题目：用两个栈实现一个队列。队列的声明如下：请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。
template<typename T> class CQueue
{
public:
CQueue(void);
~CQueue(void);
void appendTail(const T& node);
T deleteHead();
private:
stack<T> stack1;
stack<T> stack2;
}
八、面试题8：旋转数组的最小数字（P66)
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
解题思路：
九、面试题9：斐波那契数列（P73)
题目一：写一个函数，输入n,求斐波那契数列的第n项。斐波那契数列的定义如下：
解题思路：
题目二：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解题思路：
十、面试题10：二进制中1的个数（P78)
题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如把9表示成二进制是1001，有2位是1。因此如果输入9，该函数输出2。
解题思路：
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
