LeetCode 535：TinyURLのエンコードとデコード
LeetCodeの「EncodeandDecodeTinyURL」のソリューションを投稿しています。確認したい場合は、行ってください。ありがとうございました！
問題
TinyURLは、などのURLを入力すると、などhttps://leetcode.com/problems/design-tinyurlの短いURLを返すURL短縮サービスですhttp://tinyurl.com/4e9iAk。
TinyURLサービスのencodeと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));
回答
ルックアップを2回実行しています。
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);
私はマーティンヨークの答えのすべてに同意します。ただ1つだけです。unordered_map純粋にランダムなURLを作成しない場合は、2つにするのを避け、代わりに元のURLをハッシュして1つ作成することができます。このようにすると、同じ長いURLに対して常に同じ小さなURLが作成されるため、encoded_urlもう必要ありません。もちろん、何らかの方法で重複を処理する必要があります。
他の人は良い点を挙げていますが、私は様式的なクイズを追加します。
return std::size(short_url) != kDomainTinySize ||
!decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
decoded_url[short_url.substr(kDomainSize, kTinySize)];
ワンライナーの一体です。三項演算子は楽しいですが、絶対にそれを悪用した人として話すと、1、2行に快適に収まらない場合は、6か月後に戻ってそれを読むと嫌になります。また、多く!の人が走り回っているのを見ると、通常はド・モルガンの法則を破る時が来ています。そして、それは私たちが興味のない道をさらに見えなくすることを可能にするでしょう。だから、本当に三元が欲しいのなら...
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)]
: "";
私は嘘をついた、2番目のポイント：慣用的なC ++も暗黙の型変換にできるだけ依存しないようにする必要があると主張しdecoded_url.count(...) != 0ます。つまり、その条件をに変更します。これはより冗長ですが、読者には意味がすぐにわかります。しかし、合理的な人々は反対する可能性があります。