图文精华

About云-梭伦科技»专题 › 技术学习(版主发帖区) › 面试区 › 算法面试题“字符串转换成整数，通配符字符串匹配
分享

算法面试题“字符串转换成整数，通配符字符串匹配

nettman 发表于 2014-11-13 22:07:00 [显示全部楼层] 回帖奖励 阅读模式 关闭右栏 0 24044
About云VIP帮助找工作和提升
问题导读
1、学习算法，需要具备哪些编程外的基础？
2、如何解决，数据类型之间转换的老大难问题？




本文讲两个问题：
第三十章、字符串转换成整数，从确定思路，到写出有瑕疵的代码，继而到microsoft & linux的atoi实现，再到第一份比较完整的代码，最后以Net/OS中的实现结尾，看似很简单的一个问题，其实非常不简单；第三十一章、字符串匹配问题    还是这句老话，有问题恳请随时批评指正，感谢。
第三十章、字符串转换成整数    先看题目：
    输入一个表示整数的字符串，把该字符串转换成整数并输出，例如输入字符串"345"，则输出整数345。
给定函数原型int StrToInt(const char *str) ，完成函数StrToInt，实现字符串转换成整数的功能，不得用库函数atoi（即便准许使用，其对于溢出情况的处理也达不到题目的要求，详情请参看下文第7节末）。

    我们来一步一步分析（共9小节，重点在下文第8小节及后续内容），直至写出第一份准确的代码：
    1、本题考查的实际上就是字符串转换成整数的问题，或者说是要你自行实现atoi函数。那如何实现把表示整数的字符串正确地转换成整数呢？以"345"作为例子
当我们扫描到字符串的第一个字符'3'时，由于我们知道这是第一位，所以得到数字3。当扫描到第二个数字'4'时，而之前我们知道前面有一个3，所以便在后面加上一个数字4，那前面的3相当于30，因此得到数字：3*10+4=34。继续扫描到字符'5'，'5'的前面已经有了34，由于前面的34相当于340，加上后面扫描到的5，最终得到的数是：34*10+5=345。   因此，此题的思路便是：每扫描到一个字符，我们便把在之前得到的数字乘以10，然后再加上当前字符表示的数字。

    2、思路有了，有一些细节需要注意，如zhedahht所说：
“由于整数可能不仅仅之含有数字，还有可能以'+'或者'-'开头，表示整数的正负。因此我们需要把这个字符串的第一个字符做特殊处理。如果第一个字符是'+'号，则不需要做任何操作；如果第一个字符是'-'号，则表明这个整数是个负数，在最后的时候我们要把得到的数值变成负数。接着我们试着处理非法输入。由于输入的是指针，在使用指针之前，我们要做的第一件是判断这个指针是不是为空。如果试着去访问空指针，将不可避免地导致程序崩溃。另外，输入的字符串中可能含有不是数字的字符。每当碰到这些非法的字符，我们就没有必要再继续转换。最后一个需要考虑的问题是溢出问题。由于输入的数字是以字符串的形式输入，因此有可能输入一个很大的数字转换之后会超过能够表示的最大的整数而溢出。”[/ol]    比如，当给的字符串是如左边图片所示的时候，有考虑到么？当然，它们各自对应的正确输出如右边图片所示（假定你是在32位系统下，且编译环境是VS2008以上）：

                                       

    3、很快，可能你就会写下如下代码：  
  1. <span style="background-color: rgb(255, 255, 255);">//copyright@zhedahht 2007</span>
复制代码
run下上述程序，会发现当输入字符串是下图中红叉叉部分所对应的时候，程序结果出错：     

  
两个问题：
当输入的字符串不是数字，而是字符的时候，比如“1a”，上述程序直接返回了0（而正确的结果应该是得到1）：
  1. // if the char is not a digit, invalid input

  2.                                   else

  3.                                   {

  4.                                           num = 0;

  5.                                           break;

  6.                                   }
复制代码

处理溢出时，有问题。因为它遇到溢出情况时，直接返回了0：
  1. // overflow 

  2. if(num > std::numeric_limits::max())

  3. {

  4. num = 0;

  5. break;

  6. }[/ol]
