LeetCode刷题笔记 08 String to integer

作者：马志峰 链接：https://zhuanlan.zhihu.com/p/24047577 来源：知乎 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

链接

https://leetcode.com/problems/string-to-integer-atoi/

题目

实现atoi，将string转成integer

释义

这道题目重点还是考虑存在哪些可能的情况

非数字字符怎么处理 正负号溢出

当然，思路肯定是对string中的每一个字符进行处理，那么怎么把字符'1'转成数字1呢?

小马哥比较笨，想了半天没想到

想到了可能跟ASCII表有关，但是没能深入研究，最后偷看了答案。。。

你们就有福气了，如果没想到也不用去看答案了，我来告诉你们

'1' - '0' = 1;

对，和字符0相减就可以了。就是因为它们在表中是连续的

好了，关键问题解决了，我们再看一下几个特殊情况要怎么处理

非数字字符，我们可以忽略掉开头和结尾的空字符(“ 23 “)，如果数字中间有其它字符(“123x21”)，则认为后面是非法输入正负号，需要存下来溢出，我们还有上一道题目的方法，用long long来处理

补充描述

我们可以根据题目的补充描述来写一些测试用例：

“ 123 ” → 123“ -123 “ → -123“ 123x456 “ → 123“ 123 456” → 123“343485894858938553” → INT_MAX“” → 0“xxxyyy” → 0

做题之前可以预习一下c++支持哪些字符操作，见《C++ Primer》第五版（中文版） P82，表3.3

万事俱备，开始正式做题了

代码

class Solution { public: int myAtoi(string str) { int iFlag = 1; bool bStart = false; vector<int> vecDigits; for( auto c : str ) { if( !bStart ) { if( isspace(c) ) { continue; } if( ('+' == c || '-' == c ) ) { iFlag = '+' == c ? 1 : -1; bStart = true; continue; } } if( isdigit(c) ) { bStart = true; vecDigits.push_back( c - '0' ); } else { break; } } if( vecDigits.size() == 0 ) { return 0; } long long result = 0; long long iFactor = 1; auto i = vecDigits.size(); while( i > 0 ) { --i; result += iFactor * vecDigits[i]; iFactor *= 10; if( result*iFlag > INT_MAX ) { return INT_MAX; } if( result*iFlag < INT_MIN ) { return INT_MIN; } } return result*iFlag; } };

逻辑有点复杂，我来解释一下：

第一个for循环用来把合法的数字push到一个vector中 iFlag用来保存正负号bStart用来保存是不是已经开始处理数字了，之所以加这个flag，是因为数字前的空格和数字后的空格处理方式不同 如果for循环之后，vector仍为空，则没有合法数字，直接返回0后面的while语句用来得到整数，和前一题的方式相同。这里把溢出判断放到了循环内部，是避免出现比long long还要长的字符串

当然，这个代码也是做了几次修改的，目的就是能在leetcode上通过。

然后我们再来看看能不能简化上面的逻辑

在动手修改代码之前，我们要思考一个问题，如何在简化代码的时候保证逻辑的正确性？

这是一个非常普遍的问题，在编码的过程中我们会经常遇到。本来是想对代码负责，做到精益求精，结果速度上去了，但是结果不对了，这就得不偿失了。

要解决这个问题，可以试试“测试驱动开发”的方法，即在开始写代码之前先设计好测试用例，如果代码能通过所有的测试用例，则达到了我们的功能要求。后续再进行代码修改的时候，也要保证所有用例都能通过，如果有用例失败了，则说明修改代码出了问题。

正如前面我们写的那些用例，当然这些用例肯定不够充分，不过比什么都不写要强多了。要知道leetcode上这道题目有1047个测试用例！

在写一些小程序时，我们可以使用assert来完成结果判断。

//leetcode08.h #include <string using std::string; class Solution08 { public: static int myAtoi(string str); }; //main #include "cassert" assert(Solution::myAtoi("123")== 123); assert(Solution08::myAtoi("123") == 123); assert(Solution08::myAtoi("-123") == -123); assert(Solution08::myAtoi(" -123 ") == -123); assert(Solution08::myAtoi(" 123 456 ") == 123);

把上面的测试用例都补上，然后再想想还有没有其它的场景。如果有的话，不要吝啬使用测试用例，越多越好。