室友去面试,问了一个字符串转成数字的算法题,室友没搞出来,我心想,这个不是很简单的吗?因而动手在纸上画了画代码。画完后,总感受哪里不对,最后一个个挖掘,才发现,尼玛,这处处都是坑啊~~~特此记录一下中坑心路。git
首先看一下数字转成字符串。输入一个整型数字,写一个函数,返回整型数字对应的字符串形式。如:github
输入:345 输出:"345"
这个问题第一思路应该是:对整型数字每次求最高位数字,如3,将其转换为对应字符 '3' ,而后将此整型值取下面的数,直到整型值为0,输出字符串。这个问题是,怎么求最高位的数字,能够用一个循环将number累除10,直到number小于10,即为最高位。解法以下:面试
char * int2Str(int nb){ char * str= new char[12];//整型最长11位 str[11]='\0'; unsigned int nindex=0; if(nb<0){ //负数时的状况 str[0]='-'; nb*=-1; //转换为正数 ++nindex; //第0位记录了符号'-',因此下移一位开始记录数字 //若是是正数和0的状况,直接从第0位开始记录数字 }else if(0==nb){ //0时的状况 str[0]='0'; str[1]='\0'; return str; } int tmpNum,len; while(nb!=0){ len=1; tmpNum=nb; while(tmpNum>=10){ len*=10; //记录最高位的位度 tmpNum/=10; //循环累除10求最高位数字 } str[nindex++]=tmpNum+'0'; nb=nb-tmpNum*len; //nb 减去最高位 if(nb==0){ //判断最后一位是否为 0 的状况 str[nindex++]='0'; break; } } str[nindex]='\0'; //添加结束符号 return str; }
在代码A中考虑了全部可能出现的状况,如:整数nb为0或负数时的状况,整数nb的最后一位为0时的状况(仅限此种思路的状况)。能够看到,算法主要的计算部分在两个while循环中,假设nb共有M位。则第一个循环须要循环M次,第二个循环总循环次数为:\((M-1)+(M-2)+...+3+2+1=M(M-1)/2\) ,总共的循环次数为\((M-1)M/2\),时间复杂度为:\(O(M^2)\)。固然,因为整型数字,最长才只有10位(不包含正负号),因此常数时间内便可解决。但有没有其余解法了呢?算法
若是咱们从低位开始转换进字符数组里,而不是从高位开始,那不就能省掉第二个while循环了嘛!问题是,咱们一开始并不知道整数nb有多少位!因此咱们转换的低位放到字符数组str的哪里呢?这里有两种思路:数组
char * int2StrB(int nb){ char * str= new char[12];//整型最长带上符号共11位 str[11]='\0'; unsigned int nindex=0; if(nb<0){ str[0]='-'; nb*=-1; //转换为正数 nindex=1; }else if(0==nb){ str[0]='0'; str[1]='\0'; return str; } unsigned int len=0; //记录nb的位数 int tmpNb=nb; while(0!=tmpNb){ ++len; tmpNb/=10; } if(nindex==0)--len; //在str中定位最后一位数字应该在的位置 str[len+1]='\0'; //设置结束符号 while(0!=nb){ str[len--]=nb%10+'0'; nb/=10; } return str; }
代码B中,首先一个循环求出整数nb(若是nb为负数,此时已经转换为对应的正数)总共位数M,须要循环M次,时间复杂度为\(O(M)\);第二个循环依然是依次遍历整数nb的每一位,时间复杂度依然为\(O(M)\),因此总时间复杂度为:\(O(M)+O(M)=O(M)\)。固然,其实M是有最大数限制的。微信
char * int2StrC(int nb){ char * str= new char[12];//整型最长带上符号共11位 str[11]='\0'; unsigned int nindex=0; if(nb<0){ str[0]='-'; nb*=-1; //转换为正数 nindex=1; }else if(0==nb){ str[0]='0'; str[1]='\0'; return str; } unsigned int nstar=nindex; //记录要逆序的初始位置 while(0!=nb){ str[nindex++]=nb%10+'0'; nb/=10; } str[nindex]='\0'; //字符串逆序 --nindex; while(nstar<nindex){ char tmp=str[nstar]; str[nstar]=str[nindex]; str[nindex]=tmp; ++nstar; --nindex; } return str; }
代码C中也有两个循环,第一个循环完成将整数nb从低位到高位逆序转换进str中,须要时间复杂度为\(O(M)\);第二个循环将对应数字的部分进行逆序,时间复杂度为\(O(M/2)=O(M)\),因此总时间复杂度也为:\(O(M)\)。函数
至于B和C哪一个更好,我是建议用B的,简洁明了。至于谁更快写,确定都比A快,其次因为M是一常数,天然(M+M)>(M+M/2)的,可是在C中比B中的循环多出三条赋值操做,由于M不会大于11,因此,这个谁更好,就难说了~~(不知道这个分析的是否有问题~~~)spa
这个其实就是实现一下C库函数的atoi函数。固然咱们有个简单的处理,就是使用C++的stringstream
类,代码以下:指针
#include <sstream> typedef long long dlong; enum Status{kInvalid=0,kValid}; int g_status=kValid; //合法输入 int str2IntA(const char* str){ g_status=kInvalid; if(str==nullptr || *str=='\0')return 0; //指针不为空,字符串不为空 if(*str!='+' && *str!='-' && (*str<'0' && *str>'9'))return 0; if(*str=='+' || *str=='-'){ //只有 "+" 和 "-" 或 '+'/'-'后跟的不是数字 if(*(str+1)=='\0' || (*(str+1)<'0' && *(str+1)>'9'))return 0; } stringstream stream(str); dlong num=INT_MAX+10; //大于整型最大数,判断溢出 stream>>num; if(num>INT_MAX || num<INT_MIN)return 0; g_status=kValid; return (int)num; }
代码D中,首先咱们要处理的一个问题就是,当输入的字符串非法时,返回什么?返回0吗?但返回0怎么区分这个0不是合法输入返回的呢,因此要引入一个全局变量,当输入非法的时候将全局变量置为非法,不然置为合法。注释中已经说明了可能的非法输入状况,这里就不在多说。可是stringstream流也能将下面的输入正确输出:code
输入: "234dsdf" 输出:234
而咱们知道,这其实输入一个非法的输入。固然咱们能够更改代码进行遍历去判断这个,但其实若是在面试中,我以为考官应该不是但愿咱们使用这个库函数的。而应该是去从新实现C版本的那个atoi函数。因此上代码E:
typedef long long dlong; enum Status{kInvalid=0,kValid}; int g_status=kValid; //合法输入 int str2IntB(const char* str){ g_status=kInvalid; if(str==nullptr || *str=='\0')return 0; //指针不为空,字符串不为空 char const* pstr=str; int flag=1; //判断正负数,默认为正数 dlong num=0; //防溢出 if(*pstr=='-')flag=-1; //负数 else if(*pstr=='+') flag=1; //正数 else if(*pstr<'0' && *pstr>'9')return 0;//非法输入 else num=(*pstr-'0')*flag; //上来就是数字,为正数 ++pstr; if(*pstr!='\0'){ //防止字符串为"+",或 "-"的状况 while(*pstr!='\0'){ //循环求数字 if(*pstr>='0' && *pstr<='9'){ num=num*10+(*pstr-'0')*flag; if((flag==1 && num>INT_MAX) || (flag==-1 && num<INT_MIN)) //防溢出 return 0;//溢出 ++pstr; }else return 0; //非法输入 } if(*pstr=='\0') g_status=kValid; //直达字符串末尾,说明输入合法 } return (int)num; //将 dlong 型强制转换为 int }
至于思路,就是先去除非法输入部分,而后一个数字一个数字的转换为对应字符。注释里说的都已经很清楚了,因此就很少说了。