[LeetCode][C++] 用乾淨簡單的方式解 #8 String to Integer (atoi)

-

這題 Acceptance rate 是 LeetCode 前幾名最低的，只有 16% 左右，看似複雜但其實可以變成很簡單，只要我們把問題切成小塊來處理就好了。

何謂 Read In?

有沒有發現題目描述提到很多次 "Read in"?

其實每次 Read in 就是把一個 character 給吃掉的意思:


在 Parse 字串的時候有時候你會想要吃掉 character，有時候卻又不想吃掉。像是如果突然讀到一個數字字元 "4"，但這時候還在決定正負號怎麼辦?

那當然就是不要吃掉這個字元，留給負責處理數字的步驟去處理。

Easy As 123

既然題目描述都跟你說 1、2、3 步要做什麼了，我們可以就寫相對應的 functions 一個專心處理一件事就好。

第一步我們先看看要不要狂吃空白字元，認不得的東西就算了丟給第二步:


這邊如果你看到我標示的 "Read" 亮框就表示每走過一次箭頭就應該要把一個字元吃掉。

第二步我們來看看正負號，決定最後到底是正是負:


第三步我們就狂吃數字字元，直到沒辦法再吃為止:


如果看了這三張投影片，我們不管用什麼程式語言應該都可以寫出 code 來了。

如果我用 C++ 寫就會寫出像這樣的 code:

class Solution {
 public:
  int myAtoi(std::string s) {
    int index = 0;
    while (runStep1(s, index /*may change*/))
      ;
    while (runStep2(s, index /*may change*/))
      ;
    while (runStep3(s, index /*may change*/))
      ;
    if (!m_positive) m_result *= -1;
    return m_result;
  }

  bool runStep1(const std::string &s, int &index) {
    if (index >= s.size()) return false;
    if (s.at(index) == ' ') {
      index++;
      return true;  // continue
    } else {
      return false;
    }
  }

  bool runStep2(const std::string &s, int &index) {
    if (index >= s.size()) return false;
    if (s.at(index) == '-') {
      m_positive = false;
      index++;
    } else if (s.at(index) == '+') {
      m_positive = true;
      index++;
    } else {
      m_positive = true;
    }
    return false;
  }

  bool runStep3(const std::string &s, int &index) {
    if (index >= s.size()) return false;
    if (s.at(index) >= '0' && s.at(index) <= '9') {
      const int digit = s.at(index) - '0';
      m_result *= 10;
      m_result += digit;
      index++;
      return true;  // continue
    } else {
      return false;
    }
  }

  bool m_positive = false;
  int m_result = 0;
};
C++


是不是看了讓人覺得很清爽?

等等! 456 步呢?

沒錯，這題還有一個麻煩的東西我們還沒處理，就是他希望你要把數字限制在 int 能表示的範圍，不過這個借用一下 LeetCode #7 的解法就好了。

我們可以用一個 function 來 "安全地" 來算 a * 10 + x，overflow 的話就回傳 false:

bool safeMultiplyAndAdd(const int a, const int x, int &out) {
  // Does a * 10 + x > INT_MAX ?
  // (Step 1) Does a * 10 > INT_MAX ?
  if (a > INT_MAX / 10) return false;
  // (Step 2) Does a * 10 + x > INT_MAX ?
  if (a * 10 > INT_MAX - x) return false;

  out = a * 10 + x;
  return true;
}
C++


因為 a 和 x 都一定是非負的數字，所以我們可以省去很多其他一般乘法判斷 overflow/underflow 的條件式。

如果途中算到一半 overflow 的話我們不只要保護 int 不超出範圍，我們還要用一個 m_overflow member variable 像記仇一樣記住這件事，最後回傳結果的時候直接傳 INT_MAX 或 INT_MIN:

if (m_overflow) {
  return m_positive ? INT_MAX : INT_MIN;
} else {
  return m_positive ? m_result : (-m_result);
}
C++


一般來說如果 m_result 是 INT_MIN 的話加上負號其實是會超過 INT_MAX 會 overflow，不過我們只會 m_result * 10 + digit 而且 m_result 一開始是 0 所以 m_result 一定不是負的，自然就不用多去保護他。

所以最後的程式碼就會長這樣:

#include <climits>

class Solution {
 public:
  int myAtoi(std::string s) {
    int index = 0;
    while (runStep1(s, index /*may change*/))
      ;
    while (runStep2(s, index /*may change*/))
      ;
    while (runStep3(s, index /*may change*/))
      ;
    if (m_overflow) {
      return m_positive ? INT_MAX : INT_MIN;
    } else {
      return m_positive ? m_result : (-m_result);
    }
  }

