简易信息网

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 14|回复: 0

判断一个值是否在二维矩阵内

[复制链接]

29

主题

48

帖子

210

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
210
发表于 2018-1-4 11:09:14 | 显示全部楼层 |阅读模式
最近看一本书上写到的两个面试题 于是实现了一下 感觉思路很好,大牛略过 :
1、对于一个二维矩阵,从左到右  从上到下 都是递增的,如何判断一个值是否在矩阵内部?(C实现  实现复杂度 O(n))

[cpp] view plain copy
print?


  • 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))

[cpp] view plain copy
print?


  • void  ReplaceCharInEnoughMemory(char*pStr)  
  • {  
  •       if(pStr==0)  
  •         return ;  
  •       //计算空格个数  
  •       int nSpace=0 ;  
  •       int nLen=strlen(pStr);  
  •       char *pBehand,*pFront;  
  •       char *pTem=pStr;  
  •       //计算空格个数  
  •       for(;;)  
  •       {  
  •         //0 结尾  '\0'  
  •         if(*pTem=='\0')  
  •            break;  
  •         else if(*pTem==0x20)  
  •         {  
  •           ++nSpace;  
  •         }  
  •         pTem++;  
  •       }  
  •       //后面等于 '\0'需要添上  
  •       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)='\0';  
  • }  


好了 就写到这里。
  今天的心情非常美丽哦!!!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|Comsenz Inc. ( 沪ICP备10006327号-1

GMT+8, 2018-1-18 03:46 , Processed in 0.044541 second(s), 22 queries .

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表