LeetCode 535: Kodowanie i dekodowanie TinyURL
Wysyłam rozwiązanie dla LeetCode „Koduj i dekoduj TinyURL”. Jeśli chcesz przejrzeć, zrób to. Dziękuję Ci!
Problem
TinyURL to usługa skracania adresu URL, w której wpisujesz adres URL, na przykład, https://leetcode.com/problems/design-tinyurla zwraca krótki adres URL, na przykład http://tinyurl.com/4e9iAk.
Zaprojektuj metody encodei decodedla usługi TinyURL. Nie ma ograniczeń co do sposobu działania algorytmu kodowania / dekodowania. Musisz tylko upewnić się, że adres URL można zakodować do małego adresu URL, a mały adres URL można zdekodować do oryginalnego adresu URL.
Kod
// 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));
Odpowiedzi
Wyszukujesz dwukrotnie.
if (!encoded_url.count(long_url)) {
.. stuff
} else {
tiny_encoded = encoded_url[long_url];
}
Wiem, że służy O(1)do wyszukiwania. Ale jest w tym prawdziwa stała. Unikaj tego, jeśli możesz.
Użyj find(). Jeśli tam jest, możesz go po prostu użyć.
auto find = encoded_url.find(long_url);
if (find == encoded_url.end()) {
.. stuff
} else {
tiny_encoded = find->second;
}
Jest to świetne rozwiązanie, jeśli potrzebujesz losowego adresu URL, który jest trudny do odgadnięcia.
for (auto index = 0; index < kTinySize; ++index) {
tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
}
Ale czy to wymóg układanki. Wydaje się (nie jestem pewien, jak kosztowne jest wygenerowanie liczby losowej), ponieważ jest to bardzo kosztowny sposób generowania nazwy.
Jest też szansa na starcie. Jeśli korzystasz z losowo generowanych wartości, dodaj na końcu znacznik czasu, aby uniknąć kolizji.
Osobiście nie lubię określać typu. Ale jeśli zamierzasz to zrobić, użyj raczej rodzaju metody niż tej konkretnej:
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));
Ale myślę, że po prostu użyłbym emplace().
encoded_url.emplace(long_url, tiny_encoded);
Zgadzam się ze wszystkim w odpowiedzi Martina Yorka. Tylko jedno: możesz uniknąć dwóch unordered_mapadresów, jeśli nie utworzysz czysto losowego adresu URL, ale zamiast tego utworzysz go, haszując oryginalny adres URL. W ten sposób zawsze będziesz tworzyć ten sam mały adres URL dla tego samego długiego adresu URL, więc nie będziesz encoded_urljuż potrzebować . Oczywiście nadal musiałbyś w jakiś sposób obsługiwać duplikaty .
Inni zrobili słuszne uwagi, ale dodam do tego kwestię stylistyczną.
return std::size(short_url) != kDomainTinySize ||
!decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
decoded_url[short_url.substr(kDomainSize, kTinySize)];
jest cholernie jednowierszowym. Operator trójskładnikowy jest fajny, ale mówiąc jak ktoś, kto go całkowicie nadużył, jeśli nie możesz go wygodnie zmieścić w jednej lub dwóch linijkach, to znienawidzisz siebie, gdy wrócisz do przeczytania tego za 6 miesięcy. Ponadto, gdy widzisz, że wiele osób !biegnie w kółko, zwykle jest to czas, aby złamać prawa De Morgana. A to pozwoliłoby nam odsunąć nieciekawą ścieżkę dalej poza zasięg wzroku. Tak więc, jeśli naprawdę chcemy trójskładnika ...
return std::size(short_url) == kDomainTinySize &&
decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ?
decoded_url[short_url.substr(kDomainSize, kTinySize)] :
"";
a może nawet gdybym czuł się trochę zuchwały
return std::size(short_url) == kDomainTinySize
&& decoded_url.count(short_url.substr(kDomainSize, kTinySize))
? decoded_url[short_url.substr(kDomainSize, kTinySize)]
: "";
Skłamałem, druga uwaga: twierdzę, że idiomatyczny C ++ powinien również polegać na niejawnej konwersji typów w jak najmniejszym stopniu, czyli zmienić ten warunek na decoded_url.count(...) != 0. Jest bardziej rozwlekły, ale czytelnik od razu wie, o co chodzi. Jednak rozsądni ludzie mogą się nie zgodzić.