  bool runStep1(const std::string &s, int &index) {
    if (index >= s.size()) return false;
    if (s.at(index) == ' ') {
      index++;
      return true;  // continue
    } else {
      return false;
    }
  }

  bool runStep2(const std::string &s, int &index) {
    if (index >= s.size()) return false;
    if (s.at(index) == '-') {
      m_positive = false;
      index++;
    } else if (s.at(index) == '+') {
      m_positive = true;
      index++;
    } else {
      m_positive = true;
    }
    return false;
  }

  bool runStep3(const std::string &s, int &index) {
    if (index >= s.size()) return false;
    if (s.at(index) >= '0' && s.at(index) <= '9') {
      const int digit = s.at(index) - '0';
      if (!safeMultiplyAndAdd(m_result, digit, m_result /*out*/))
        m_overflow = true;
      index++;
      return true;  // continue
    } else {
      return false;
    }
  }

  bool safeMultiplyAndAdd(const int a, const int x, int &out) {
    // Does a * 10 + x > INT_MAX ?
    // (Step 1) Does a * 10 > INT_MAX ?
    if (a > INT_MAX / 10) return false;
    // (Step 2) Does a * 10 + x > INT_MAX ?
    if (a * 10 > INT_MAX - x) return false;

    out = a * 10 + x;
    return true;
  }

  bool m_positive = false;
  bool m_overflow = false;
  int m_result = 0;
};
C++


結語

Submit 完會得到又快又省記憶體的結果:


這和上一題的原因差不多，因為我們沒有用一些 string 或 long 來判斷 overflow，也沒有用太複雜的方式來解題，所以得到這結果是滿合理的。

其實上面 Steps 1-3 如果我們把那些圖合起來會得到類似 state machine 的圖，像是有人這樣解、或是這樣子。如果我們去看 JSON 官網也會看到類似的圖，其實都是在做類似的事情。我們甚至可以用比較專業的 DFA 或 NFA 去表示，不過用一大堆專業術語可不是我的目標。

GitHub

Code 和投影片我都放在 GitHub 上了，有興趣的歡迎參考。

留言

發佈留言

此網誌的熱門文章

[試算表] 追蹤台股 Google Spreadsheet (未實現損益/已實現損益)

