LeetCode Encode and Decode TinyURL

Note: This is a companion problem to the System Design problem: Design TinyURL.

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk. Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

---

实现短网址的功能，即把一个长的网址加密成短网址，并且能够把短网址还原为原来的长网址。 显然要用Hash，有多种方法，参考：https://leetcode.com/articles/encode-and-decode-tinyurl/ 直接用一个计数器当key，相当于自己维护了一个长的url池，给每个url编了一个号。加密的时候把号码给他，解密的时候根据编号找到原始的url。代码如下： [cpp] class Solution { private: unsigned long long m_ullCnt; unordered_map<unsigned long long, string> m_umHash; public: Solution() :m_ullCnt(0) {}; // Encodes a URL to a shortened URL. string encode(string longUrl) { m_umHash[m_ullCnt] = longUrl; return "http://tinyurl.com/" + to_string(m_ullCnt++); } // Decodes a shortened URL to its original URL. string decode(string shortUrl) { int id = atoi(shortUrl.substr(19).c_str()); return m_umHash[id]; } }; [/cpp] 本代码提交AC，用时9MS。 既然可以用计数器，也可以生成不重复的随机数作为key，不断random，和上面的解法类似。 还有一种生成key的方法，就是用STL自带的hash函数，把string hash成一个size_t作为key。注意要从短url中还原回hash值时，不能用atoi和atol，因为size_t可能是unsigned int，也可能和平台有关，所以必须用sscanf “%zu”的形式转换成size_t。 代码如下： [cpp] class Solution { private: unordered_map<size_t, string> m_umHash; public: // Encodes a URL to a shortened URL. string encode(string longUrl) { hash<string> h; m_umHash[h(longUrl)] = longUrl; return "http://tinyurl.com/" + to_string(h(longUrl)); } // Decodes a shortened URL to its original URL. string decode(string shortUrl) { size_t id = 0; sscanf(shortUrl.substr(19).c_str(), "%zu", &id); return m_umHash[id]; } }; [/cpp] 本代码提交AC，用时6MS。]]>