复制代码

    4、把代码做下微调，如下（注：库函数atoi规定超过int值，按最大值maxint：2147483647来，超过-int按最小值minint：-2147483648来）：
  1. //copyright@SP_daiyq 2013/5/29

  2. int StrToInt(const char* str)

  3. {

  4.         int res = 0; // result

  5.         int i = 0; // index of str

  6.         int signal = '+'; // signal '+' or '-'

  7.         int cur; // current digit

  8.         if (!str)

  9.                 return 0;

  10.         // skip backspace

  11.         while (isspace(str))

  12.                 i++;

  13.         // skip signal

  14.         if (str == '+' || str == '-')

  15.         {

  16.                 signal = str;

  17.                 i++;

  18.         }

  19.         // get result

  20.         while (str >= '0' && str  INT_MAX - res*10) )

  21.                 {

  22.                         res = INT_MAX;

  23.                         break;

  24.                 }

  25.                 else if ( (signal == '-') && (cur -1 > INT_MAX - res*10) )

  26.                 {

  27.                         res = INT_MIN;

  28.                         break;

  29.                 }

  30.                 res = res * 10 + cur;

  31.                 i++;

  32.         }

  33.         return (signal == '-') ? -res : res;

  34. }    
复制代码


此时会发现，上面第3小节末所述的第1个小问题（当输入的字符串不是数字，而是字符的时候）解决了：   



但， 上文第3小节末所述的第2个小问题：溢出问题却没有解决。即当给定下述测试数据的时候，问题就来了：               
需要转换的字符串代码运行结果    理应得到的正确结果   

   
什么问题呢？比如说用上述代码转换这个字符串："    10522545459"，它本应得到的正确结果应该是2147483647，但程序实际得到的结果却是：1932610867。故很明显，程序没有解决好上面的第2个小问题：溢出问题。原因是什么呢？咱们来分析下代码，看是如何具体处理溢出情况的：
  1. // judge overlap or not

  2.                 if ( (signal == '+') && (cur > INT_MAX - res*10) )

  3.                 {

  4.                         res = INT_MAX;

  5.                         break;

  6.                 }

  7.                 else if ( (signal == '-') && (cur -1 > INT_MAX - res*10) )

  8.                 {

  9.                         res = INT_MIN;

  10.                         break;

  11.                 }    
复制代码

接着上面的例子来，比如给定字符串"    10522545459"，除去空格有11位，而MAX_INT，即2147483647是10位数，当扫描到最后一个字符‘9’的时候，程序会比较 9 和 2147483647 - 1052254545*10的大小。     问题立马就暴露出来了，因为此时让res*10，即让1052254545*10 > MAX_INT，溢出无疑，程序已经出错，再执行下面这行代码已无意义：cur > INT_MAX - res*10    也就是说，对于字符串"10522545459", 当扫描到最后一个字符‘9’时，根据上文第1小节的字符串转换成整数的思路：“每扫描到一个字符，我们便把在之前得到的数字乘以10，然后再加上当前字符表示的数字”，为了得到最终的整数，我们得如此计算：1052254545*10 + 4，
    然实际上当程序计算到1052254545*10时，
1052254545*10 >
2147483647
    此时已经溢出了,若再执意计算，则程序逻辑将出错，故此后也就不能再判断字串的最后一位4是否大于2147483647%10了（耐不得烦想尽快看到最终正确代码的读者可以直接跳到下文第8节）。

    5、上面说给的程序没有“很好的解决溢出问题。由于输入的数字是以字符串的形式输入，因此有可能输入一个很大的数字转换之后会超过能够表示的最大的整数而溢出”。那么，到底代码该如何写呢？    像下面这样？：
  1. <span style="background-color: rgb(255, 255, 255);">//copyright@fuwutu 2013/5/29</span>
复制代码

run下程序，看看运行结果：   

     上图所示程序貌似通过了，然实际上它还是未能处理数据溢出的问题，因为它只是做了个取巧，即把返回的值esult定义成了long long，如下所示：long long result = 0;    故严格说来，我们依然未写出准确的规范代码。

    6、那到底该如何解决这个数据溢出的问题呢？咱们先来看看Microsoft是如何实现atoi的吧：//atol函数
  1. //Copyright (c) 1989-1997, Microsoft Corporation. All rights reserved.

  2. long __cdecl atol(

  3.         const char *nptr

  4.         )

  5. {

  6.         int c; /* current char */

  7.         long total; /* current total */

  8.         int sign; /* if ''-'', then negative, otherwise positive */

  9.         /* skip whitespace */

  10.         while ( isspace((int)(unsigned char)*nptr) )

  11.                 ++nptr;

  12.         c = (int)(unsigned char)*nptr++;

  13.         sign = c; /* save sign indication */

  14.         if (c == ''-'' || c == ''+'')

  15.                 c = (int)(unsigned char)*nptr++; /* skip sign */

  16.         total = 0;

  17.         while (isdigit(c)) {

  18.                 total = 10 * total + (c - ''0''); /* accumulate digit */

  19.                 c = (int)(unsigned char)*nptr++; /* get next char */

  20.         }

  21.         if (sign == ''-'')

  22.                 return -total;

  23.         else

  24.                 return total; /* return result, negated if necessary */

  25. }
