LeetCode 535:编解码TinyURL

Question

我正在为LeetCode的“编码和解码TinyURL”发布一个解决方案。如果你想复习，请看。谢谢!

问题

TinyURL是一个URL缩短服务，您可以在其中输入一个URL (如https://leetcode.com/problems/design-tinyurl )，它返回一个短URL (如http://tinyurl.com/4e9iAk )。

为encode服务设计TinyURL和decode方法。对于编码/解码算法的工作方式没有任何限制。您只需要确保URL可以被编码成一个微小的URL，并且这个微小的URL可以被解码到原始的URL。

码

// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();

// Most of headers are already included;
// Can be removed;
#include <iostream>
#include <cstdint>
#include <string>
#include <unordered_map>
#include <utility>
#include <random>

static const struct Solution {
    public:
        const std::string encode(
            const std::string long_url
        ) {
            std::string tiny_encoded;

            if (!encoded_url.count(long_url)) {
                for (auto index = 0; index < kTinySize; ++index) {
                    tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
                }

                encoded_url.insert(std::pair<std::string, std::string>(long_url, tiny_encoded));
                decoded_url.insert(std::pair<std::string, std::string>(tiny_encoded, long_url));

            } else {
                tiny_encoded = encoded_url[long_url];
            }

            return kDomain + tiny_encoded;
        }

        const std::string decode(
            const std::string short_url
        ) {

            return std::size(short_url) != kDomainTinySize ||
                   !decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
                   decoded_url[short_url.substr(kDomainSize, kTinySize)];
        }

    private:
        static constexpr char kDomain[] = "http://tinyurl.com/";
        static constexpr unsigned int kTinySize = 6;
        static constexpr unsigned int kDomainSize = std::size(kDomain) - 1;
        static constexpr auto kDomainTinySize = kDomainSize + kTinySize;
        static constexpr char char_pool[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        std::unordered_map<std::string, std::string> encoded_url;
        std::unordered_map<std::string, std::string> decoded_url;
        std::random_device rand_generator;
};

// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));

Answer 1

你正在做两次查找。

            if (!encoded_url.count(long_url)) {

                .. stuff

            } else {
                tiny_encoded = encoded_url[long_url];
            }

我知道它是用于查找的O(1)。但这里面有一个真正的常数。如果你可以的话，尽量避免。

使用find()。那么，如果它在那里，你可以简单地使用它。

            auto find = encoded_url.find(long_url);
            if (find == encoded_url.end()) {

                .. stuff

            } else {
                tiny_encoded = find->second;
            }

这是伟大的，如果你想要随机的URL是很难猜测的。

                for (auto index = 0; index < kTinySize; ++index) {
                    tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
                }

但这是谜题的要求吗。看起来(不确定产生随机数的代价有多大)这样的方式产生一个名字是非常昂贵的。

也有可能发生冲突。如果使用的是随机生成的值，则在末尾附加时间戳以避免冲突。

就我个人而言，我不喜欢指定类型。但是，如果要这样做，请使用方法的类型，而不是特定的类型：

    encoded_url.insert(std::pair<std::string, std::string>(long_url, tiny_encoded));


    // Top of the class.
    using Map      = std::unordered_map<std::string, std::string>;
    using MapValue = Map::value_type;

    // In the code.
    encoded_url.insert(MapValue(long_url, tiny_encoded));

但我想我会简单地使用emplace()。

    encoded_url.emplace(long_url, tiny_encoded);

Answer 2

我同意马丁约克回答的每一件事。只有一件事:如果你不创建一个纯粹随机的网址，而是通过散列原始网址来创建一个，你可以避免拥有两个unordered_maps。这样，您将始终为相同的长URL创建相同的小URL，因此您不再需要encoded_url了。当然，您仍然需要处理以某种方式中的副本。

Answer 3

其他人说得很好，但我要加上一个文体上的小测验。

return std::size(short_url) != kDomainTinySize ||
       !decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
       decoded_url[short_url.substr(kDomainSize, kTinySize)];

是一条该死的单线船。三元操作符很有趣，但作为一个绝对滥用它的人来说，如果你不能让它舒适地放在一两行线上，那么当你在6个月后回去读它时，你会恨自己的。此外，当你看到许多!s四处奔走时，通常是打破德摩根定律的时候了。这会让我们把这条无趣的路远远地抛在视线之外。所以，如果我们真的想要三元..。

return std::size(short_url) == kDomainTinySize &&
       decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ?
       decoded_url[short_url.substr(kDomainSize, kTinySize)] :
       "";

或者如果我觉得有点大胆，也许甚至

return std::size(short_url) == kDomainTinySize 
       && decoded_url.count(short_url.substr(kDomainSize, kTinySize))
       ? decoded_url[short_url.substr(kDomainSize, kTinySize)]
       : "";

我撒谎了，第二点:我认为惯用的C++也应该尽可能少地依赖于隐式类型转换，也就是说，将该条件更改为decoded_url.count(...) != 0。这是更详细，但它也立即更清楚的读者是什么意思。不过，理智的人可能会不同意。