1 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。（来自牛客网，剑指offer）
// IO_Solution.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h"
#include <vector>
using namespace std; /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// //在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
//请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 //首先构造这样一个二维向量
void BuildDstArray(vector<vector<int>>&Array)
{
int nRow = Array[].size();
int nColumn = Array.size();
for (int i = ; i < nColumn; i++)
{
for (int j = ; j < nRow; j++)
{
Array[i][j] = i*nRow + j;
}
} for (int i = ; i < nColumn; i++)
{
for (int j = ; j < nRow; j++)
{
printf("%4d", Array[i][j]);
}
printf("\n");
} } //最差情况复杂度为：n+m
bool TwoDemoArrayFind(vector<vector <int>>Array,int nDst)
{
bool bFound = false;
if (Array.empty())
{
return bFound;
}
else
{
int nCurRow = ;
int nCurCol = ;
int nRows = Array[].size();
int nCols = Array.size(); while (nCurRow < nRows&&nCurCol >= )
{
if (Array[nCurCol][nCurRow] == nDst)
{
printf("位置：{%d,%d}",nCurCol,nCurRow);
bFound = true;
break;
}
else
{
if (Array[nCurCol][nCurRow] > nDst)
{
nCurRow--;
}
else
{
nCurCol++;
}
} }
return bFound; } }
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int main()
{
//构造并初始化一个二维向量：4行5列
vector<vector<int>> Array(, vector<int>(, )); //另外一种构造二维向量的方法
vector<vector<int>> a;
a.resize();
for (int i = ; i < ; i++)
{
a[i].resize();
} BuildDstArray(a);
TwoDemoArrayFind(a,); getchar();
return ;
}
2
请实现一个函数，将一个字符串中的空格替换成“ % 20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
//注意如果输出的是%20d需要对%进行转义
//用Stl中的vector时间复杂度为：O(str.length());空间复杂度O(str.length+3*SpaceNum)
void ReplaceSpace( string strSrc,char *sOut)
{
vector<char> cOut;
const char *pStr = strSrc.data();
while (*pStr != '\0')
{
if (*pStr == ' ')
{
cOut.push_back('%');
cOut.push_back('');
cOut.push_back('');
}
else
cOut.push_back(*pStr);
pStr++;
}
cOut.push_back('\0'); for (int i = ; i < cOut.size(); i++)
{
sOut[i] = cOut[i];
} } //Test
string str= "ni hao ma";
char pStr[] = {};
ReplaceSpace(str,pStr);
printf("%s",pStr);
getchar();
return ;