复制代码
其中，isspace和isdigit函数的实现代码为： 
  1. <span style="background-color: rgb(255, 255, 255);">isspace(int x) </span>
复制代码
然后atoi调用上面的atol函数，如下所示：//atoi调用上述的atol
  1. int __cdecl atoi(

  2.         const char *nptr

  3.         )

  4. {

  5.         //Overflow is not detected. Because of this, we can just use

  6.         return (int)atol(nptr);

  7. }
复制代码
但很遗憾的是，上述atoi标准代码依然返回的是long：
  1. long total; /* current total */

  2. if (sign == ''-'')

  3.         return -total;

  4. else

  5.         return total; /* return result, negated if necessary */
复制代码

再者，下面这里定义成long的total与10相乘，即total*10很容易溢出：
  1. long total; /* current total */

  2. total = 10 * total + (c - ''0''); /* accumulate digit */
复制代码
最后，根据本文评论下的读者meiyuli反应：“测试数据是字符串"-21474836480"，api算出来的是-2147483648，用上述代码算出来的结果是0”，如此，上述微软的这个atoi源码是有问题的。

7、microsoft既然不行，读者想必很自然的想到linux。So，咱们接下来便看看linux内核中是如何实现此字符串转换为整数的问题的。linux内核中提供了以下几个函数：[ol]simple_strtol，把一个字符串转换为一个有符号长整数；simple_strtoll，把一个字符串转换为一个有符号长长整数；simple_strtoul，把一个字符串转换为一个无符号长整数；simple_strtoull，把一个字符串转换为一个无符号长长整数相关源码及分析如下。首先，atoi调下面的strtol：//linux/lib/vsprintf.c
  1. //Copyright (C) 1991, 1992  Linus Torvalds

  2. //simple_strtol - convert a string to a signed long

  3. long simple_strtol(const char *cp, char **endp, unsigned int base)

  4. {

  5.         if (*cp == '-')

  6.                 return -simple_strtoul(cp + 1, endp, base);

  7.         return simple_strtoul(cp, endp, base);

  8. }

  9. EXPORT_SYMBOL(simple_strtol);   
复制代码

然后，上面的strtol调下面的strtoul：//simple_strtoul - convert a string to an unsigned long
  1. unsigned long simple_strtoul(const char *cp, char **endp, unsigned int base)

  2. {

  3.         return simple_strtoull(cp, endp, base);

  4. }

  5. EXPORT_SYMBOL(simple_strtoul);
复制代码
接着，上面的strtoul调下面的strtoull：
  1. //simple_strtoll - convert a string to a signed long long

  2. long long simple_strtoll(const char *cp, char **endp, unsigned int base)

  3. {

  4.         if (*cp == '-')

  5.                 return -simple_strtoull(cp + 1, endp, base);

  6.         return simple_strtoull(cp, endp, base);

  7. }

  8. EXPORT_SYMBOL(simple_strtoll);    
复制代码

最后，strtoull调_parse_integer_fixup_radix和_parse_integer来处理相关逻辑：
  1. //simple_strtoull - convert a string to an unsigned long long

  2. unsigned long long simple_strtoull(const char *cp, char **endp, unsigned int base)

  3. {

  4.         unsigned long long result;

  5.         unsigned int rv;

  6.         cp = _parse_integer_fixup_radix(cp, &base);

  7.         rv = _parse_integer(cp, base, &result);

  8.         /* FIXME */

  9.         cp += (rv & ~KSTRTOX_OVERFLOW);

  10.         if (endp)

  11.                 *endp = (char *)cp;

  12.         return result;

  13. }

  14. EXPORT_SYMBOL(simple_strtoull);
