LeetCode 535: Encode dan Decode TinyURL
Saya memposting solusi untuk LeetCode "Encode and Decode TinyURL". Jika Anda ingin mengulas, harap lakukan. Terima kasih!
Masalah
TinyURL adalah layanan pemendekan URL di mana Anda memasukkan URL seperti https://leetcode.com/problems/design-tinyurldan mengembalikan URL singkat seperti http://tinyurl.com/4e9iAk.
Mendesain encodedan decodemetode untuk layanan TinyURL. Tidak ada batasan tentang bagaimana algoritma encode / decode Anda harus bekerja. Anda hanya perlu memastikan bahwa URL dapat dikodekan menjadi URL kecil dan URL kecil dapat diterjemahkan ke URL asli.
Kode
// 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));
Jawaban
Anda melakukan pencarian dua kali.
if (!encoded_url.count(long_url)) {
.. stuff
} else {
tiny_encoded = encoded_url[long_url];
}
Saya tahu itu O(1)untuk pencarian. Tapi ada konstanta nyata di dalamnya. Hindari jika Anda bisa.
Gunakan find(). Kemudian jika ada, Anda bisa menggunakannya.
auto find = encoded_url.find(long_url);
if (find == encoded_url.end()) {
.. stuff
} else {
tiny_encoded = find->second;
}
Ini bagus jika Anda menginginkan URL acak yang sulit ditebak.
for (auto index = 0; index < kTinySize; ++index) {
tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
}
Tapi apakah itu persyaratan teka-teki. Tampaknya (tidak yakin seberapa mahal menghasilkan nomor acak) seperti ini adalah cara yang sangat mahal untuk menghasilkan nama.
Ada juga peluang untuk bentrokan. Jika Anda menggunakan nilai yang dihasilkan secara acak, tambahkan stempel waktu di bagian akhir untuk menghindari bentrokan.
Secara pribadi saya tidak suka harus menentukan tipe. Tetapi jika Anda ingin melakukannya, gunakan tipe metode daripada spesifik ini:
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));
Tapi saya pikir saya hanya akan menggunakan emplace().
encoded_url.emplace(long_url, tiny_encoded);
Saya setuju dengan semua jawaban Martin York. Hanya satu hal: Anda dapat menghindari memiliki dua unordered_mapjika Anda tidak membuat URL yang murni acak, melainkan membuatnya dengan mencirikan URL asli. Dengan cara ini, Anda akan selalu membuat URL kecil yang sama untuk URL panjang yang sama, jadi Anda tidak perlu encoded_urllagi. Tentu saja, Anda masih perlu menangani duplikat dengan cara tertentu .
Orang lain telah membuat poin bagus, tapi saya akan menambahkan quibble gaya.
return std::size(short_url) != kDomainTinySize ||
!decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
decoded_url[short_url.substr(kDomainSize, kTinySize)];
adalah salah satu kalimat. Operator terner menyenangkan tetapi berbicara sebagai seseorang yang benar-benar telah menyalahgunakannya, jika Anda tidak dapat menyesuaikannya dengan nyaman pada satu atau dua baris maka Anda akan membenci diri sendiri ketika Anda kembali membacanya dalam 6 bulan. Juga, ketika Anda melihat banyak orang !berkeliaran, biasanya inilah saatnya untuk melanggar hukum De Morgan. Dan itu akan membiarkan kita menyingkirkan jalan yang tidak menarik lebih jauh dari pandangan. Jadi, jika kita benar-benar menginginkan terner ...
return std::size(short_url) == kDomainTinySize &&
decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ?
decoded_url[short_url.substr(kDomainSize, kTinySize)] :
"";
atau jika saya merasa agak berani bahkan mungkin
return std::size(short_url) == kDomainTinySize
&& decoded_url.count(short_url.substr(kDomainSize, kTinySize))
? decoded_url[short_url.substr(kDomainSize, kTinySize)]
: "";
Saya berbohong, poin kedua: Saya akan mengklaim bahwa idiomatik C ++ juga harus bergantung pada konversi tipe implisit sesedikit mungkin, artinya, ubah kondisi itu menjadi decoded_url.count(...) != 0. Ini lebih bertele-tele, tetapi juga segera lebih jelas bagi pembaca apa yang dimaksud. Orang yang berakal sehat bisa saja tidak setuju.