第一题：二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
代码：
这个题其实很简单
左上角是最小的，右下角是最大的，如果我们从最大或者最小的地方开始查找不是很方便，想一想是不是，因为有时候选择是不确定的，这样就会导致后续走向有回头现象
这个时候我们很容易想到用二分来做，但是依然不是很好二分，因为一行或者一列中可能二分不到想要的结果
而恰好在另外的一条对角线有二分的思想，大了可以选择小的，小了可以选择大的
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int row=array.size();
int col=array[0].size();
if(row==0||col==0) return false;
int i=0,j=col-1;
while(i<row&&j>=0){
if(array[i][j]==target) return true;
if(array[i][j]>target) j--;
else i++;
}
return false;
}
};
第二题：替换空格
请实现一个函数，将一个字符串中的空格替换成“ ”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We Are Happy
代码
这里处理的是：在不申请新的内存的条件下完成转换
这样处理的话肯定就是倒过来处理，然后注意一下字符串结尾标志的处理
class Solution {
public:
void replaceSpace(char *str,int length) {
if(!str) return ;
int cnt=0,oriLength=0;
char *p=str;
while(*p){
if(*p==' ') cnt++;
oriLength++;
p++;
}
int newLength=oriLength+2*cnt+1;
if(newLength>length) return;
int p1=oriLength+1;
int p2=newLength;
while(p1<p2){
if(str[p1]!=' ') str[p2--]=str[p1--];
else str[p2--]='0',str[p2--]='2',str[p2--]='%',p1--;
}
return;
}
};
第三题：从尾到头打印链表
就是利用盏来暂时保存结果，然后一个个从栈里面取出来即可
代码
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
stack<ListNode * > nodes;
struct ListNode * p=head;
while(p!=NULL){
nodes.push(p);
p=p->next;
}
vector<int>res;
while(!nodes.empty()){
p=nodes.top();
res.push_back(p->val);
nodes.pop();
}
return res;
}
};
第四题：重建二叉树
给出先序和中序，求解二叉树
给出先序就可以知道先序的第一个节点一定是跟节点，而这个节点在中序中又可以分辨出左子树和右子树，以此类推就能得到一颗二叉树
因此给出先序和后序的时候不能求解出相应的二叉树
代码：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.empty()) return NULL;
TreeNode * root = new TreeNode(pre[0]);
if(pre.size()==1){
root->val=pre[0];
root->left=NULL;
root->right=NULL;
return root;
}
vector<int>::iterator it = vin.begin();
while(it!=vin.end()){
if((*it)==pre[0]) break;
it++;
}
int len=it-vin.begin();///左子树长度
vector<int> pre1(pre.begin()+1,pre.begin()+1+len);
vector<int> vin1(vin.begin(),vin.begin()+len);
vector<int> pre2(pre.begin()+1+len,pre.end());
vector<int> vin2(vin.begin()+1+len,vin.end());
root->left=reConstructBinaryTree(pre1,vin1);
root->right=reConstructBinaryTree(pre2,vin2);
return root;
}
};
第五题：两个栈来实现队列
始终让一个栈来入队列，一个栈来出队列
当出队列的栈为空的时候就从入队列的栈取数据到出队列
代码：
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if(!stack2.empty()){
int val=stack2.top();
stack2.pop();
return val;
}
while(!stack1.empty()){
int val=stack1.top();
stack1.pop();
stack2.push(val);
}
int val=stack2.top();
stack2.pop();
return val;
}
private:
stack<int> stack1;
stack<int> stack2;
};
第六题：旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{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.empty()) return 0;
if(rotateArray.size()==1) return rotateArray[0];
int len=rotateArray.size();
int left=0,right=len-1,mid;
while(rotateArray[left]>=rotateArray[right]){
if(right-left==1) return rotateArray[right];
mid=left+((right-left)>>1);
if(rotateArray[left]==rotateArray[mid]&&rotateArray[mid]==rotateArray[right]){
int t=rotateArray[left];
for(int i=left+1;i<=right;i++)
if(rotateArray[i]<t) t=rotateArray[i];
return t;
}
if(rotateArray[mid]>=rotateArray[left]) left=mid;
if(rotateArray[mid]<=rotateArray[right])right=mid;
}
return rotateArray[left];
}
};