复制代码
重头戏来了。接下来，我们来看上面strtoull函数中的parse_integer_fixup_radix和_parse_integer两段代码。如鲨鱼所说“真正的处理逻辑主要是在_parse_integer里面，关于溢出的处理，_parse_integer处理的很优美，而_parse_integer_fixup_radix是用来自动根据字符串判断进制的”。    先来看_parse_integer函数：
  1. //lib/kstrtox.c, line 39 

  2. //Convert non-negative integer string representation in explicitly given radix to an integer. 

  3. //Return number of characters consumed maybe or-ed with overflow bit. 

  4. //If overflow occurs, result integer (incorrect) is still returned. 

  5. unsigned int _parse_integer(const char *s, unsigned int base, unsigned long long *p) 

  6. { 

  7. unsigned long long res; 

  8. unsigned int rv; 

  9. int overflow; 

  10. 

  11. res = 0; 

  12. rv = 0; 

  13. overflow = 0; 

  14. while (*s) { 

  15. unsigned int val; 

  16. 

  17. if ('0' = base) 

  18. break; 

  19. /* 

  20. * Check for overflow only if we are within range of 

  21. * it in the max base we support (16) 

  22. */ 

  23. if (unlikely(res & (~0ull div_u64(ULLONG_MAX - val, base)) 

  24. overflow = 1; 

  25. } 

  26. res = res * base + val; 

  27. rv++; 

  28. s++; 

  29. } 

  30. *p = res; 

  31. if (overflow) 

  32. rv |= KSTRTOX_OVERFLOW; 

  33. return rv; 

  34. }
复制代码

解释下两个小细节上头出现了个unlikely，其实unlikely和likely经常出现在linux相关内核源码中
  1. if(likely(value)){

  2.         //等价于if(likely(value)) == if(value)

  3. }

  4. else{

  5. }
复制代码

likely表示value为真的可能性更大，而unlikely表示value为假的可能性更大，这两个宏被定义成：
  1. //include/linux/compiler.h

  2. # ifndef likely

  3. #  define likely(x)        (__builtin_constant_p(x) ? !!(x) : __branch_check__(x, 1))

  4. # endif

  5. # ifndef unlikely

  6. #  define unlikely(x)        (__builtin_constant_p(x) ? !!(x) : __branch_check__(x, 0))

  7. # endif
复制代码


呈现下div_u64的代码：
  1. //include/linux/math64.h

  2. //div_u64

  3. static inline u64 div_u64(u64 dividend, u32 divisor)

  4. {

  5.         u32 remainder;

  6.         return div_u64_rem(dividend, divisor, &remainder);

  7. }

  8. //div_u64_rem

  9. static inline u64 div_u64_rem(u64 dividend, u32 divisor, u32 *remainder)

  10. {

  11.         *remainder = dividend % divisor;

  12.         return dividend / divisor;

  13. }
复制代码


最后看下_parse_integer_fixup_radix函数：
  1. //lib/kstrtox.c, line 23

  2. const char *_parse_integer_fixup_radix(const char *s, unsigned int *base)

  3. {

  4.         if (*base == 0) {

  5.                 if (s[0] == '0') {

  6.                         if (_tolower(s[1]) == 'x' && isxdigit(s[2]))

  7.                                 *base = 16;

  8.                         else

  9.                                 *base = 8;

  10.                 } else

  11.                         *base = 10;

  12.         }

  13.         if (*base == 16 && s[0] == '0' && _tolower(s[1]) == 'x')

  14.                 s += 2;

  15.         return s;

  16. }    
复制代码

读者MJN君在我的建议下，对上述linux内核中的atoi函数进行了测试，咱们来看下测试结果如何。
  1. <span style="background-color: rgb(255, 255, 255);">2147483647 : 2147483647</span>
复制代码
如上，根据程序的输出结果可以看出，对于某些溢出的情况，atoi程序的处理并不符合本题的要求。 也就是说，atoi程序对溢出的处理是一个标准，而本题要求对溢出的处理则是另外一个标准，所以说直接用atoi程序达不到本题的要求，但你不能因为本题的标准而否认atoi程序的正确性。  既然直接借用atoi的源码（原理是parseXXX，int i=Integer.parseInt(String str)，把str转换成int的方法），不符合题目要求，则咱们另寻他路。  路漫漫其修远兮，吾等将上下而求索，但与此同时，我们已渐入佳境。     8、根据我们第1小节达成一致的字符串转换成整数的思路：“每扫描到一个字符，我们便把在之前得到的数字乘以10，然后再加上当前字符表示的数字”，相信读者已经觉察到，在扫描到最后一个字符的时候，如果之前得到的数比较大，此时若再让其扩大10倍，相对来说是比较容易溢出的。

但车到山前必有路，既然让一个比较大的int整型数括大10倍，比较容易溢出， 那么在不好判断是否溢出的情况下，可以尝试使用除法。即如MJN所说：与其将n扩大10倍,，冒着溢出的风险, 再与MAX_INT进行比较（如果已经溢出, 则比较的结果没有意义），不如未雨绸缪先用n与MAX_INT/10进行比较： 若n>MAX_INT/10（当然同时还要考虑n=MAX_INT/10的情况）， 说明最终得到的整数一定会溢出， 故此时可以当即进行溢出处理，直接返回最大值MAX_INT，从而也就免去了计算n*10这一步骤。[/ol]    也就是说，计算n*10前,先比较n与MAX_INT/10大小，若n>MAX_INT/10，那么n*10肯定大于MAX_INT，即代表最后得到的整数n肯定溢出，既然溢出，不能再计算n*10，直接提前返回MAX_INT就行了。    一直以来，我们努力的目的归根结底是为了更好的处理溢出，但上述做法最重要的是巧妙的规避了计算n*10这一乘法步骤，转换成计算除法MAX_INT/10代替，不能不说此法颇妙。
   他的代码如下，如有问题请指出：
  1. //copyright@njnu_mjn 2013

  2. int StrToDecInt(const char* str)    

  3. {    

  4.     static const int MAX = (int)((unsigned)~0 >> 1);    

  5.     static const int MIN = -(int)((unsigned)~0 >> 1) - 1;    

  6.     unsigned int n = 0;    

  7.     int sign = 1;    

  8.     int c;    

  9.     

  10.     while (isspace(*str))    

  11.         ++str;    

  12.     if (*str == '+' || *str == '-')    

  13.     {    

  14.         if (*str == '-')    

  15.             sign = -1;    

  16.         ++str;    

  17.     }    

  18.     while (isdigit(*str))    

  19.     {    

  20.         c = *str - '0';    

  21.         if (sign > 0 && (n > MAX/10 || (n == MAX/10 && c > MAX%10)))    

  22.         {    

  23.             n = MAX;    

  24.             break;    

  25.         }    

  26.         else if (sign  (unsigned)MIN/10     

  27.                               || (n == (unsigned)MIN/10 && c > (unsigned)MIN%10)))    

  28.         {    

  29.             n = MIN;    

  30.             break;    

  31.         }    

  32.         n = n * 10 + c;    

  33.         ++str;    

  34.     }    

  35.     return sign > 0 ? n : -n;    

  36. }
