LeetCode 解题思路：535.Encode and Decode TinyURL

╰半橙微兮° 2021-12-21 02:19 234阅读 0赞

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.

题意就是对url设计编码和解码，使长url变成短url。没有严格限制编解码算法，只要能保证长短url可以互相转换。

基本思路：

encode：根据url生成一个序号，将url用vector或unordered\_map保存在该序号对应项中，返回string为http://tinyurl.com/+序号

decode：从短网址中拿到序号，从容器中找到对应序号项。

简单的例子：用longUrl在vector中的存储位置做标识

1 class Solution {
     2 public:
     3 
     4     // 编码：长变短
     5     string encode(string longUrl) {
     6         url.push_back(longUrl);
     7         return "http://tinyurl.com/" + to_string(url.size() - 1);
     8     }
     9 
    10     // 解码：短变长
    11     string decode(string shortUrl) {
    12         size_t pos = shortUrl.find_last_of("/");
    13         return url[stoi(shortUrl.substr(pos + 1))];
    14     }
    15 private:
    16     vector<string> url;
    17 };

但是和题目给的不一样怎么办？有一个小方案，和解题无关，单纯说一下怎么去设计tinyurl，只有思路没有写代码。

基本思路不变，仍然保存在容器中，或者调用接口写在数据库/redis中。

编码：使用题目 “4e9iAk“ 这样的编码可以认为将URL换成一个 0 ~ 9 + ‘A’ ~‘Z’ + ‘a’ ~ ‘z’ 换成一个5位62进制的数，这样每个url保存一次, 总共可以保存62^5 =916132832 个不同的url，最后一位另有他用；

可以将url用哈希函数（自己写）变成一个整型数（<916132832），将网址保存在容器中这个整形数所对应的位置，并且将这个整型数变成一个62进制数；

最后一位默认为0，如果这个位置已经有了一个地址，就偏移62位，如果还被占用，将偏移62\*2个依次类推，用最后一位纪录到底偏移了几次；

如果偏移了很多次仍然没找到位置（那得已经保存了很多），判断下当前容器大小是否超过容器一半，如果是就扩容，如果否，就将原哈希值加在url后面再进行一次哈希计算，用新的哈希值保存这条url。

解码：按照编码规则反解成整型数，然后把容器/数据库中网址取出。

还有一个取巧的方法，分享给一些只求过的同学，当然也不是不好，因为题目没有具体的要求，可以accept。

class Solution {
    public:
        string encode(string longUrl) {
            return longUrl;
        }
        string decode(string shortUrl) {
            return shortUrl;
        }
    };

还有一种突发奇想的思路就是压缩算法，转化成二进制将相邻的0和1压缩在一起，比如00000000压缩为080，或者使用RLE（Run Length Encoding）替换重复的字。这种方法的好处就是不需要单独存储空间，所有的都是直接转化的，既符合要求速度也很快。坏处就是写起来代码量稍微有点大。

转载于:https://www.cnblogs.com/hellomotty/p/7291236.html