LeetCode 535: encoder et décoder TinyURL
Je poste une solution pour "Encode and Decode TinyURL" de LeetCode. Si vous souhaitez examiner, veuillez le faire. Merci!
Problème
TinyURL est un service de raccourcissement d'URL dans lequel vous entrez une URL telle que https://leetcode.com/problems/design-tinyurlet il renvoie une URL courte telle que http://tinyurl.com/4e9iAk.
Concevez les méthodes encodeet decodepour le service TinyURL. Il n'y a aucune restriction sur le fonctionnement de votre algorithme d'encodage / décodage. Vous devez simplement vous assurer qu'une URL peut être codée en une petite URL et que la petite URL peut être décodée en l'URL d'origine.
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));
Réponses
Vous effectuez la recherche deux fois.
if (!encoded_url.count(long_url)) {
.. stuff
} else {
tiny_encoded = encoded_url[long_url];
}
Je sais que c'est O(1)pour la recherche. Mais il y a une vraie constante à l'intérieur de cela. Évitez-le si vous le pouvez.
Utilisez find(). Ensuite, s'il est là, vous pouvez simplement l'utiliser.
auto find = encoded_url.find(long_url);
if (find == encoded_url.end()) {
.. stuff
} else {
tiny_encoded = find->second;
}
C'est génial si vous voulez une URL aléatoire difficile à deviner.
for (auto index = 0; index < kTinySize; ++index) {
tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
}
Mais est-ce une exigence du puzzle. Semble (je ne sais pas combien coûte la génération du nombre aléatoire) comme cela est un moyen très coûteux de générer un nom.
Il y a aussi une chance pour un affrontement. Si vous utilisez des valeurs générées aléatoirement, ajoutez un horodatage à la fin pour éviter un conflit.
Personnellement, je n'aime pas avoir à spécifier un type. Mais si vous voulez le faire, utilisez le type de méthode plutôt que d'être aussi spécifique:
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));
Mais je pense que j'aurais simplement utilisé emplace().
encoded_url.emplace(long_url, tiny_encoded);
Je suis d'accord avec tout dans la réponse de Martin York. Juste une chose: vous pouvez éviter d'avoir deux unordered_maps si vous ne créez pas une URL purement aléatoire, mais en créez une en hachant l'URL d'origine. De cette façon, vous créerez toujours la même petite URL pour la même URL longue, vous n'en aurez donc encoded_urlplus besoin . Bien sûr, vous devrez toujours gérer les doublons d' une manière ou d'une autre .
D'autres ont fait valoir de bons points, mais j'ajouterai un petit problème stylistique.
return std::size(short_url) != kDomainTinySize ||
!decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
decoded_url[short_url.substr(kDomainSize, kTinySize)];
est un diable d'un one-liner. L'opérateur ternaire est amusant, mais parler comme quelqu'un qui en a absolument abusé, si vous ne pouvez pas le mettre confortablement sur une ligne ou deux, vous allez vous détester quand vous reviendrez le lire dans 6 mois. De plus, quand vous voyez que beaucoup de gens !courent partout, il est généralement temps d'écarter les lois de De Morgan. Et cela nous permettrait de mettre encore plus hors de vue le chemin inintéressant. Donc, si on veut vraiment le ternaire ...
return std::size(short_url) == kDomainTinySize &&
decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ?
decoded_url[short_url.substr(kDomainSize, kTinySize)] :
"";
ou si je me sentais un peu audacieux peut-être même
return std::size(short_url) == kDomainTinySize
&& decoded_url.count(short_url.substr(kDomainSize, kTinySize))
? decoded_url[short_url.substr(kDomainSize, kTinySize)]
: "";
J'ai menti, deuxième point: je dirais que le C ++ idiomatique devrait également s'appuyer le moins possible sur la conversion de type implicite, c'est-à-dire changer cette condition en decoded_url.count(...) != 0. C'est plus détaillé, mais c'est aussi immédiatement plus clair pour le lecteur ce que cela signifie. Les gens raisonnables pourraient cependant être en désaccord.