1題目：在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序垮斯，每一列都按照從上到下遞增的順序排序郎仆。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)兜蠕，判斷數(shù)組中是否含有該整數(shù)扰肌。
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int row = array.size();
int colume = array[0].size();
int x = row - 1;
int y = 0;
while (x >= 0 && y <= colume-1) {
if (target < array[x][y]) {
--x;
}else if (target > array[x][y]) {
++y;
}else {
return true;
}
}
return false;
}
};
2題目：請實現(xiàn)一個函數(shù)，將一個字符串中的空格替換成“%20”熊杨。例如曙旭，當(dāng)字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy盗舰。
//思路
//1：從前往后插入，這樣移動·的次數(shù)多不建議
//2：從后往前插入
class Solution {
public:
void replaceSpace(char *str,int length) {
//遍歷一邊字符串找出空格的數(shù)量
if(str==NULL||length<0)
return ;
int i=0;
int oldnumber=0;//記錄以前的長度
int replacenumber=0;//記錄空格的數(shù)量
while(str[i]!='\0')
{
oldnumber++;
if(str[i]==' ')
{
replacenumber++;
}
i++;
}
int newlength=oldnumber+replacenumber*2;//插入后的長度
if(newlength>length)//如果計算后的長度大于總長度就無法插入
return ;
int pOldlength=oldnumber; //注意不要減一因為隱藏個‘\0’也要算里
int pNewlength=newlength;
while(pOldlength>=0&&pNewlength>pOldlength)//放字符
{
if(str[pOldlength]==' ') //碰到空格就替換
{
str[pNewlength--]='0';
str[pNewlength--]='2';
str[pNewlength--]='%';
}
else //不是空格就把pOldlength指向的字符裝入pNewlength指向的位置
{
str[pNewlength--]=str[pOldlength];
}
pOldlength--; //不管是if還是elsr都要把pOldlength前移
}
}
};
3題目：輸入一個鏈表桂躏，從尾到頭打印鏈表每個節(jié)點的值钻趋。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) :
* val(x), next(NULL) {
* }
* };
*/
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> result;
stack<struct ListNode*> stack;
while(head != NULL){
stack.push(head);
head = head->next;
}
while(!stack.empty()){
result.push_back(stack.top()->val);
stack.pop();
}
return result;
}
};
4.輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹剂习。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字蛮位。例如輸入前序遍歷序列{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:
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
int inlen=in.size();
if(inlen==0)
return NULL;
vector<int> left_pre,right_pre,left_in,right_in;
//創(chuàng)建根節(jié)點失仁，根節(jié)點肯定是前序遍歷的第一個數(shù)
TreeNode* head=new TreeNode(pre[0]);
//找到中序遍歷根節(jié)點所在位置,存放于變量gen中
int gen=0;
for(int i=0;i<inlen;i++)
{
if (in[i]==pre[0])
{
gen=i;
break;
}
}
//對于中序遍歷，根節(jié)點左邊的節(jié)點位于二叉樹的左邊们何，根節(jié)點右邊的節(jié)點位于二叉樹的右邊
//利用上述這點萄焦，對二叉樹節(jié)點進(jìn)行歸并
for(int i=0;i<gen;i++)
{
left_in.push_back(in[i]);
left_pre.push_back(pre[i+1]);//前序第一個為根節(jié)點
}
for(int i=gen+1;i<inlen;i++)
{
right_in.push_back(in[i]);
right_pre.push_back(pre[i]);
}
//和shell排序的思想類似，取出前序和中序遍歷根節(jié)點左邊和右邊的子樹
//遞歸冤竹，再對其進(jìn)行上述所有步驟楷扬，即再區(qū)分子樹的左、右子子數(shù)贴见，直到葉節(jié)點
head->left=reConstructBinaryTree(left_pre,left_in);
head->right=reConstructBinaryTree(right_pre,right_in);
return head;
}
};
5.用兩個棧來實現(xiàn)一個隊列烘苹，完成隊列的Push和Pop操作。 隊列中的元素為int類型片部。
/*用兩個棧實現(xiàn)一個隊列的功能?要求給出算法和思路!
**<分析>：
**入隊：將元素進(jìn)棧A
**出隊：判斷棧B是否為空镣衡，如果為空，則將棧A中所有元素pop档悠，并push進(jìn)棧B廊鸥，棧B出棧；
**如果不為空辖所，棧B直接出棧惰说。
*/
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
int a;
// 如果棧2空
if (stack2.empty()) {
// 依次把棧1中的所有元素放入到棧2中去
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;
};
