自增 ID、RabinKarp 哈希算法和随机数：求解《535. TinyURL 的加密与解密》

代码数据结构:字符串算法:Brian-Kernighan算法算法:哈希数学:随机数数学:随机化语言:JavaScript 语言:Go 语言:PHP 语言:Python 语言:C 语言:C++语言:C#语言:TypeScript 语言:Java

2022-06-29 17:14:24

自增 ID、RabinKarp 哈希算法和随机数，求解《535. TinyURL 的加密与解密》

例题

535. TinyURL 的加密与解密

TinyURL 是一种 URL 简化服务，比如：当你输入一个 URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的URL http://tinyurl.com/4e9iAk 。请你设计一个类来加密与解密 TinyURL 。
加密和解密算法如何设计和运作是没有限制的，你只需要保证一个 URL 可以被加密成一个 TinyURL ，并且这个 TinyURL 可以用解密方法恢复成原本的 URL 。
实现 Solution 类：
Solution() 初始化 TinyURL 系统对象。
String encode(String longUrl) 返回 longUrl 对应的 TinyURL 。
String decode(String shortUrl) 返回 shortUrl 原本的 URL 。题目数据保证给定的 shortUrl 是由同一个系统对象加密的。
示例：
输入：url = "https://leetcode.com/problems/design-tinyurl"
输出："https://leetcode.com/problems/design-tinyurl"
解释：
Solution obj = new Solution();
string tiny = obj.encode(url); // 返回加密后得到的 TinyURL 。
string ans = obj.decode(tiny); // 返回解密后得到的原本的 URL 。

答案

自增 ID

var encode = function(longUrl) { // 自增 ID
  this.DB = new Map()
  this.id = 0
  this.DB.set(this.id, longUrl)
  return 'http://tinyurl.com/' + (this.id++)
};

var decode = function(shortUrl) {
  const i = shortUrl.lastIndexOf('/') + 1
  return this.DB.get(+shortUrl.substring(i))
};

function encode(longUrl: string): string {
  this.DB = []
  this.id = 0
  this.DB[this.id] = longUrl
  return 'http://tinyurl.com/' + this.id++
};

function decode(shortUrl: string): string {
  const i = shortUrl.lastIndexOf('/') + 1
  return this.DB[shortUrl.substring(i)]
};

type Codec struct {
  DB map[int]string
  id int
}

func Constructor() Codec {
  return Codec{
    map[int]string{},
    -1,
  }
}

func (this *Codec) encode(longUrl string) string {
  this.id++
  this.DB[this.id] = longUrl
  return "http://tinyurl.com/" + strconv.Itoa(this.id)
}

func (this *Codec) decode(shortUrl string) string {
   i := strings.LastIndexByte(shortUrl, '/') + 1
   id, _ := strconv.Atoi(shortUrl[i:])
   return this.DB[id]
}

class Codec {
  private $DB = array();
  private $id = 0;  
  function encode($longUrl) {
    $this->DB[$this->id] = $longUrl;
    return 'http://tinyurl.com/' . $this->id++;
  }

  function decode($shortUrl) {
    $i = strrpos($shortUrl, '/') + 1;
    return $this->DB[substr($shortUrl, $i)];
  }
}

class Codec:
  DB, id = {}, -1
  def encode(self, longUrl: str) -> str:
    self.id += 1
    self.DB[self.id] = longUrl
    return "http://tinyurl.com/" + str(self.id)

  def decode(self, shortUrl: str) -> str:
    i = shortUrl.rfind('/') + 1
    return self.DB[int(shortUrl[i:])]

public class Codec {
  private Map<Integer, String> DB = new HashMap<Integer, String>();
  private int id = 0; 

  public String encode(String longUrl) {
    DB.put(id, longUrl);
    return "http://tinyurl.com/" + id++;
  }

  public String decode(String shortUrl) {
    int i = shortUrl.lastIndexOf('/') + 1;
    return DB.get(Integer.parseInt(shortUrl.substring(i)));
  }
}

class Solution {
public:
  unordered_map<int, string> DB;
  int id = 0;

  string encode(string longUrl) {
    DB[id] = longUrl;
    return "http://tinyurl.com/" + to_string(id++);
  }

  string decode(string shortUrl) {
    int i = shortUrl.rfind('/') + 1;
    return DB[stoi(shortUrl.substr(i))];
  }
};

public class Codec {
  private Dictionary<int, string> DB = new Dictionary<int, string>();
  private int id = 0;
  public string encode(string longUrl) {
    DB[id] = longUrl;
    return "http://tinyurl.com/" + id;
  }

  public string decode(string shortUrl) {
    int i = shortUrl.LastIndexOf('/') + 1;
    return DB[int.Parse(shortUrl.Substring(i))];
  }
}

RabinKarp 哈希算法

var encode = function(longUrl) { // 自增 ID
  this.DB = new Map()
  const BASE = 128, MOD = 1e4 + 7, n = longUrl.length
  let h = 0
  for (let i = 0; i < n; i++) {
    h += (h * BASE + longUrl.charCodeAt(i) - 97) % MOD
  }
  while (this.DB.has(h)) h++
  this.DB.set(h, longUrl)
  return 'http://tinyurl.com/' + h
};

