程序員面試題精選100題(17)-把字符串轉換成整數[算法]

時間:2019-09-22 編輯:范文亭
題目:輸入一個表示整數的字符串,把該字符串轉換成整數并輸出。例如輸入字符串"345",則輸出整數345。分析:這道題盡管不是很難,學過C/C++語言一般都能實現基本功能,但不同程序員就這道題寫出的代碼有很大區別,可以說這道題能夠很好地反應出程序員的思維和編程習慣,因此已經被包括微軟在內的多家公司用作面試題。建議讀者在往下看之前自己先編寫代碼,再比較自己寫的代碼和下面的參考代碼有哪些不同。
首先我們分析如何完成基本功能,即如何把表示整數的字符串正確地轉換成整數。還是以"345"作為例子。當我們掃描到字符串的第一個字符'3'時,我們不知道后面還有多少位,僅僅知道這是第一位,因此此時得到的數字是3。當掃描到第二個數字'4'時,此時我們已經知道前面已經一個3了,再在后面加上一個數字4,那前面的3相當于30,因此得到的數字是3*10+4=34。接著我們又掃描到字符'5',我們已經知道了'5'的前面已經有了34,由于后面要加上一個5,前面的34就相當于340了,因此得到的數字就是34*10+5=345。
分析到這里,我們不能得出一個轉換的思路:每掃描到一個字符,我們把在之前得到的數字乘以10再加上當前字符表示的數字。這個思路用循環不難實現。
由于整數可能不僅僅之含有數字,還有可能以'+'或者'-'開頭,表示整數的正負。因此我們需要把這個字符串的第一個字符做特殊處理。如果第一個字符是'+'號,則不需要做任何操作;如果第一個字符是'-'號,則表明這個整數是個負數,在最后的時候我們要把得到的數值變成負數。
接著我們試著處理非法輸入。由于輸入的是指針,在使用指針之前,我們要做的第一件是判斷這個指針是不是為空。如果試著去訪問空指針,將不可避免地導致程序崩潰。另外,輸入的字符串中可能含有不是數字的字符。每當碰到這些非法的字符,我們就沒有必要再繼續轉換。最后一個需要考慮的問題是溢出問題。由于輸入的數字是以字符串的形式輸入,因此有可能輸入一個很大的數字轉換之后會超過能夠表示的最大的整數而溢出。
現在已經分析的差不多了,開始考慮編寫代碼。首先我們考慮如何聲明這個函數。由于是把字符串轉換成整數,很自然我們想到:
int StrToInt(const char* str);
這樣聲明看起來沒有問題。但當輸入的字符串是一個空指針或者含有非法的字符時,應該返回什么值呢?0怎么樣?那怎么區分非法輸入和字符串本身就是”0”這兩種情況呢?
接下來我們考慮另外一種思路。我們可以返回一個布爾值來指示輸入是否有效,而把轉換后的整數放到參數列表中以引用或者指針的形式傳入。于是我們就可以聲明如下:
bool StrToInt(const char *str, int& num);
這種思路解決了前面的問題。但是這個函數的用戶使用這個函數的時候會覺得不是很方便,因為他不能直接把得到的整數賦值給其他整形變量,顯得不夠直觀。
前面的第一種聲明就很直觀。如何在保證直觀的前提下當碰到非法輸入的時候通知用戶呢?一種解決方案就是定義一個全局變量,每當碰到非法輸入的時候,就標記該全局變量。用戶在調用這個函數之后,就可以檢驗該全局變量來判斷轉換是不是成功。
下面我們寫出完整的實現代碼。參考代碼:
enum Status {kValid = 0, kInvalid};
int g_nStatus = kValid;

///////////////////////////////////////////////////////////////////////
// Convert a string into an integer
///////////////////////////////////////////////////////////////////////
int StrToInt(const char* str)
{
      g_nStatus = kInvalid;
      long long num = 0;

      if(str != NULL)
      {
            const char* digit = str;

            // the first char in the string maybe '+' or '-'
            bool minus = false;
            if(*digit == '+')
                  digit ++;
            else if(*digit == '-')
            {
                  digit ++;
                  minus = true;
            }

            // the remaining chars in the string
            while(*digit != '\0')
            {
                  if(*digit >= '0' && *digit <= '9')
                  {
                        num = num * 10 + (*digit - '0');

                        // overflow  
                        if(num > std::numeric_limits<int>::max())
                        {
                              num = 0;
                              break;
                        }

                        digit ++;
                  }
                  // if the char is not a digit, invalid input
                  else
                  {
                        num = 0;
                        break;
                  }
            }

            if(*digit == '\0')
            {
                  g_nStatus = kValid;
                  if(minus)
                        num = 0 - num;
            }
      }

      return static_cast<int>(num);
}

討論:在參考代碼中,我選用的是第一種聲明方式。不過在面試時,我們可以選用任意一種聲明方式進行實現。但當面試官問我們選擇的理由時,我們要對兩者的優缺點進行評價。第一種聲明方式對用戶而言非常直觀,但使用了全局變量,不夠優雅;而第二種思路是用返回值來表明輸入是否合法,在很多API中都用這種方法,但該方法聲明的函數使用起來不夠直觀。
最后值得一提的是,在C語言提供的庫函數中,函數atoi能夠把字符串轉換整數。它的聲明是int atoi(const char *str)。該函數就是用一個全局變量來標志輸入是否合法的。
本文已影響
相關文章
大亨pk10计划苹果版