LeetCode 535: Mã hóa và giải mã TinyURL
Tôi đang đăng một giải pháp cho "Mã hóa và giải mã TinyURL" của LeetCode. Nếu bạn muốn xem lại, hãy làm. Cảm ơn bạn!
Vấn đề
TinyURL là một dịch vụ rút ngắn URL, nơi bạn nhập một URL chẳng hạn https://leetcode.com/problems/design-tinyurlvà nó trả về một URL ngắn chẳng hạn http://tinyurl.com/4e9iAk.
Thiết kế các encodevà decodephương pháp cho dịch vụ TinyURL. Không có hạn chế về cách thuật toán mã hóa / giải mã của bạn sẽ hoạt động. Bạn chỉ cần đảm bảo rằng một URL có thể được mã hóa thành một URL nhỏ và URL nhỏ có thể được giải mã thành URL ban đầu.
Mã
// 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));
Trả lời
Bạn đang thực hiện tra cứu hai lần.
if (!encoded_url.count(long_url)) {
.. stuff
} else {
tiny_encoded = encoded_url[long_url];
}
Tôi biết rằng nó là O(1)để tra cứu. Nhưng có một hằng số thực sự bên trong đó. Hãy tránh nó nếu bạn có thể.
Sử dụng find(). Sau đó, nếu nó ở đó, bạn có thể chỉ cần sử dụng nó.
auto find = encoded_url.find(long_url);
if (find == encoded_url.end()) {
.. stuff
} else {
tiny_encoded = find->second;
}
Điều này thật tuyệt nếu bạn muốn có URL ngẫu nhiên khó đoán.
for (auto index = 0; index < kTinySize; ++index) {
tiny_encoded.push_back(char_pool[rand_generator() % std::size(char_pool)]);
}
Nhưng đó có phải là một yêu cầu của câu đố. Có vẻ như (không chắc việc tạo ra số ngẫu nhiên đắt thế nào) như thế này là một cách tạo tên rất tốn kém.
Cũng có cơ hội xảy ra đụng độ. Nếu bạn đang sử dụng các giá trị được tạo ngẫu nhiên, hãy thêm dấu thời gian vào cuối để tránh xung đột.
Cá nhân tôi không thích phải chỉ định một loại. Nhưng nếu bạn muốn làm điều đó, hãy sử dụng loại phương pháp thay vì cụ thể như sau:
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));
Nhưng tôi nghĩ đơn giản là tôi đã sử dụng emplace().
encoded_url.emplace(long_url, tiny_encoded);
Tôi đồng ý với mọi thứ trong câu trả lời của Martin York. Chỉ một điều: bạn có thể tránh có hai unordered_mapURL nếu bạn không tạo một URL hoàn toàn ngẫu nhiên, nhưng thay vào đó hãy tạo một URL bằng cách băm URL ban đầu. Bằng cách này, bạn sẽ luôn tạo cùng một URL nhỏ cho cùng một URL dài, vì vậy bạn không cần encoded_urlnữa. Tất nhiên, bạn vẫn cần phải xử lý các bản sao theo một cách nào đó .
Những người khác đã đưa ra những điểm tốt, nhưng tôi sẽ thêm vào một cách phân minh theo phong cách.
return std::size(short_url) != kDomainTinySize ||
!decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ? "" :
decoded_url[short_url.substr(kDomainSize, kTinySize)];
là một con quái vật của một lớp lót. Nhà điều hành bậc ba rất vui nhưng nói như một người đã hoàn toàn lạm dụng nó, nếu bạn không thể đặt nó một cách thoải mái trên một hoặc hai dòng thì bạn sẽ ghét chính mình khi đọc lại nó sau 6 tháng. Ngoài ra, khi bạn thấy nhiều người !chạy xung quanh thì thường là lúc bạn phải phá bỏ định luật De Morgan. Và nó sẽ cho chúng ta đặt con đường không thú vị xa hơn trong tầm mắt. Vì vậy, nếu chúng ta thực sự muốn chim nhạn ...
return std::size(short_url) == kDomainTinySize &&
decoded_url.count(short_url.substr(kDomainSize, kTinySize)) ?
decoded_url[short_url.substr(kDomainSize, kTinySize)] :
"";
hoặc nếu tôi cảm thấy hơi táo bạo thậm chí có thể
return std::size(short_url) == kDomainTinySize
&& decoded_url.count(short_url.substr(kDomainSize, kTinySize))
? decoded_url[short_url.substr(kDomainSize, kTinySize)]
: "";
Tôi đã nói dối, điểm thứ hai: Tôi sẽ khẳng định rằng C ++ thành ngữ cũng nên dựa vào việc chuyển đổi kiểu ngầm càng ít càng tốt, có nghĩa là, hãy thay đổi điều kiện đó thành decoded_url.count(...) != 0. Nó dài dòng hơn, nhưng nó cũng ngay lập tức rõ ràng hơn cho người đọc ý nghĩa của nó. Những người hợp lý có thể không đồng ý.