西山居笔试题：求字符的Unicode编码

已知utf8的编码规则，求将unicode转换成utf8编码

具体转换规则见代码中注释

#include <stack>
#include <vector>
#include <iostream>

using namespace std;


class Solution {
public:
    string to_bin(int val) {
        string ar;
        while(val) {
            ar.push_back(val % 2 + '0');
            val >>= 1;
        }

        for(auto beg=ar.begin(), end=--ar.end(); beg < end; ++beg, --end) {
            char ch = *beg;
            *beg = *end;
            *end = ch;
        }
        return ar;
    }

    int to_value(const string &str) {
        int ret = 0;
        int tmp = 1;
        for(auto beg=str.rbegin(), end=str.rend(); beg!=end; ++beg) {
            ret += (*beg - '0') * tmp;
            tmp *= 2;
        }
        return ret;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 把一个Unicode 字符用Utf-8的编码方式表达出来，Utf-8编码的规则如下
    1 char: 0xxxxxxx                                    7-bits    [0, 127]
    2 char: 110xxxxx 10xxxxxx                           11-bits   [128, 2047]
    3 char: 1110xxxx 10xxxxxx 10xxxxxx                  16-bits   [2048, 65535]
    4 char: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx         21-bits   [65536, 0x10FFFF]

当unicode编码范围在0到127之间的时候，用utf-8编码以后占用一个字节，字节最高bit为0
当unicode编码范围在128到2047之间的时候，用utf-8编码以后占用两个字节，第一个字节高三位为 110，第二个字节高两位为10，其余bit用来编码
其它依上表类推

编码后的返回值通过一个std::vector的容器返回
     * @param codepoint int整型 unicode 字符码
     * @return int整型vector
     */
    vector<int> EncodeUtf8(int codepoint) {
        // write code here
        vector<int> ret;
        string bin = to_bin(codepoint);
        if(codepoint < 128) {
            ret.push_back(codepoint);
        }else if(codepoint < 2048) {
            bin = string(11-bin.size(), '0') + bin;
            int a1 = to_value(string("110") + bin.substr(0, 5));
            int a2 = to_value(string("10")  + bin.substr(5));
            ret.push_back(a1);
            ret.push_back(a2);
        }else if(codepoint < 65536) {
            bin = string(16-bin.size(), '0') + bin;
            int a1 = to_value(string("1110") + bin.substr(0, 4));
            int a2 = to_value(string("10")  + bin.substr(4, 6));
            int a3 = to_value(string("10") + bin.substr(10));
            ret.push_back(a1);
            ret.push_back(a2);
            ret.push_back(a3);
        }else {
            bin = string(21-bin.size(), '0') + bin;
            int a1 = to_value(string("1110") + bin.substr(0, 3));
            int a2 = to_value(string("10")  + bin.substr(3, 6));
            int a3 = to_value(string("10") + bin.substr(9, 6));
            int a4 = to_value(string("10") + bin.substr(15));
            ret.push_back(a1);
            ret.push_back(a2);
            ret.push_back(a3);
            ret.push_back(a4);
        }

        return ret;
    }
};


int main()
{
    int val = 12345;
//    auto bin = Solution().to_bin(val);
//    auto restore = Solution().to_value(bin);
//    cout << bin << " '" << restore << endl;
    auto res = Solution().EncodeUtf8(val);
    for(int i : res)
        cout << i << " ";
    cout << endl;

}

第二题：求大数的乘法

给定两个十进制字符串a，b，求a*b的字符串结果。
没写完，说一下思路吧：
拆分成三个代码块，第一个函数是
string solution(string a, string b);
第二个函数是：
string signle_plus(string val, char ch); // 用于单个数字与字符串相乘

第三个函数是：
string single_add(string a, string b); // 用于两个大数相乘

solution里调用signle_plus并维护一个结果vector<string> result;
然后对该结果
string ret = result[0];
for(int i=1; i<result.size(); ++i) {
ret = single_add(ret, result[i]);
}
return ret;</string>

当然，更好的方法是用俩for循环对result进行倒叙遍历，最后得到最终结果，复杂度是n^2 / 2