常见问题整理

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

  1 // IO_Solution.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 #include <vector>
  6 using namespace std;
  7 
  8 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  9 
 10 //在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 11 //请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 12 
 13 //首先构造这样一个二维向量
 14 void BuildDstArray(vector<vector<int>>&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<vector <int>>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<vector<int>> Array(4, vector<int>(5, 1));
 92 
 93     //另外一种构造二维向量的方法
 94     vector<vector<int>> 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 }

请实现一个函数，将一个字符串中的空格替换成“ % 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<char> 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         else
14             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 //Test
27 　　string str= "ni hao ma";
28     char pStr[32] = {0};
29     ReplaceSpace(str,pStr);
30     printf("%s",pStr);
31     getchar();
32     return 0;

秒客网

常见问题整理

相关文章