复制代码
   上述代码从测试结果来看，暂未发现什么问题
                             输入                 输出
  1.          10522545459 :     2147483647

  2.          -10522545459 :   -2147483648
复制代码
   咱们再来总结下上述代码是如何处理溢出情况的。对于正数来说，它溢出的可能性有两种
一种是诸如2147483650，即n > MAX/10 的；一种是诸如2147483649，即n == MAX/10 && c > MAX%10。故咱们上面处理溢出情况的代码便是：
  1. c = *str - '0';  

  2.         if (sign > 0 && (n > MAX/10 || (n == MAX/10 && c > MAX%10)))  

  3.         {  

  4.             n = MAX;  

  5.             break;  

  6.         }  

  7.         else if (sign  (unsigned)MIN/10   

  8.                               || (n == (unsigned)MIN/10 && c > (unsigned)MIN%10)))  

  9.         {  

  10.             n = MIN;  

  11.             break;  

  12.         }
复制代码
不过，即便如此，有些细节是改进的，如他自己所说n的声明及定义应该为
  1. int n = 0;
复制代码
将MAX/10,MAX%10,(unsigned)MIN/10及(unsigned)MIN%10保存到变量中, 防止重复计算 这样，优化后的代码为：
  1. //copyright@njnu_mjn 2013

  2. int StrToDecInt(const char* str)  

  3. {  

  4.     static const int MAX = (int)((unsigned)~0 >> 1);  

  5.     static const int MIN = -(int)((unsigned)~0 >> 1) - 1;  

  6.     static const int MAX_DIV = (int)((unsigned)~0 >> 1) / 10;  

  7.     static const int MIN_DIV = (int)((((unsigned)~0 >> 1) + 1) / 10);  

  8.     static const int MAX_R = (int)((unsigned)~0 >> 1) % 10;  

  9.     static const int MIN_R = (int)((((unsigned)~0 >> 1) + 1) % 10);  

  10.     int n = 0;  

  11.     int sign = 1;  

  12.     int c;  

  13.   

  14.     while (isspace(*str))  

  15.         ++str;  

  16.     if (*str == '+' || *str == '-')  

  17.     {  

  18.         if (*str == '-')  

  19.             sign = -1;  

  20.         ++str;  

  21.     }  

  22.     while (isdigit(*str))  

  23.     {  

  24.         c = *str - '0';  

  25.         if (sign > 0 && (n > MAX_DIV || (n == MAX_DIV && c >= MAX_R)))  

  26.         {  

  27.             n = MAX;  

  28.             break;  

  29.         }  

  30.         else if (sign  MIN_DIV   

  31.                                                     || (n == MIN_DIV && c >= MIN_R)))  

  32.         {  

  33.             n = MIN;  

  34.             break;  

  35.         }  

  36.         n = n * 10 + c;  

  37.         ++str;  

  38.     }  

  39.     return sign > 0 ? n : -n;  

  40. }      
复制代码

