• 热门专题

关于有序二维矩阵查找和字符串替换的两道算法题

作者:  发布日期:2015-11-12 20:39:21
Tag标签:二维  矩阵  字符串  
  • 最近看一本书上写到的两个面试题 于是实现了一下 感觉思路很好,大牛略过 :

    1、对于一个二维矩阵,从左到右 从上到下 都是递增的,如何判断一个值是否在矩阵内部?(C实现 实现复杂度 O(n))

     

    bool FindInTwoDimensionalMatrix(int*pMatrix,int iRows,int iCols,int iFindVal)
    {
       bool bFind=false ;
       if(pMatrix==0||iRows<=0||iCols<=0)
          return bFind ;
       int iRow=0,iCol=iCols-1;
       while(iRow<iRows&&iCol>=0)
       {
           if(pMatrix[iRow*iCols+iCol]==iFindVal)
           {
             bFind=true ;
             break;
           }else if(pMatrix[iRow*iCols+iCol]>iFindVal)
              --iCol;
            else
              ++iRow;
       }
       return bFind ;
    }
    

    2、在一个内存足够大的空间中,存储的 一串字符序列,替换其中的空格为 %20?(C实现,时间复杂度 O(n))

     

     

    void  ReplaceCharInEnoughMemory(char*pStr)
    {
          if(pStr==0)
            return ;
          //计算空格个数
          int nSpace=0 ;
          int nLen=strlen(pStr);
          char *pBehand,*pFront;
          char *pTem=pStr;
          //计算空格个数
          for(;;)
          {
            //0 结尾  ''
            if(*pTem=='')
               break;
            else if(*pTem==0x20)
            {
              ++nSpace;
            }
            pTem++;
          }
          //后面等于 ''需要添上
          pBehand=pStr+nLen-1+nSpace*2;
          pFront=pStr+nLen-1;
          for(;;)
          {
             if(*pFront!=0x20){
              *pBehand=*pFront ;
             }else{
               *pBehand='0';
               *(--pBehand)='2';
               *(--pBehand)='%';
             }
             if(pFront==pStr)
                break ;
             pBehand--;
             pFront--;
          }
          //结尾
          *(pStr+nLen-1+nSpace*2+1)='';
    }

    好了 就写到这里。

     

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规