LeetCode 535: TinyURL codieren und decodieren
Ich veröffentliche eine Lösung für LeetCodes "Encode and Decode TinyURL". Wenn Sie eine Bewertung abgeben möchten, tun Sie dies bitte. Dankeschön!
Problem
TinyURL ist ein URL-Verkürzungsdienst, bei dem Sie eine URL wie eingeben https://leetcode.com/problems/design-tinyurlund eine kurze URL wie zurückgeben http://tinyurl.com/4e9iAk.
Entwerfen Sie die encodeund decodeMethoden für den TinyURL-Service. Es gibt keine Einschränkung, wie Ihr Codierungs- / Decodierungsalgorithmus funktionieren soll. Sie müssen nur sicherstellen, dass eine URL in eine winzige URL codiert und die winzige URL in die ursprüngliche URL decodiert werden kann.
Code
// 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));
Antworten
Sie führen die Suche zweimal durch.
if (!encoded_url.count(long_url)) {
.. stuff
} else {
tiny_encoded = encoded_url[long_url];
}
Ich weiß, dass es O(1)für die Suche ist. Aber darin steckt eine echte Konstante. Vermeiden Sie es, wenn Sie können.
Verwenden Sie find(). Wenn es dort ist, können Sie es einfach verwenden.
auto find = encoded_url.find(long_url);
if (find == encoded_url.end()) {
.. stuff
} else {
tiny_encoded = find->second;
}
Dies ist großartig, wenn Sie eine zufällige URL wünschen, die schwer zu erraten ist.
for (auto index = 0; index < kTinySize; ++index) {
tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
}
Aber ist das eine Voraussetzung für das Puzzle? Scheint (nicht sicher, wie teuer das Generieren der Zufallszahl ist), dass dies eine sehr teure Art ist, einen Namen zu generieren.
Es besteht auch die Möglichkeit eines Zusammenstoßes. Wenn Sie zufällig generierte Werte verwenden, fügen Sie am Ende einen Zeitstempel hinzu, um einen Konflikt zu vermeiden.
Persönlich mag ich es nicht, einen Typ angeben zu müssen. Wenn Sie dies jedoch tun möchten, verwenden Sie den Typ der Methode, anstatt so spezifisch zu sein:
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));
Aber ich denke ich hätte es einfach benutzt emplace().
encoded_url.emplace(long_url, tiny_encoded);
Ich stimme mit allem in Martin Yorks Antwort überein. Nur eines: Sie können zwei unordered_maps vermeiden, wenn Sie keine rein zufällige URL erstellen, sondern eine erstellen, indem Sie die ursprüngliche URL hashen. Auf diese Weise erstellen Sie immer dieselbe winzige URL für dieselbe lange URL, sodass Sie sie nicht encoded_urlmehr benötigen . Natürlich müssten Sie immer noch auf irgendeine Weise mit Duplikaten umgehen .
Andere haben gute Punkte gemacht, aber ich werde in einem stilistischen Streit hinzufügen.
return std::size(short_url) != kDomainTinySize ||
!decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
decoded_url[short_url.substr(kDomainSize, kTinySize)];
ist ein verdammter Einzeiler. Der ternäre Operator macht Spaß, spricht aber als jemand, der ihn absolut missbraucht hat. Wenn Sie ihn nicht bequem in ein oder zwei Zeilen einpassen können, werden Sie sich selbst hassen, wenn Sie ihn in 6 Monaten wieder lesen. Wenn Sie sehen, dass viele !herumlaufen, ist es normalerweise an der Zeit, De Morgans Gesetze aufzuheben. Und es würde uns den uninteressanten Weg weiter außer Sichtweite bringen. Also, wenn wir wirklich das Ternäre wollen ...
return std::size(short_url) == kDomainTinySize &&
decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ?
decoded_url[short_url.substr(kDomainSize, kTinySize)] :
"";
oder wenn ich mich ein bisschen kühn fühlte, vielleicht sogar
return std::size(short_url) == kDomainTinySize
&& decoded_url.count(short_url.substr(kDomainSize, kTinySize))
? decoded_url[short_url.substr(kDomainSize, kTinySize)]
: "";
Ich habe gelogen, zweiter Punkt: Ich würde behaupten, dass idiomatisches C ++ auch so wenig wie möglich auf impliziter Typkonvertierung beruhen sollte, dh diese Bedingung in ändern sollte decoded_url.count(...) != 0. Es ist ausführlicher, aber es ist dem Leser auch sofort klarer, was gemeint ist. Vernünftige Leute könnten jedoch anderer Meinung sein.