剑指offer（一）

面试题3：二维数组中查找

题目描述：

在一个二维数组中，每一行都按照从左往右递增地顺序排序，每一列都按照从上往下递增的顺序排序。请完成一个函数，输入这样的一个数组和一个整数，判断数组中是否存在该整数。

算法一：直接查找，即采取遍历数组的方法；

算法二：从数组右上角开始比较；

算法三：从数组左下角开始比较；

算法四：如果数组是N*N，可以采取沿对角线进行比较的方法；

----------------------------------------------------------------------------分割线---------------------------------------------------------------------------------------

面试题4：替换空格

题目描述：

请实现一个函数，把字符串中的每一个空格替换成“%20”。

这道题目的难点不是函数的实现，而是在面试过错中，需要弄清楚是在原始的字符串上作替换还是可以单独生成另外的字符串。

算法很简单，在此不多说。

---------------------------------------------------------------------------分割线---------------------------------------------------------------------------------------

面试题5：从尾到头打印链表

题目描述：

输入一个链表的头节点，从尾到头打印链表链表中的每一个节点。

算法一：递归；

算法二：利用栈结构；

---------------------------------------------------------------------------分割线----------------------------------------------------------------------------------------

面试题6：重建二叉树

题目：输入某二叉树的前序遍历和中序遍历，请重建该二叉树。假设输入的前序遍历和中序遍历都不包含重复数字。

代码：

 1 //二叉树节点
 2 struct  BinaryTreeNode
 3 {
 4     int m_nValue;
 5     BinaryTreeNode *m_pLeft;
 6     BinaryTreeNode *m_pRight;
 7 };
 8 BinaryTreeNode* Construct(int *preOrder,int *inOrder,int length);
 9 BinaryTreeNode* ConstructCore(int *startPreOrder,int *endPreOrder,int *startInOrder,int *endInOrder);
10 
11 BinaryTreeNode* Construct(int *preOrder,int *inOrder,int length)
12 {
13     if (NULL == preOrder || NULL == inOrder || length<=0)
14     {
15         return NULL;
16     }
17 
18     return ConstructCore(preOrder,preOrder+length-1,inOrder,inOrder+length-1);
19 }
20 BinaryTreeNode* ConstructCore(int *startPreOrder,int *endPreOrder,int *startInOrder,int *endInOrder)
21 {
22     //前序遍历第一个数字是根节点值
23     int rootValue = startPreOrder[0];
24     BinaryTreeNode *root = new BinaryTreeNode();
25     root->m_nValue = rootValue;
26     root->m_pLeft = root->m_pRight = NULL;
27 
28     if (startPreOrder == endPreOrder)
29     {
30         if (startInOrder == endInOrder && *startPreOrder == *startInOrder)
31         {
32             return root;
33         }
34         else
35         {
36             //throw std::exception("Invalid input.");
37             cout << "Invalid input.
";
38 
39         }
40     }
41 
42     //中序遍历中找到根节点值
43     int *rootInOrder = startInOrder;
44     while(rootInOrder <= endInOrder && *rootInOrder != rootValue)
45         ++rootInOrder;
46 
47     if (rootInOrder == endInOrder && *rootInOrder != rootValue)
48     {
49         //throw std::exception("Invalid input.");
50         cout << "Invalid input.
";
51     }
52     
53     int leftLength = rootInOrder - startInOrder;
54     int *leftPreOrderEnd = startPreOrder + leftLength;
55     if (leftLength > 0)
56     {
57         root->m_pLeft = ConstructCore(startPreOrder+1,leftPreOrderEnd,startInOrder,rootInOrder-1);
58     }
59     if (leftLength < endPreOrder - startPreOrder)
60     {
61         root->m_pRight = ConstructCore(leftPreOrderEnd+1,endPreOrder,rootInOrder+1,endInOrder);
62     }
63     return root;
64 
65 }

------------------------------------------------------------------------------------分割线---------------------------------------------------------------------------------------------

面试题7：用两个栈实现队列

题目：用两个栈实现队列的插入和删除操作。

思想：stack1和stack2，每次队列插入元素时，都将该元素压入（push）stack1，队列删除元素时，首先判断stack2是不是空，如果是空的，将stack1中元素依次弹出（pop），然后压入stack2，直到stack1为空，再从stack2中删除栈顶元素（前提是stack2中此时有元素存在，否则有错，这也是需要考虑的边界条件）。

引申题目：用两个队列实现栈。

思想：和面试题7的解题思想是一致的。在实现的时候，始终有一个队列是空的。

面试题10：二进制1的个数

题目：输入一个整数，输出其二进制表示中1的个数。

思想：通过右移，然后与1做与运算，判断1的个数。

代码：

 1 int NumberOf1(int n)
 2 {
 3     int count = 0;
 4     while(n)
 5     {
 6         if (n&1)
 7         {
 8             count++;
 9         }
10         n=>>1;
11     }
12     return count;
13 }

以上代码的缺点是：当输入一个负数时，最终n=0xffffffff，然后进入死循环。

改进：此方法仍然需要移动32位

 1 int NumberOf1(int n)
 2 {
 3     int count = 0;
 4     int flag = 1;
 5     while(n)
 6     {
 7         if (n&flag)
 8         {
 9             count++;
10         }
11         flag=<<1;
12     }
13     return count;
14 }

继续改进：n有几个1，就只移动几次

 1 int NumberOf1(int n)
 2 {
 3     int count = 0;
 4     while(n)
 5     {
 6         count++;
 7         n=n&(n-1);
 8     }
 9     return count;
10 }

在n=n&(n-1)操作中，每次都将n中最右边第一个不为0的数变为1，已经该位往右之后的所有位都变为0，而该位往左的位上的数都不会改变。