SP3. 某度短网址
描述
示例1
输入:
["http:www.baidu.com", "http://www.nowcoder.com"],["http://tiny.urleNm26h"]
输出:
["http://tiny.urleNm26h","http://tiny.urlJc7hPD","http:www.baidu.com"]
C++ 解法, 执行用时: 3ms, 内存消耗: 392KB, 提交时间: 2022-07-08
class Solution {
public:
vector<string> urlTransformation(vector<string>& long_url, vector<string>& short_url) {
const long mod = 56800235584L;
char dict[] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
unordered_set<long> st; // 防止key值冲突
unordered_map<string, string> decode; // 用于解码
vector<string> ans;
for (string& s : long_url) {
long key = 0L; // 注意初值为0才可以
for (char c : s)
key = (key * 64 + c) % mod;
while (st.count(key))
key = (key + 1) % mod;
st.insert(key);
string str; // 映射字符串
for (int i = 0; i < 6; ++i) {
char c = dict[key % 62];
str.push_back(c);
key /= 62;
}
reverse(str.begin(), str.end());
string code = "http://tiny.url" + str;
decode[code] = s;
ans.emplace_back(code);
}
for (string& s : short_url) {
ans.emplace_back(decode[s]);
}
return ans;
}//42
};
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-07-21
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param long_url string字符串vector
* @param short_url string字符串vector
* @return string字符串vector
*/
unordered_map<unsigned long long , bool>mp;
unordered_map<string, int>rmp;
string s="123456";
string s1="http://tiny.url";
string s2="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int cnt=0;
void solve(string &str,vector<string>&res){
unsigned long long key=0,mod=56800235584,t1=64,t2=62;
for(int i=0;str[i];++i)
key=((key<<6)+(unsigned long long)str[i])%mod;
while(mp.count(key)) ++key;
mp[key]=true;
for(int i=5;i>=0;--i){
s[i]=s2[(int)(key%t2)];
key/=t2;
}
res.push_back((s1+s));
rmp[s]=cnt++;
}
vector<string> urlTransformation(vector<string>& long_url, vector<string>& short_url) {
// write code here
vector<string>res;
for(int i=0;i<long_url.size();++i)
solve(long_url[i],res);
for(int i=0;i<short_url.size();++i)
res.push_back(long_url[rmp[short_url[i].substr(15)]]);
return res;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 396KB, 提交时间: 2022-07-06
class Solution {
public:
vector<string> urlTransformation(vector<string> &long_url, vector<string> &short_url)
{
static long mod = 56800235584;
static std::string table = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
std::unordered_map<long, std::string> key_long_hash; // key和长网址绑定
std::unordered_map<std::string, long> short_key_hash; // 短网址和key绑定
auto generate_short_url = [](long key)
{
std::string url(6, '0');
int index = 6;
while (key > 0)
{
url[--index] = table[key % 62];
key /= 62;
}
return url;
};
auto calc_key = [&key_long_hash](const std::string &url) -> long
{
long key = 0;
for (auto c : url)
{
key = (key * 64 + c) % mod;
}
while (key_long_hash.find(key) != key_long_hash.end())
{
key = (key + 1) % mod;
}
return key;
};
std::vector<std::string> ans;
std::string prefix = "http://tiny.url";
for (auto &url : long_url)
{
long key = calc_key(url);
auto s = generate_short_url(key);
key_long_hash[key] = url;
short_key_hash[s] = key;
ans.push_back(prefix + s);
}
for (auto &url : short_url)
{
auto pos = url.find(prefix);
if (pos == url.npos)
{
continue;
}
auto s = url.substr(pos + prefix.size());
if (short_key_hash.find(s) != short_key_hash.end())
{
ans.push_back(key_long_hash[short_key_hash[s]]);
}
}
return ans;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 404KB, 提交时间: 2022-07-25
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param long_url string字符串vector
* @param short_url string字符串vector
* @return string字符串vector
*/
const int64_t mod = 56800235584;
const string table = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
unordered_map<int64_t, string> key_long_hash; // key和长网址绑定
unordered_map<std::string, int64_t> short_key_hash; // 短网址和key绑定
string generate_short_url(int64_t key)
{
std::string url(6, '0');
int index = 6;
while (key > 0)
{
url[--index] = table[key % 62];
key /= 62;
}
return url;
};
int64_t calc_key(const std::string& url)
{
int64_t key = 0;
for (auto c : url)
{
key = (key * 64 + c) % mod;
}
while (key_long_hash.find(key) != key_long_hash.end())
{
key = (key + 1) % mod;
}
return key;
};
vector<string> urlTransformation(vector<string>& long_url, vector<string>& short_url) {
// write code here
std::vector<std::string> ans;
std::string prefix = "http://tiny.url";
for (auto& url : long_url)
{
int64_t key = calc_key(url);
auto s = generate_short_url(key);
key_long_hash[key] = url;
short_key_hash[s] = key;
ans.push_back(prefix + s);
}
for (auto& url : short_url)
{
auto pos = url.find(prefix);
if (pos == url.npos)
{
continue;
}
auto s = url.substr(pos + prefix.size());
if (short_key_hash.find(s) != short_key_hash.end())
{
ans.push_back(key_long_hash[short_key_hash[s]]);
}
}
return ans;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 404KB, 提交时间: 2022-06-30
#include<unordered_map>
typedef long long ll;
class Solution {
private:
unordered_map<string,ll> long_to_key;
unordered_map<ll,string> key_to_short;
unordered_map<string,string> short_to_long;
public:
ll compKey(const string& l){
ll key=0;
for (int i=0;i<l.length();i++){
key=(key*64+l[i])%56800235584;
}
auto it=long_to_key.begin();
while (it!=long_to_key.end()){
if (it->second==key){
key=(key+1)%56800235584;
it=long_to_key.begin();
continue;
}
it++;
}
return key;
}
string keyToShort(ll key){
string keyref="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
string s(6,'0');
for (int i=5;i>=0;i--){
s[i]=keyref[key%62];
key=key/62;
}
return s;
}
void convert(const vector<string>& long_url){
for (int i=0;i<long_url.size();i++){
ll key=compKey(long_url[i]);
long_to_key[long_url[i]]=key;
string s=keyToShort(key);
key_to_short[key]=s;
short_to_long[s]=long_url[i];
}
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param long_url string字符串vector
* @param short_url string字符串vector
* @return string字符串vector
*/
vector<string> urlTransformation(vector<string>& long_url, vector<string>& short_url) {
// write code here
vector<string> output;
convert(long_url);
for (int i=0;i<long_url.size();i++){
output.push_back("http://tiny.url"+key_to_short[long_to_key[long_url[i]]]);
}
for (int i=0;i<short_url.size();i++){
output.push_back(short_to_long[short_url[i].substr(15)]);
}
return output;
}
};