#LeetCode OJ#273.Integer to Engl

最近发现一个很好的网站叫做LeetCodeOJ，注册一个账号之后就可以在上面刷题，进一步加深对语言的熟悉。多造点轮子什么的。网址：https://leetcode.com/
这是我今晚在上面写的一道题。（其实还写了一道50.pow(x,n)，求次方的，不过代码太难看了，为了提高运行效率也参考了别人的做法，是在位运算的基础上用了分治策略）
下面这道题目是273.Integer to English Words，先PIA一下这道题的题干

题干.png

这道题目要求我们输入一个int然后转化为字符串，题目原理很简单，不过写出来挺麻烦的。我自己是用了一种运行效率很低的写法。（12ms）

rank.png

运行效率只超过了9.47%，倒数了=-=，的确挺差的，有时间一定找个更好一点的算法把这东西的效率给提高了。
我的思路是：
举个例子，对于2,147,483,647 拆分成2 147 483 647四个部分

输出.png

可以发现规律是每隔10^3会有一段0~999的数字(如上述中的 002 147 483 647)，然后002 147 483 647后面接上thousand million billion这些，所以我定义了一个dealWithHundred函数来输出0~999的字符串，在numberToWords中加入thousand million billion最后输出完整字符串。

dealWithHundred函数

string s;
        int units = num % 10;//个位
        int decade0 = num % 100;//含个位的十位数
        int decade = decade0 - units;//十位数
        int hundred = (num - decade0)/100;//百位的数字
        if (num > 100 && decade0>=20)
        {
            s = a[hundred] + " " + a[100] + " " + a[decade] + " " + a[units];
        }
        else if (num >= 100)
        {
            s = a[hundred] + " " + a[100] + " " + a[decade0];
        }
        else if (num >= 20)
        {
            s = a[decade] + " " + a[units];
        }
        else
        {
            s = a[decade0];
        }
        if (s[s.length() - 1] == ' '&&s.length()!=0)//最后一位为空，则删除
        {
            s = s.substr(0, s.length() - 1);
        }
        return s;

考虑数字120到有可能在最后的个位为0 且map中a[0]="",会使得最后多一个空格，所以用s = s.substr(0, s.length() - 1)这条表达式去删除那个空格。
PS.在这个地方编译器会出现assert，毕竟这样不大安全，不过是string所以还是没有大的问题，程序照样运行的下去

以下是完整代码

#include<iostream>
#include<map>
#include<string>
using namespace std;
class Solution {
public:
    Solution();
    ~Solution();
    string numberToWords(int num);
    string dealWithHundred(int num);
private:
    map<int, string> a;//定义一个Map，让键值和string对应
    int counter;
    string str, moredigit[4];
};
Solution::Solution()
{
    str = "";
    counter = 0;
    moredigit[0] = "";
    moredigit[1] = "Thousand";
    moredigit[2] = "Million";
    moredigit[3] = "Billion";
    a.insert(pair<int, string>(0, ""));
    a.insert(pair<int, string>(1, "One"));
    a.insert(pair<int, string>(2, "Two"));
    a.insert(pair<int, string>(3, "Three"));
    a.insert(pair<int, string>(4, "Four"));
    a.insert(pair<int, string>(5, "Five"));
    a.insert(pair<int, string>(6, "Six"));
    a.insert(pair<int, string>(7, "Seven"));
    a.insert(pair<int, string>(8, "Eight"));
    a.insert(pair<int, string>(9, "Nine"));
    a.insert(pair<int, string>(10, "Ten"));
    a.insert(pair<int, string>(11, "Eleven"));
    a.insert(pair<int, string>(12, "Twelve"));
    a.insert(pair<int, string>(13, "Thirteen"));
    a.insert(pair<int, string>(14, "Fourteen"));
    a.insert(pair<int, string>(15, "Fifteen"));
    a.insert(pair<int, string>(16, "Sixteen"));
    a.insert(pair<int, string>(17, "Seventeen"));
    a.insert(pair<int, string>(18, "Eighteen"));
    a.insert(pair<int, string>(19, "Nineteen"));
    a.insert(pair<int, string>(20, "Twenty"));
    a.insert(pair<int, string>(30, "Thirty"));
    a.insert(pair<int, string>(40, "Forty"));
    a.insert(pair<int, string>(50, "Fifty"));
    a.insert(pair<int, string>(60, "Sixty"));
    a.insert(pair<int, string>(70, "Seventy"));
    a.insert(pair<int, string>(80, "Eighty"));
    a.insert(pair<int, string>(90, "Ninety"));
    a.insert(pair<int, string>(100, "Hundred"));
}
Solution::~Solution(){}
string Solution::numberToWords(int num)
{
    if (num == 0) { return "Zero"; }
    int thousand = num % 1000;
    str = dealWithHundred(thousand);
    num = (num - num % 1000) / 1000;
    string str0;
    while (num > 0)
    {
        thousand = num % 1000;
        str0 = dealWithHundred(thousand);
        counter++;
        if (thousand != 0)
        {
            str = str0 + " " + moredigit[counter] + " " + str;
            if (str[str.length() - 1] == ' '&&str.length() != 0)
            {
                str = str.substr(0, str.length() - 1);
            }
        }
        num = (num - num % 1000) / 1000;
    }
    return str;
}
string Solution::dealWithHundred(int num)
{
    string s;
    int units = num % 10;//个位
    int decade0 = num % 100;//含个位的十位数
    int decade = decade0 - units;//十位数
    int hundred = (num - decade0) / 100;//百位的数字
    if (num > 100 && decade0 >= 20)
    {
        s = a[hundred] + " " + a[100] + " " + a[decade] + " " + a[units];
    }
    else if (num >= 100)
    {
        s = a[hundred] + " " + a[100] + " " + a[decade0];
    }
    else if (num >= 20)
    {
        s = a[decade] + " " + a[units];
    }
    else
    {
        s = a[decade0];
    }
    if (s[s.length() - 1] == ' '&&s.length() != 0)//最后一位为空，则删除
    {
        s = s.substr(0, s.length() - 1);
    }
    return s;
}
int main()
{
    Solution a;
    int num;
    cin >> num;
    cout << a.numberToWords(num);
}

C++STL里面的东西在内存中都比较安全，析构函数我也就没有写了（其实是还没研究）

感想：最近在学Python，这一个国庆C++没怎么看，一刷C++的题就发现了要用map，这个map我之前也只是略知一二。但是最近学Python后对于迭代器和dict类型有了一定的理解，所以我很快就大概知道了map是怎么一回事，对于学习还是很有用的，编程语言都也是互通的。

最近还因为学了Python里面的lambda表达式，所以我还特意去看了一下C++的lambda表达式，lambda表达式也是一个很有用的东西，可以大大简化代码。

所以其实觉得C++的确是博大精深，而且不同的语言之间互通真的特别多，还是应该要继续学习，掌握那种思想。