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

1 // IO_Solution.cpp : 定义控制台应用程序的入口点。  2 //  3   4 #include "stdafx.h"  5 #include 
     
        6 using namespace std;  7   8 ///  9  10 //在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。 11 //请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 12  13 //首先构造这样一个二维向量 14 void BuildDstArray(vector
      
       
        >&Array) 15 { 16     int nRow = Array[0].size(); 17     int nColumn = Array.size(); 18     for (int i = 0; i < nColumn; i++) 19     { 20         for (int j = 0; j < nRow; j++) 21         { 22             Array[i][j] = i*nRow + j; 23         } 24     } 25  26     for (int i = 0; i < nColumn; i++) 27     { 28         for (int j = 0; j < nRow; j++) 29         { 30             printf("%4d", Array[i][j]); 31         } 32         printf("\n"); 33     } 34  35 } 36  37 //最差情况复杂度为：n+m 38 bool TwoDemoArrayFind(vector
        
         
          >Array,int nDst) 39 { 40     bool bFound = false; 41     if (Array.empty()) 42     { 43         return bFound; 44     } 45     else 46     { 47         int nCurRow = 0; 48         int nCurCol = 0; 49         int nRows = Array[0].size(); 50         int nCols = Array.size(); 51  52         while (nCurRow < nRows&&nCurCol >= 0) 53         { 54             if (Array[nCurCol][nCurRow] == nDst) 55             { 56                 printf("位置：{%d,%d}",nCurCol,nCurRow); 57                 bFound = true; 58                 break; 59             } 60             else 61             { 62                 if (Array[nCurCol][nCurRow] > nDst) 63                 { 64                     nCurRow--; 65                 } 66                 else 67                 { 68                     nCurCol++; 69                 } 70             } 71  72         } 73         return bFound; 74  75     } 76  77  78 } 79 /// 88 int main() 89 { 90     //构造并初始化一个二维向量：4行5列 91     vector
          
           
            > Array(4, vector
            
             (5, 1)); 92 93 //另外一种构造二维向量的方法 94 vector
             
              
               > a; 95 a.resize(4); 96 for (int i = 0; i < 4; i++) 97 { 98 a[i].resize(5); 99 }100 101 BuildDstArray(a);102 TwoDemoArrayFind(a,10);103 104 105 106 getchar();107 return 0;108 }
              
             
            
           
          
         
        
       
      
     

 2 

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

//注意如果输出的是%20d需要对%进行转义

//用Stl中的vector时间复杂度为：O(str.length());空间复杂度O(str.length+3*SpaceNum)

1 void ReplaceSpace( string strSrc,char *sOut) 2 {  3     vector
     
       cOut; 4     const char *pStr = strSrc.data(); 5     while (*pStr != '\0') 6     { 7         if (*pStr == ' ') 8         { 9             cOut.push_back('%');10             cOut.push_back('2');11             cOut.push_back('0');12         }13         else14             cOut.push_back(*pStr);15         pStr++;16     }17     cOut.push_back('\0');18 19     for (int i = 0; i < cOut.size(); i++)20     {21         sOut[i] = cOut[i];22     }23 24 }25 26 //Test27 　　string str= "ni hao ma";28     char pStr[32] = {
   0};29     ReplaceSpace(str,pStr);30     printf("%s",pStr);31     getchar();32     return 0;