LeetCode 535: เข้ารหัสและถอดรหัส TinyURL

Question

ฉันกำลังโพสต์วิธีแก้ปัญหาสำหรับ "เข้ารหัสและถอดรหัส TinyURL" ของ LeetCode หากคุณต้องการตรวจสอบโปรดดำเนินการ ขอบคุณ!

ปัญหา

TinyURL เป็นบริการย่อ URL ที่คุณป้อน URL https://leetcode.com/problems/design-tinyurlและส่งคืน URL แบบสั้นเช่นhttp://tinyurl.com/4e9iAk.

ออกแบบencodeและdecodeวิธีการสำหรับบริการ TinyURL ไม่มีข้อ จำกัด ว่าอัลกอริทึมการเข้ารหัส / ถอดรหัสควรทำงานอย่างไร คุณเพียงแค่ต้องตรวจสอบให้แน่ใจว่า 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

ฉันเห็นด้วยกับทุกสิ่งในคำตอบของ Martin York สิ่งเดียว: คุณสามารถหลีกเลี่ยงการมีสองunordered_mapวินาทีได้หากคุณไม่ได้สร้าง URL แบบสุ่มทั้งหมด แต่ให้สร้าง URL โดยการแฮช URL เดิมแทน ด้วยวิธีนี้คุณจะสร้าง 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 เดือน นอกจากนี้เมื่อคุณเห็นว่ามีหลายคน!วิ่งไปรอบ ๆ ก็ถึงเวลาที่จะต้องออกกฎหมายของ De Morgan และมันจะทำให้เราวางเส้นทางที่ไม่น่าสนใจให้ไกลออกไปจากสายตา ดังนั้นหากเราต้องการเทอร์นารีจริงๆ ...

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นั้นเป็น. เป็นคำที่ละเอียดกว่า แต่ก็ชัดเจนขึ้นทันทีสำหรับผู้อ่านว่าหมายถึงอะไร คนที่มีเหตุผลอาจไม่เห็นด้วย