-
圖片
在 Dcard 上發了一篇文結果引起超多網友回應想要看試算表，我就來整理一下我追蹤台股用的 Google 試算表給大家。 這個試算表我目標是以 "簡單" 為主，底下我也會講解公式的運作原理，希望大家能以此試算表輕鬆擴充自己想要的功能。 功能 未實現損益 (Unrealized Gain/Loss 表) 不管同一支股票是不是有部分已經賣出，只要你還持有未賣出的股票這邊都看的到。 已實現損益 (Realized Profit/Loss 表) 我過去的績效如何? 在這個表一目了然。 未實現損益: 詳細資料 (Unrealized Stats 表) 我還持有多少股? 每股市值多少? 每股的成本是多少? 在這個表可以快速追蹤。 手機友善 (Mobile Friendly) 我為了在手機上也可以快速看我想看的資訊，把 "Unrealized Gain/Loss" 做成比較窄的版型。 只要下載 Google Sheets app 打開試算表就可以了。 Google Spreadsheet 連結 Google Drive 連結 Stock Tracking 使用方式 請先點 "檔案" -> "建立副本"，copy 一份試算表到你自己的 Google Drive 將 "Current Price" 表單中填上你想要追蹤的股票代號和名稱 將 "Transactions" 表單中刪除範例資料，但請務必留下第 2 列 (因為有公式)，然後慢慢往下填入你的資料 Step 1: 檔案 -> 建立副本 Step 2: 新增/刪除股票代號和名稱 (紅框圈起處)，灰色底欄位代表有公式 Step 3: 在 "Transactions" 表填入資料到白色底欄位 (紅框圈起處)，灰色底欄位代表要讓公式自動計算 未實現損益的正確算法 其實在發 Dcard 文之前我自己也像 另外一個表單 犯了同樣的錯誤，就是只有在股票全部賣光光 (持有 0 股) 後計算的未實現損益才會正確。還沒全部賣光怎麼辦? 難道就不顯示了嗎? 飲料的例子 只要股票中途賣出一部分，目前還持有部分股票的話，感覺計算就突然變得很複雜。但不用怕，我們來用飲料當作股票舉個超簡單的例子 (1 杯=1...
閱讀更多

[Side Project] 互動式教學神經網路反向傳播 Interactive Computational Graph

-
圖片
成品 互動式網頁連結:  Interactive Computational Graph 微積分課經典的範例 df/dx sin(x) / x: 2 個 inputs, 1 個 output, 沒有 hidden layer 的 fully connected neural network: 為何要做這套工具 以前在學 machine learning 的時候覺得最難理解的部分就是 backpropagation，也就是神經網路到底是怎麼用數學來做訓練的。 我們知道神經網路就是長這樣子: Source: Wikipedia 但實際上每個 neuron (圓圈圈) 裡面有許多基本的數學運算，像是 sum 還有 activation function: Source:  Neural Networks and Machine Learning 當我們把所有東西綜合在一起，腦袋就會打結，到底 chain rule 是怎麼在這麼複雜的神經網路之間套用的? 就算了解基礎也很難相信實際上到底怎麼運作的。我又沒有要真的使用的話，網路上的教學就覺得看看就好 Source:  A Step by Step Backpropagation Example 但決心要了解 backpropagation 細節之後，不少教學都提到了 computational graph，從基礎的數學運算當作 nodes 來去理解似乎是比較簡單的方式。 後來找到了這篇文章  Calculus on Computational Graphs: Backpropagation  把 chain rule 講解的簡單至極，於是就在想，為何我不做一個網頁，讓大家可以自由地組合想要的 graph，然後看一下 chain rule 是怎麼流通的。 失敗作經驗 在做這次 side project 前，其實早在一年前我就開始作另一個 side project 是想展現神經網路的訓練過程。名稱叫做 explain-derivatives，是被 TensorFlow 的一個網頁 A Neural Network Playground 啟發的。 但由於一開始欠缺規劃，想到什麼就加什麼功能進去，造成架構一直修改，最後由於程式碼架構太過複雜就放棄了。 這個 project 是用 Cy...
閱讀更多

[插件] 在 Chrome 網頁做區分大小寫的搜尋

-
圖片
寫軟體的時候最常用到的功能就是上網查 API 文件，但是常常會遇到一個困擾就是，搜尋的文字在 Chrome 裡面是不區分大小寫 (case-insensitive) 的。有的時候是還好，多按一些 F3 就找到了，可是有時候實在是太多大小寫的東西混在一起，這時候我們有一些快速的解法: 用 Firefox 搜尋 (Firefox 的搜尋框裡面預設就提供有 match case 的功能了) 開 DevTools 按 Ctrl + Shift + F 進行全部東西的搜尋 (不過大概會發瘋) 用插件的解法算是意外發現的，原本只是在找有沒有可以用 regex 搜尋的插件，沒想到意外發現  regex 的插件也是可以拿來做區分大小寫 (case-sensitive) 的一般搜尋。 用 Chrome Regex Search 來做區分大小寫的搜尋 先裝好 Chrome Regex Search 之後，按 Ctrl + Shift + F 或是點工具列的圖示，打上想找的文字就可以了。 例如我最近在看 Qt QTextCursor 的文件，但是我只想找 "cursor"，很不幸的如果用 Chrome 預設搜尋他會把一大堆 QText Cursor 也會找到: 如果用 Chrome Regex Search 就會侷限在小寫的 "cursor": 用 Regex 的陷阱 如果你不知道 regex 是什麼，那你很有可能會發現在搜尋一些含特殊符號的東西會搜尋到怪怪的東西，不然就是搜尋會失敗。 這是因為 regex 本來就是偏工程師在用的東西，有一些符號是有特殊涵意的，所以如果搜尋的字包含以下任何特殊符號記得要在前面加一個反斜線 \ ( ref ): . + * ? ^ $ ( ) [ ] { } | \ 例如我想搜尋 1+1=(2-1)+1*1 ，那其實要打 1\+1=\(2-1\)\+1\*1  才會正確找的到。 是不是很麻煩? 不過如果你要找的東西有特殊符號的話，其實用一般 Chrome 的搜尋通常是不會有太多搜尋結果的，那就用一般搜尋就好。 Chrome 什麼時候要支援大小寫搜尋? 其實上面弄了那麼麻煩，還不如開個 Firefox 搜尋更快。那我就滿好奇，這麼基本的功能怎麼 Chrome 一直都沒做? 找了一下才發現 Super User 有人...
閱讀更多