var decode = function(shortUrl) {
  const i = shortUrl.lastIndexOf('/') + 1
  return this.DB.get(+shortUrl.substring(i))
};


function encode(longUrl: string): string {
  this.DB = []
  const BASE = 128, MOD = 1e7 + 7, n = longUrl.length
  let h = 0
  for (let i = 0; i < n; i++) {
    h += (h * BASE + longUrl.charCodeAt(i) - 97) % MOD
  }
  while (this.DB[h] !== void 0) h++
  this.DB[h] = longUrl
  return 'http://tinyurl.com/' + h
};

function decode(shortUrl: string): string {
  const i = shortUrl.lastIndexOf('/') + 1
  return this.DB[shortUrl.substring(i)]
};

type Codec struct {
  DB map[int]string
}

func Constructor() Codec {
  return Codec{
    map[int]string{},
  }
}

func (this *Codec) encode(longUrl string) string {
  const BASE, MOD = -1, 10000007
  h := 0
  for _, c := range longUrl {
    h += (h * BASE + int(c - 'a')) % MOD
  }
  for {
    if _, ok := this.DB[h]; ok == false {
      break
    }
    h++
  }
  this.DB[h] = longUrl
  return "http://tinyurl.com/" + strconv.Itoa(h)
}

func (this *Codec) decode(shortUrl string) string {
   i := strings.LastIndexByte(shortUrl, '/') + 1
   id, _ := strconv.Atoi(shortUrl[i:])
   return this.DB[id]
}

class Codec {
  private $DB = array(); 
  function encode($longUrl) {
    $BASE = 128;
    $MOD = 1e7 + 7;
    $n = strlen($longUrl);
    $h = 0;
    for ($i = 0; $i < $n; $i++) {
      $h += ($h * $BASE + ord($longUrl[$i]) - 97) % $MOD;
    }
    while ($DB[$h] !== null) $h++;
    $this->DB[$h] = $longUrl; 
    return 'http://tinyurl.com/' . $h;
  }

  function decode($shortUrl) {
    $i = strrpos($shortUrl, '/') + 1;
    return $this->DB[substr($shortUrl, $i)];
  }
}

class Codec:
  DB = {}
  def encode(self, longUrl: str) -> str:
    BASE, MOD, h = 128, 10000007, 0
    for _, c in enumerate(longUrl):
      h = (h * BASE + ord(c) - 97) % MOD
    while h in self.DB: h += 1
    self.DB[h] = longUrl
    return "http://tinyurl.com/" + str(h)

  def decode(self, shortUrl: str) -> str:
    i = shortUrl.rfind('/') + 1
    return self.DB[int(shortUrl[i:])]

public class Codec {
  private Map<Integer, String> DB = new HashMap<Integer, String>();

  public String encode(String longUrl) {
    int BASE = 128, MOD = 10000007, h = 0, n = longUrl.length();
    for (int i = 0; i < n; i++) {
      h = (h * BASE + longUrl.charAt(i) - 'a') % MOD;
    }
    while (DB.containsKey(h)) h++;
    DB.put(h, longUrl);
    return "http://tinyurl.com/" + h;
  }

  public String decode(String shortUrl) {
    int i = shortUrl.lastIndexOf('/') + 1;
    return DB.get(Integer.parseInt(shortUrl.substring(i)));
  }
}

BASE 128
MOD 10007
class Solution {
public:
  unordered_map<int, string> DB;

  string encode(string longUrl) {
    int h = 0;
    for (char c : longUrl) {
      h = (h * BASE + int(c - 'a')) % MOD; 
    }
    while (DB.find(h) != DB.end()) h++;
    DB[h] = longUrl;
    return "http://tinyurl.com/" + to_string(h);
  }

  string decode(string shortUrl) {
    int i = shortUrl.rfind('/') + 1;
    return DB[stoi(shortUrl.substr(i))];
  }
};

public class Codec {
  private Dictionary<int, string> DB = new Dictionary<int, string>();
  public string encode(string longUrl) {
    int BASE = 128, MOD = 10000007, h = 0, n = longUrl.Length;
    for (int i = 0; i < n; i++) {
      h += (h * BASE + longUrl[i] - 'a') % MOD;
    }
    while (DB.ContainsKey(h)) h++;
    DB.Add(h, longUrl);
    return "http://tinyurl.com/" + h;
  }

  public string decode(string shortUrl) {
    int i = shortUrl.LastIndexOf('/') + 1;
    return DB[int.Parse(shortUrl.Substring(i))];
  }
}

随机数

var encode = function(longUrl) { // 自增 ID
  this.DB = new Map()
  const BASE = 128, MOD = 1e4 + 7, n = longUrl.length
  let h = 0
  for (let i = 0; i < n; i++) {
    h = (h * BASE + longUrl.charCodeAt(i) - 97) % MOD
  }
  while (this.DB.has(h)) h++
  this.DB.set(h, longUrl)
  return 'http://tinyurl.com/' + h
};

