剑指offer第二章

1.二维数组中的查找

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

 1 class Solution {
 2 public:
 3     bool Find(int target, vector<vector<int> > array) 
 4     {
 5         /*二维数组的行数和列数*/
 6          int rows = array.size();
 7          int columns = array[0].size();
 8         
 9             int row;
10             int column;
11         for (row = rows - 1, column = 0; row >= 0 && column<columns;)
12         {
13              if (target == array[row][column])
14                  return true;
15             if (target<array[row][column])
16              {
17                  row--;
18                  continue;
19              }
20              if (target>array[row][column])
21              {
22                  column++;
23                  continue;
24              }
25          }
26          return false;
27     }
28 };

2.替换空格

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

 1 class Solution {
 2 public:
 3     void replaceSpace(char *str,int length) 
 4     {
 5         if(str==NULL||length<0)
 6         {
 7             return;
 8         }
 9         int originalLength=0;
10         int numberOfBlank=0;
11         int i=0;
12         while(str[i]!='')//计算原始字符串长度和空格数目
13         {
14             ++originalLength;
15             if(str[i]==' ')
16             {
17                 ++numberOfBlank;
18             }
19             ++i;
20         }
21         int newLength=originalLength+numberOfBlank*2;//替换之后新的长度
22         if(newLength>length)
23             //溢出、越界
24             return;
25         int indexOfOriginal=originalLength;
26         int indexOfNew=newLength;
27         while(indexOfOriginal>=0&&indexOfNew>indexOfOriginal)
28         {
29             if(str[indexOfOriginal]==' ')//找到空格，依次插入‘0’‘2’‘%’
30             {
31                 str[indexOfNew--]='0';
32                 str[indexOfNew--]='2';
33                 str[indexOfNew--]='%';
34             }
35             else
36             {
37                 str[indexOfNew--]=str[indexOfOriginal];
38             }
39             --indexOfOriginal;
40         }
41     }
42 };

3.从尾到头打印链表

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

 1 //struct ListNode {
 2 //int val;
 3 //struct ListNode *next;
 4 //ListNode(int x) :
 5 //val(x), next(NULL) {
 6 //}
 7 //};
 8 
 9 class Solution{
10 public:
11     vector<int> printListFromTailToHead(struct ListNode* head){
12         vector<int> result;
13         struct ListNode* pNode=head;
14         while(pNode!=NULL){
15             result.push_back(pNode->val);
16             pNode=pNode->next;
17         }
18         reverse(result.begin(),result.end());//applying reverse()
19         return result;
20     }
21 };

4.重建二叉树

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

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) 
13     {
14         //判定递归终止条件；
15         if(pre.size() == 0 || in.size() == 0) 
16         {
17             return NULL;
18         }
19         //定义Node节点并其求根节点；
20         int root = pre[0];
21         TreeNode* node = new TreeNode(root);
22         vector<int>::iterator it;
23         //1.求左右子树的遍历序列；
24         vector<int> preLeft, preRight, inLeft, inRight;
25         //（1）.求根节点在中序遍历序列中的位置；
26         vector<int>::iterator i;
27         for(it = in.begin(); it != in.end(); it++)
28         {
29             if(root == *it)
30             {
31                 i = it;
32             }
33         }
34         //（2）.求左右子树的中序遍历子序列；
35         int k = 0;
36         for(it = in.begin(); it != in.end(); it++) 
37         {
38             if(k == 0)
39             {
40                 inLeft.push_back(*it);
41             }
42             else if(k == 1) 
43             {
44                 inRight.push_back(*it);
45             }
46             else {}
47             if(it == i) 
48             {
49                 k = 1;
50             }  
51         }
52         //（3）.求左右子树的前序遍历子序列；
53         k = 0;
54         vector<int>::iterator ite;
55         for(it = pre.begin()+1; it != pre.end(); it++) 
56         {
57             for(ite = inLeft.begin(); ite != inLeft.end(); ite++) 
58             {
59                 if(*it == *ite) 
60                 {
61                     preLeft.push_back(*it);
62                     k = 1;
63                 }
64             }
65             if(k == 0)
66             {
67                 preRight.push_back(*it);
68             }
69             k = 0;
70         }
71         //根据遍历序列求出跟的左右节点；
72         node->left = reConstructBinaryTree(preLeft,inLeft);
73         node->right = reConstructBinaryTree(preRight,inRight);
74         //返回节点地址；
75         return node; 
76     }
77 };

5.用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

<分析>：

入队：将元素进栈A

出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；

如果不为空，栈B直接出栈。

 1 class Solution
 2 {
 3 public:
 4     void push(int node) 
 5     {
 6         stack1.push(node);       
 7     }
 8     int pop() 
 9     {
10         int a;
11         if(stack2.empty())
12         {
13             while(!stack1.empty())
14             {
15                 a=stack1.top();
16                 stack2.push(a);
17                 stack1.pop();
18             }
19         }
20         a=stack2.top();
21         stack2.pop();
22         return a;
23     }
24 private:
25     stack<int> stack1;
26     stack<int> stack2;
27 };

6.旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

 1 class Solution {
 2 public:
 3      int minNumberInRotateArray(vector<int> rotateArray)
 4      {
 5         //数组为空时
 6         if(rotateArray.size() == 0)
 7             return -1;
 8         //前部分数据旋转
 9         for(int i = 0; i < rotateArray.size() - 1; i++)
10         {
11             if (rotateArray[i] > rotateArray[i + 1])
12                 return rotateArray[i + 1];
13         }
14         //全部数据旋转，相当于没有旋转，最小数即为第一个数
15         return rotateArray[0];
16      }
17 };

7.菲波那切数列

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

 1 class Solution {
 2 public:
 3     int Fibonacci(int n)
 4     {
 5         int result[2]={0,1};
 6         if(n<2)
 7             return result[n];
 8         long long f1=1;
 9         long long f2=0;
10         long long fn=0;
11         for(int i=2;i<=n;i++)
12         {
13             fn=f1+f2;
14             f2=f1;
15             f1=fn;
16         }
17         return fn;
18     }
19 };

8.二进制中”1“的个数

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

解法1：首先把n和1做与运算，判断n的最低位是不是为1

接着把1左移一位得到2，在与n做与运算，就能判断n的次低位是不是1

......这样反复左移，每次都能判断n的其中一位是不是1。

循环的次数等于整数二进制的位数

解法2：首先把一个整数减去1，再和原整数做与运算，会把最右边一个1变成0.

那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作

循环的次数等于整数中1的个数

 1 class Solution {
 2 public:
 3      int  NumberOf1(int n)
 4      {
 5          int count=0;//统计的值初始化
 6          unsigned int flag=1;//设置一个标志，作为循环结束的终止条件
 7          while(flag)
 8          {
 9              //首先把n和1做与运算，判断n的最低位是不是为1
10             //接着把1左移一位得到2，在与n做与运算，就能判断n的次低位是不是1
11             //......这样反复左移，每次都能判断n的其中一位是不是1。
12            // 循环的次数等于整数二进制的位数
13              if(n&flag)
14                  count++;
15              flag=flag<<1;
16          }
17          return count;
18      }
19 };