部分数据的测试结果如下图所示：输入输出
  1. 10522545459  : 2147483647

  2. -10522545459 : -2147483648

  3. 2147483648   : 2147483647

  4. -2147483648  : -2147483648
复制代码
是否已是完美？如MJN君本人所说“我的实现与linux内核的atoi函数的实现, 都有一个共同的问题: 即使出错, 函数也返回了一个值, 导致调用者误认为自己传入的参数是正确的, 但是可能会导致程序的其他部分产生莫名的错误且很难调试”。

9、最后看下Nut/OS中atoi的实现，同时，本小节内容主要来自参考文献条目9，即MJN的博客：
  1. 00077 #include 

  2. 00078 #include 

  3. 00079 

  4. 00084 

  5. 00092 int atoi(CONST char *str)

  6. 00093 {

  7. 00094     return ((int) strtol(str, (char **) NULL, 10));

  8. 00095 }  
复制代码

上述代码中strtol实现的思想跟上文第7节所述的MJN君的思路类似，也是除法代替乘法。加上测试函数后的具体代码如下：
  1. #include 

  2. #include 

  3. #include 

  4. #include 

  5. #define CONST      const

  6. long mstrtol(CONST char *nptr, char **endptr, int base)

  7. {

  8.     register CONST char *s;

  9.     register long acc, cutoff;

  10.     register int c;

  11.     register int neg, any, cutlim;

  12.     /*

  13.      * Skip white space and pick up leading +/- sign if any.

  14.      * If base is 0, allow 0x for hex and 0 for octal, else

  15.      * assume decimal; if base is already 16, allow 0x.

  16.      */

  17.     s = nptr;

  18.     do {

  19.         c = (unsigned char) *s++;

  20.     } while (isspace(c));

  21.     if (c == '-') {

  22.         neg = 1;

  23.         c = *s++;

  24.     } else {

  25.         neg = 0;

  26.         if (c == '+')

  27.             c = *s++;

  28.     }

  29.     if ((base == 0 || base == 16) && c == '0' && (*s == 'x' || *s == 'X')) {

  30.         c = s[1];

  31.         s += 2;

  32.         base = 16;

  33.     }

  34.     if (base == 0)

  35.         base = c == '0' ? 8 : 10;

  36.     /*

  37.      * Compute the cutoff value between legal numbers and illegal

  38.      * numbers.  That is the largest legal value, divided by the

  39.      * base.  An input number that is greater than this value, if

  40.      * followed by a legal input character, is too big.  One that

  41.      * is equal to this value may be valid or not; the limit

  42.      * between valid and invalid numbers is then based on the last

  43.      * digit.  For instance, if the range for longs is

  44.      * [-2147483648..2147483647] and the input base is 10,

  45.      * cutoff will be set to 214748364 and cutlim to either

  46.      * 7 (neg==0) or 8 (neg==1), meaning that if we have accumulated

  47.      * a value > 214748364, or equal but the next digit is > 7 (or 8),

  48.      * the number is too big, and we will return a range error.

  49.      *

  50.      * Set any if any `digits' consumed; make it negative to indicate

  51.      * overflow.

  52.      */

  53.     cutoff = neg ? LONG_MIN : LONG_MAX;

  54.     cutlim = cutoff % base;

  55.     cutoff /= base;

  56.     if (neg) {

  57.         if (cutlim > 0) {

  58.             cutlim -= base;

  59.             cutoff += 1;

  60.         }

  61.         cutlim = -cutlim;

  62.     }

  63.     for (acc = 0, any = 0;; c = (unsigned char) *s++) {

  64.         if (isdigit(c))

  65.             c -= '0';

  66.         else if (isalpha(c))

  67.             c -= isupper(c) ? 'A' - 10 : 'a' - 10;

  68.         else

  69.             break;

  70.         if (c >= base)

  71.             break;

  72.         if (any  cutlim) {

  73.                 any = -1;

  74.                 acc = LONG_MIN;

  75.                 errno = ERANGE;

  76.             } else {

  77.                 any = 1;

  78.                 acc *= base;

  79.                 acc -= c;

  80.             }

  81.         } else {

  82.             if ((acc > cutoff || acc == cutoff) && c > cutlim) {

  83.                 any = -1;

  84.                 acc = LONG_MAX;

  85.                 errno = ERANGE;

  86.             } else {

  87.                 any = 1;

  88.                 acc *= base;

  89.                 acc += c;

  90.             }

  91.         }

  92.     }

  93.     if (endptr != 0)

  94.         *endptr = (char *) (any ? s - 1 : nptr);

  95.     return (acc);

  96. }

  97. int matoi2(CONST char *str)

  98. {

  99.     return ((int) mstrtol(str, (char **) NULL, 10));

  100. }

  101. int mgetline(char* buf, size_t n) {

  102.   size_t idx = 0;

  103.   int c;

  104.   

  105.   while (--n > 0 && (c = getchar()) != EOF && c != '\n') {

  106.     buf[idx++] = c;

  107.   }

  108.   buf[idx] = '\0';

  109.   return idx;

  110. }

  111. #define MAX_LINE 200

  112. int main() {

  113.     char buf[MAX_LINE];

  114.     while (mgetline(buf, MAX_LINE) >= 0) {

  115.         if (strcmp(buf, "quit") == 0) break;

  116.         printf("matoi2=%d\n", matoi2(buf));

  117.     }

  118.     return 0;

  119. }    
