已知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