首页 > 代码库 > 剑指offer面试题笔记11~20题（Java实现）
剑指offer面试题笔记11~20题（Java实现）
一、面试题1：复制运算符函数(P24)
题目：如下为类型CMString的声明，请为该类型添加赋值运算符函数。
class CMyString { public: CMyString(Char* pData =http://www.mamicode.com/ 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 =http://www.mamicode.com/ preOrder[beginP]; BinaryTreeNode head = new BinaryTreeNode(); head.value =http://www.mamicode.com/ 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。
解题思路：
剑指offer面试题笔记11~20题（Java实现）