复制代码

同样，MJN对上述实现测试了下，结果如下:
  1. 10522545459

  2. matoi2=2147483647

  3. -10522545459

  4. matoi2=-2147483648
复制代码

    程序貌似对溢出的处理是正确的, 真的吗? 再把测试数据换成"10522545454"（与"10522545459"的区别在于最后一个字符）
  1. 10522545454

  2. matoi2=1932610862

  3. -10522545454

  4. matoi2=-1932610862
复制代码

   症结就在于下面这段代码：
  1. if (neg) {

  2.             if ((acc  cutlim) {

  3.                 any = -1;

  4.                 acc = LONG_MIN;

  5.                 errno = ERANGE;

  6.             } else {

  7.                 any = 1;

  8.                 acc *= base;

  9.                 acc -= c;

  10.             }

  11.         } else {

  12.             if ((acc > cutoff || acc == cutoff) && c > cutlim) {

  13.                 any = -1;

  14.                 acc = LONG_MAX;

  15.                 errno = ERANGE;
复制代码

要想得到正确的输出结果，需要改动两个地方：
    ①其中这行：
  1. if ((acc > cutoff || acc == cutoff) && c > cutlim)    应该改为：

  2. if ( acc > cutoff ||  (acc == cutoff) && c > cutlim)  )    ②与此同时，这行:

  3. if ((acc  cutlim) {    改为：

  4. if (acc  cutlim)) {   
复制代码
为何要这样修改呢？细心的读者相信还是会记得上文第8节中关于正数的两种溢出情况的可能性：“对于正数来说，它溢出的可能性有两种：一种是诸如2147483650，即n > MAX/10 的；一种是诸如2147483649，即n == MAX/10 && c > MAX%10。”[/ol]    也就是说无论是"10522545459"，还是"10522545454"，都是属于第1种情况，即“诸如2147483650，即n > MAX/10的”，此时直接返回MAX_INT即可，所以不需要也不能再去判断n == MAX/10的情况。
    这个处理思路类似于上文第8节处理溢出情况的代码：
  1. if (sign > 0 && (n > MAX/10 || (n == MAX/10 && c > MAX%10)))    

  2.         {    

  3.             n = MAX;    

  4.             break;    

  5.         }    

  6.         else if (sign  (unsigned)MIN/10     

  7.                               || (n == (unsigned)MIN/10 && c > (unsigned)MIN%10)))    

  8.         {    

  9.             n = MIN;    

  10.             break;    

  11.         }    
复制代码
修改过后的代码测试正常:
  1. 10522545459

  2. matoi2=2147483647

  3. -10522545459\

  4. matoi2=-2147483648

  5. 10522545454

  6. matoi2=2147483647

  7. -10522545454

  8. matoi2=-2147483648
复制代码

quit    OK，字符串转换成整数这一问题已基本解决。但如果面试官继续问你，如何把整数转换成字符串呢？欢迎于本文评论下或hero上show出你的思路或代码。

第三十一章、带通配符的字符串匹配问题字符串匹配问题，给定一串字符串，按照指定规则对其进行匹配，并将匹配的结果保存至output数组中，多个匹配项用空格间隔，最后一个不需要空格。
要求
匹配规则中包含通配符？和*，其中？表示匹配任意一个字符，*表示匹配任意多个（>=0）字符。匹配规则要求匹配最大的字符子串，例如a*d,匹配abbdd而非abbd,即最大匹配子串。匹配后的输入串不再进行匹配，从当前匹配后的字符串重新匹配其他字符串。请实现函数：char* my_find(char  input[],   char rule[])
举例说明
        input:abcadefg
        rule:a?c
        output:abc
        input :newsadfanewfdadsf
        rule: new
        output: new new
        input :breakfastfood
        rule: f*d
        output:fastfood

注意事项
自行实现函数my_find，勿在my_find函数里夹杂输出，且不准用C、C++库，和Java的String对象；请注意代码的时间，空间复杂度，及可读性，简洁性；input=aaa，rule=aa时，返回一个结果aa，即可。
    1、本题与上述第三十章的题不同，上题字符串转换成整数更多考察对思维的全面性和对细节的处理，本题则更多的是编程技巧。闲不多说，直接上代码：
  1. //copyright@cao_peng 2013/4/23

  2. int str_len(char *a) {  //字符串长度

  3.         if (a == 0) {

  4.                 return 0;

  5.         }

  6.         char *t = a;

  7.         for (;*t;++t)

  8.                 ;

  9.         return (int) (t - a);

  10. }

  11. void str_copy(char *a,const char *b,int len) {  //拷贝字符串 a = b

  12.         for (;len > 0; --len, ++b,++a) {

  13.                 *a = *b;

  14.         }

  15.         *a = 0;

  16. }

  17. char *str_join(char *a,const char *b,int lenb) { //连接字符串 第一个字符串被回收

  18.         char *t;

  19.         if (a == 0) {

  20.                 t = (char *) malloc(sizeof(char) * (lenb + 1)); 

  21.                 str_copy(t, b, lenb);

  22.                 return t;

  23.         }

  24.         else {

  25.                 int lena = str_len(a);

  26.                 t = (char *) malloc(sizeof(char) * (lena + lenb + 2));

  27.                 str_copy(t, a, lena);

  28.                 *(t + lena) = ' ';

  29.                 str_copy(t + lena + 1, b, lenb);

  30.                 free(a);

  31.                 return t;

  32.         }

  33. }

  34. int canMatch(char *input, char *rule) { // 返回最长匹配长度 -1表示不匹配　

  35.         if (*rule == 0) { //已经到rule尾端

  36.                 return 0;

  37.         }

  38.         int r = -1 ,may;

  39.         if (*rule == '*') {

  40.                 r = canMatch(input, rule + 1);  // *匹配0个字符

  41.                 if (*input) {

  42.                         may = canMatch(input + 1, rule);  // *匹配非0个字符

  43.                         if ((may >= 0) && (++may > r)) {

  44.                                 r = may;

  45.                         }

  46.                 }

  47.         }

  48.         if (*input == 0) {  //到尾端

  49.                 return r;

  50.         }

  51.         if ((*rule == '?') || (*rule == *input)) {

  52.                 may = canMatch(input + 1, rule + 1);

  53.                 if ((may >= 0) && (++may > r)) {

  54.                         r = may;

  55.                 }

  56.         }

  57.         return r;

  58. }

  59. char * my_find(char  input[],   char rule[]) {

  60.         int len = str_len(input);

  61.         int *match = (int *) malloc(sizeof(int) * len);  //input第i位最多能匹配多少位 匹配不上是-1

  62.         int i,max_pos = - 1;

  63.         char *output = 0;

  64.         for (i = 0; i  match[max_pos])) {

  65.                         max_pos = i;

  66.                 }

  67.         }

  68.         if ((max_pos     
复制代码


2、本题也可以直接写出DP方程，如下代码所示：
  1. //copyright@chpeih 2013/4/23

  2. char* my_find(char  input[],   char rule[])

  3. {

  4.         //write your code here

  5.         int len1,len2;

  6.         for(len1 = 0;input[len1];len1++);

  7.         for(len2 = 0;rule[len2];len2++);

  8.         int MAXN = len1>len2?(len1+1):(len2+1);

  9.         int  **dp;

  10.         //dp[j]表示字符串1和字符串2分别以i j结尾匹配的最大长度

  11.         //记录dp[j]是由之前那个节点推算过来  i*MAXN+j

  12.         dp = new int *[len1+1];

  13.         for (int i = 0;im){

  14.                         m = dp[len2];

  15.                         count_ans = 0;

  16.                         ans[count_ans++] = i-m;

  17.                 }else if(dp[len2]!=-1 &&dp[len2]==m){

  18.                         ans[count_ans++] = i-m;

  19.                 }

  20.                 if (count_ans!=0)

  21.                 {    

  22.                         int len = ans[0];

  23.                         for (int i = 0;i
复制代码

回复

使用道具 举报

自定义广告语

没找到任何评论，期待你打破沉寂

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发表新帖
nettman

超级版主

关注

  • 2910

    主题

  • 3203

    帖子

  • 478

    粉丝

TA的主题
关闭

推荐上一条 /2 下一条

关于我们· 联系我们· 加入我们· 小黑屋· 合作伙伴   

Copyright © 2001-2024 About云-梭伦科技 Powered by Discuz! X3.4 Licensed Discuz Team.

简书 / Smrz 京ICP备2020039040号 Wxb 简书网举报电话：021-34700000