var decode = function(shortUrl) {
  const i = shortUrl.lastIndexOf('/') + 1
  return this.DB.get(+shortUrl.substring(i))
};

function encode(longUrl: string): string {
  this.DB = []
  let h
  while (true) {
    h = Math.random() * Number.MAX_SAFE_INTEGER | 0
    if (this.DB[h] === void 0) break
  }
  this.DB[h] = longUrl
  return 'http://tinyurl.com/' + h
};

function decode(shortUrl: string): string {
  const i = shortUrl.lastIndexOf('/') + 1
  return this.DB[shortUrl.substring(i)]
};

type Codec struct {
  DB map[int]string
}

func Constructor() Codec {
  return Codec{
    map[int]string{},
  }
}

func (this *Codec) encode(longUrl string) string {
  h := 0
  for true {
    h = rand.Intn(int(^uint(0) >> 1))
    if _, ok := this.DB[h]; ok == false {
      break
    }
  }
  this.DB[h] = longUrl
  return "http://tinyurl.com/" + strconv.Itoa(h)
}

func (this *Codec) decode(shortUrl string) string {
   i := strings.LastIndexByte(shortUrl, '/') + 1
   id, _ := strconv.Atoi(shortUrl[i:])
   return this.DB[id]
}

class Codec {
  private $DB = array(); 
  function encode($longUrl) {
    $h = 0;
    while (true) {
      $h = rand(0, PHP_INT_MAX);
      if ($this->DB[$h] === null) break;
    }
    $this->DB[$h] = $longUrl; 
    return 'http://tinyurl.com/' . $h;
  }

  function decode($shortUrl) {
    $i = strrpos($shortUrl, '/') + 1;
    return $this->DB[substr($shortUrl, $i)];
  }
}

class Codec: # Python 2.7.12
  DB = {}
  def encode(self, longUrl):
    while True:
      h = randrange(sys.maxint)
      if h not in self.DB:
        self.DB[h] = longUrl
        return "http://tinyurl.com/" + str(h)

  def decode(self, shortUrl):
    i = shortUrl.rfind('/') + 1
    return self.DB[int(shortUrl[i:])]

class Codec: # Python 3.10
  DB = {}
  def encode(self, longUrl: str) -> str:
    while True:
      h = random.randrange(sys.maxsize)
      if h != self.DB:
        self.DB[h] = longUrl
        return "http://tinyurl.com/" + str(h)

  def decode(self, shortUrl: str) -> str:
    i = shortUrl.rfind('/') + 1
    return self.DB[int(shortUrl[i:])]

public class Codec {
  private Map<Integer, String> DB = new HashMap<Integer, String>();
  private Random random = new Random();

  public String encode(String longUrl) {
    while (true) {
      int h = random.nextInt();
      if (DB.containsKey(h) == false) {
        DB.put(h, longUrl);
        return "http://tinyurl.com/" + h;
      }
    }
  }

  public String decode(String shortUrl) {
    int i = shortUrl.lastIndexOf('/') + 1;
    return DB.get(Integer.parseInt(shortUrl.substring(i)));
  }
}

class Solution {
public:
  unordered_map<int, string> DB;

  string encode(string longUrl) {
    while (true) {
      int h = rand();
      if (DB.count(h) == 0) {
        DB[h] = longUrl;
        return "http://tinyurl.com/" + to_string(h);
      }
    }
  }

  string decode(string shortUrl) {
    int i = shortUrl.rfind('/') + 1;
    return DB[stoi(shortUrl.substr(i))];
  }
};

public class Codec {
  private Dictionary<int, string> DB = new Dictionary<int, string>();
  private Random rand = new Random();
  public string encode(string longUrl) {
    int h;
    while (true) {
      h = rand.Next();
      if (DB.ContainsKey(h) == false) break;
    }
    DB.Add(h, longUrl);
    return "http://tinyurl.com/" + h;
  }

  public string decode(string shortUrl) {
    int i = shortUrl.LastIndexOf('/') + 1;
    return DB[int.Parse(shortUrl.Substring(i))];
  }
}

Shon

Github　力扣　 M站　全部原创，请勿转载

比较字符串的子序列：求解《521. 最长特殊序列 Ⅰ》和《522. 最长特殊序列 II》

比较字符串的子序列，求解《521. 最长特殊序列 Ⅰ》和《522. 最长特殊序列 II》

字符串的 Unicode 码与字符转换，求解《709. 转换成小写字母》《1309. 解码字母到整数映射》和《953. 验证外星语词典》

字符串的 Unicode 码与字符本身的转换，求解《709. 转换成小写字母》《1309. 解码字母到整数映射》和《953. 验证外星语词典》

哈希映射 + 滑动窗口：求解《438. 找到字符串中所有字母异位词》和《30. 串联所有单词的子串》

哈希映射 + 滑动窗口，求解《438. 找到字符串中所有字母异位词》和《30. 串联所有单词的子串》