leetcode：无此题

题目

将中文数字转换为阿拉伯数字（详见《算法的乐趣》一书的 4.3 节）

示例：

  1. 输入："十五"
  2. 输出：15
  1. 输入："八百七十三亿九千零六十万五百八十七"
  2. 输出：87390600587
  1. 输入："两万零一十"
  2. 输出：20010

解答 & 代码

中文数字以万为小节，**"亿"**、**"万"** 是节权位，**"十"**、**"百"**、**"千"** 是普通权位
遍历中文数字：

  • 如果当前是节权位，则需要将当前节的整体数值 secVal 乘上节权位对应的量级，加到 result
  • 如果当前是普通权位，则只需要将当前数值 curVal 乘上对应的权位，加到 secVal
  • 如果当前是数字，则转换为数字，赋值给 curVal ```cpp

    include

    include

    include

    include

    using namespace std;

const int CHAR_LENGTH = 2; // GBK 编码一个中文字符占 2 个字节, 如果是 UTF-8 编码则一个中文字符占 3 个字节

long long ChineseToNumber(string chineseStr) { unordered_map weightValMap = { // 权位和量级（10 的 倍数）的对应关系 {“十”, 10}, {“百”, 100}, {“千”, 1000}, {“万”, 1e4}, {“亿”, 1e8} }; unordered_map numValMap = { // 普通数字和阿拉伯数字的对应关系 {“零”, 0}, {“一”, 1}, {“二”, 2}, {“两”, 2}, {“三”, 3}, {“四”, 4}, // 注意 “两” {“五”, 5}, {“六”, 6}, {“七”, 7}, {“八”, 8}, {“九”, 9} };

  1. long long result = 0;    // 结果，中文数字转换后的阿拉伯数字
  2. long long secVal = 0;    // 当前小节（以万为一个小节）的数值，即节权位之前的数值
  3. long long curVal = 0;    // 当前的数值，即普通权位之前的数值
  4. for(int i = 0; i < chineseStr.size(); i += CHAR_LENGTH)
  5. {
  6.     string ch = chineseStr.substr(i, CHAR_LENGTH);        // 当前的汉字
  7.     // 如果当前汉字为权位
  8.     if(weightValMap.find(ch) != weightValMap.end())
  9.     {
  10.         if(ch == "万" || ch == "亿")    // 如果是节权位：需要将当前节的整体数值 secVal 乘上节权位对应的量级，加到 result
  11.         {
  12.             secVal += curVal;
  13.             result += secVal * weightValMap[ch];
  14.             secVal = 0;
  15.         }
  16.         else                        // 如果是普通权位：需要将当前数值 curVal 乘上对应的权位，加到 secVal
  17.         {
  18.             curVal = curVal == 0 ? 1 : curVal;        // 注意特殊情况：如果 curVal == 0 要设为 1，不然如果输入"十五"，输出是 5 而不是 15
  19.             secVal += curVal * weightValMap[ch];
  20.         }
  21.         curVal = 0;
  22.     }
  23.     // 当前汉字为普通数字，转换为数字
  24.     else if(numValMap.find(ch) != numValMap.end())
  25.         curVal = numValMap[ch];
  26. }
  27. // 最后加上最后一小节的值
  28. result += secVal + curVal;
  29. return result;

}

struct TEST_DATA { string chineseStr; long long number; };

int main() { vector testPairList = { {“十五”, 15}, {“一十五”, 15}, {“八百七十三亿九千零六十万五百八十七”, 87390600587}, {“零”, 0}, {“一”, 1}, {“二”, 2}, {“三”, 3}, {“四”, 4}, {“五”, 5}, {“六”, 6}, {“七”, 7}, {“八”, 8}, {“九”, 9}, {“十”, 10}, {“一十”, 10}, {“一十一”, 11}, {“一百一十”, 110}, {“一百一十一”, 111}, {“一百”, 100}, {“一百零二”, 102}, {“一千零二十”, 1020}, {“一千零一”, 1001}, {“一千零一十五”, 1015}, {“一千”, 1000}, {“一万”, 10000}, {“两万零一十”, 20010}, {“两万零一”, 20001}, {“十万”, 100000}, {“一十万”, 100000}, {“一百万”, 1000000}, {“一千万”, 10000000}, {“一亿”, 100000000}, {“一十亿”, 1000000000}, {“十亿”, 1000000000}, {“一十亿一千”, 1000001000}, {“十亿一千”, 1000001000}, {“一十亿一百”, 1000000100}, {“十亿一百”, 1000000100}, {“二十万零一十”, 200010}, {“二十万零十”, 200010}, {“二百万零一百零五”, 2000105}, {“二千万一千零七”, 20001007}, {“二十亿零一十万零一百九十”, 2000100190}, {“一十亿四千零一万”, 1040010000}, {“二十亿零十万零一百九十”, 2000100190}, {“十亿四千零一万”, 1040010000}, {“二亿零一万二千三百零一”, 200012301}, {“二十亿零五百零一万零一十”, 2005010010}, {“二十亿零五百零一万零十”, 2005010010}, {“四十亿零九百零六万零二百”, 4009060200}, {“四十二亿九千四百九十六万七千二百九十五”, 4294967295} };

  1. for(int i = 0; i < testPairList.size(); ++i)
  2. {
  3.     string chineseStr = testPairList[i].chineseStr;
  4.     long long targetNum = testPairList[i].number;
  5.     long long result = ChineseToNumber(chineseStr);
  6.     if(result != targetNum)
  7.         cout << chineseStr << ", " << targetNum << ", " << result << endl;
  8. }
  9. cout << "finished..." << endl;
  10. return 0;

}

``` 复杂度分析：设字符串长为 n

  • 时间复杂度 O(n)：
  • 空间复杂度 O(1)：