剑指offer第二章
1.二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
class Solution {
public:
bool Find(int target, vector<vector<int> > array)
{
/*二维数组的行数和列数*/
int rows = array.size();
int columns = array[].size();
int row;
int column;
for (row = rows - , column = ; row >= && column<columns;)
{
if (target == array[row][column])
return true;
if (target<array[row][column])
{
row--;
continue;
}
if (target>array[row][column])
{
column++;
continue;
}
}
return false;
}
};2.替换空格
请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
class Solution {
public:
void replaceSpace(char *str,int length)
{
if(str==NULL||length<)
{
return;
}
int originalLength=;
int numberOfBlank=;
int i=;
while(str[i]!='\0')//计算原始字符串长度和空格数目
{
++originalLength;
if(str[i]==' ')
{
++numberOfBlank;
}
++i;
}
int newLength=originalLength+numberOfBlank*;//替换之后新的长度
if(newLength>length)
//溢出、越界
return;
int indexOfOriginal=originalLength;
int indexOfNew=newLength;
while(indexOfOriginal>=&&indexOfNew>indexOfOriginal)
{
if(str[indexOfOriginal]==' ')//找到空格，依次插入‘0’‘2’‘%’
{
str[indexOfNew--]='';
str[indexOfNew--]='';
str[indexOfNew--]='%';
}
else
{
str[indexOfNew--]=str[indexOfOriginal];
}
--indexOfOriginal;
}
}
};3.从尾到头打印链表
输入一个链表，从尾到头打印链表每个节点的值。
//struct ListNode {
//int val;
//struct ListNode *next;
//ListNode(int x) :
//val(x), next(NULL) {
//}
//};
class Solution{
public:
vector<int> printListFromTailToHead(struct ListNode* head){
vector<int> result;
struct ListNode* pNode=head;
while(pNode!=NULL){
result.push_back(pNode->val);
pNode=pNode->next;
}
reverse(result.begin(),result.end());//applying reverse()
return result;
}
};4.重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in)
{
//判定递归终止条件；
if(pre.size() == || in.size() == )
{
return NULL;
}
//定义Node节点并其求根节点；
int root = pre[];
TreeNode* node = new TreeNode(root);
vector<int>::iterator it;
//1.求左右子树的遍历序列；
vector<int> preLeft, preRight, inLeft, inRight;
//（1）.求根节点在中序遍历序列中的位置；
vector<int>::iterator i;
for(it = in.begin(); it != in.end(); it++)
{
if(root == *it)
{
i = it;
}
}
//（2）.求左右子树的中序遍历子序列；
int k = ;
for(it = in.begin(); it != in.end(); it++)
{
if(k == )
{
inLeft.push_back(*it);
}
else if(k == )
{
inRight.push_back(*it);
}
else {}
if(it == i)
{
k = ;
}
}
//（3）.求左右子树的前序遍历子序列；
k = ;
vector<int>::iterator ite;
for(it = pre.begin()+; it != pre.end(); it++)
{
for(ite = inLeft.begin(); ite != inLeft.end(); ite++)
{
if(*it == *ite)
{
preLeft.push_back(*it);
k = ;
}
}
if(k == )
{
preRight.push_back(*it);
}
k = ;
}
//根据遍历序列求出跟的左右节点；
node->left = reConstructBinaryTree(preLeft,inLeft);
node->right = reConstructBinaryTree(preRight,inRight);
//返回节点地址；
return node;
}
};
5.用两个栈实现队列
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
<分析>：
入队：将元素进栈A
出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；
如果不为空，栈B直接出栈。
class Solution
{
public:
void push(int node)
{
stack1.push(node);
}
int pop()
{
int a;
if(stack2.empty())
{
while(!stack1.empty())
{
a=stack1.top();
stack2.push(a);
stack1.pop();
}
}
a=stack2.top();
stack2.pop();
return a;
}
private:
stack<int> stack1;
stack<int> stack2;
};
6.旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray)
{
//数组为空时
if(rotateArray.size() == )
return -;
//前部分数据旋转
for(int i = ; i < rotateArray.size() - ; i++)
{
if (rotateArray[i] > rotateArray[i + ])
return rotateArray[i + ];
}
//全部数据旋转，相当于没有旋转，最小数即为第一个数
return rotateArray[];
}
};7.菲波那切数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39
class Solution {
public:
int Fibonacci(int n)
{
int result[]={,};
if(n<)
return result[n];
long long f1=;
long long f2=;
long long fn=;
for(int i=;i<=n;i++)
{
fn=f1+f2;
f2=f1;
f1=fn;
}
return fn;
}
};8.二进制中”1“的个数
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解法1：首先把n和1做与运算，判断n的最低位是不是为1
接着把1左移一位得到2，在与n做与运算，就能判断n的次低位是不是1
......这样反复左移，每次都能判断n的其中一位是不是1。
循环的次数等于整数二进制的位数
解法2：首先把一个整数减去1，再和原整数做与运算，会把最右边一个1变成0.
那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作
循环的次数等于整数中1的个数
class Solution {
public:
int NumberOf1(int n)
{
int count=;//统计的值初始化
unsigned int flag=;//设置一个标志，作为循环结束的终止条件
while(flag)
{
//首先把n和1做与运算，判断n的最低位是不是为1
//接着把1左移一位得到2，在与n做与运算，就能判断n的次低位是不是1
//......这样反复左移，每次都能判断n的其中一位是不是1。
// 循环的次数等于整数二进制的位数
if(n&flag)
count++;
flag=flag<<;
}
return count;
}
};