哈希集合 + 哈希映射 + 随机数生成，求解《217. 存在重复元素》《242. 有效的字母异位词》和《710. 黑名单中的随机数》 710. 黑名单中的随机数
例题
217. 存在重复元素
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入：nums = [1,2,3,1]
输出：true
答案
哈希集合
var containsDuplicate = function(nums) {
const n = nums.length, s = new Set()
for (let i = 0; i < n; i++) {
if (s.has(nums[i])) return true
s.add(nums[i])
}
return false
};function containsDuplicate(nums: number[]): boolean {
const n = nums.length, s = new Set()
for (let i = 0; i < n; i++) {
if (s.has(nums[i])) return true
s.add(nums[i])
}
return false
};class Solution {
function containsDuplicate($nums) {
$s = [];
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
if ($s[$nums[$i]] !== null) return true;
$s[$nums[$i]] = true;
}
return false;
}
}func containsDuplicate(nums []int) bool {
type void struct{}
var value void
n, s := len(nums), map[int]void{}
for i := 0; i < n; i++ {
if _, ok := s[nums[i]]; ok {
return true
}
s[nums[i]] = value
}
return false
}class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> s = new HashSet<Integer>();
for (int n : nums) {
if (s.contains(n)) return true;
s.add(n);
}
return false;
}
}class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
s = set()
for _, c in enumerate(nums):
if c in s: return True
s.add(c)
return Falsestruct hashTable {
int key;
UT_hash_handle hh;
};
bool containsDuplicate(int* nums, int numsSize){
struct hashTable* set = NULL;
for (int i = 0; i < numsSize; i++) {
struct hashTable* tmp;
HASH_FIND_INT(set, nums + i, tmp);
if (tmp != NULL) return true;
else {
tmp = malloc(sizeof(struct hashTable));
tmp->key = nums[i];
HASH_ADD_INT(set, key, tmp);
}
}
return false;
}class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
set<int> s;
for (int n : nums) {
if (s.find(n) != s.end()) return true;
s.emplace(n);
}
return false;
}
};public class Solution {
public bool ContainsDuplicate(int[] nums) {
int n = nums.Length;
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < n; i++) {
if (s.Contains(nums[i])) return true;
s.Add(nums[i]);
}
return false;
}
}242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
答案
哈希映射
var isAnagram = function(s, t) {
if (s.length !== t.length) return false
const n = s.length, h = new Int16Array(26)
for (let i = 0; i < n; i++) {
h[s.charCodeAt(i) - 97]++
}
for (let i = 0; i < n; i++) {
h[t.charCodeAt(i) - 97]--
if (h[t.charCodeAt(i) - 97] < 0) return false
}
return true
};function isAnagram(s: string, t: string): boolean {
if (s.length !== t.length) return false
const n = s.length, h = new Int16Array(26)
for (let i = 0; i < n; i++) h[s.charCodeAt(i) - 97]++
for (let i = 0; i < n; i++) {
h[t.charCodeAt(i) - 97]--
if (h[t.charCodeAt(i) - 97] < 0) return false
}
return true
};func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
h := make([]int, 26)
for _, c := range s {
h[c - 'a']++
}
for _, c := range t {
h[c - 'a']--
if h[c - 'a'] < 0 {
return false
}
}
return true
}class Solution {
function isAnagram($s, $t) {
if (strlen($s) !== strlen($t)) return false;
$n = strlen($s);
$h = array_fill(0, 26, 0);
for ($i = 0; $i < $n; $i++) {
$h[ord($s[$i]) - 97]++;
}
for ($i = 0; $i < $n; $i++) {
$h[ord($t[$i]) - 97]--;
if ($h[ord($t[$i]) - 97] < 0) return false;
}
return true;
}
}class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t): return False
h = [0] * 26
for _, c in enumerate(s): h[ord(c) - 97] += 1
for _, c in enumerate(t):
h[ord(c) - 97] -= 1
if h[ord(c) - 97] < 0: return False
return Trueclass Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] h = new int[26];
int n = s.length();
for (int i = 0; i < n; i++) {
h[s.charAt(i) - 'a']++;
}
for (int i = 0; i < n; i++) {
h[t.charAt(i) - 'a']--;
if (h[t.charAt(i) - 'a'] < 0) return false;
}
return true;
}
}public class Solution {
public bool IsAnagram(string s, string t) {
if (s.Length != t.Length) return false;
int[] h = new int[26];
int n = s.Length;
for (int i = 0; i < n; i++) {
h[s[i] - 'a']++;
}
for (int i = 0; i < n; i++) {
h[t[i] - 'a']--;
if (h[t[i] - 'a'] < 0) return false;
}
return true;
}
}bool isAnagram(char * s, char * t){
if (strlen(s) != strlen(t)) return false;
int* h = (int*)malloc(sizeof(int) * 26);
for (int i = 0; i < 26; i++) h[i] = 0;
int n = strlen(s);
for (int i = 0; i < n; i++) {
h[s[i] - 'a']++;
}
for (int i = 0; i < n; i++) {
h[t[i] - 'a']--;
if (h[t[i] - 'a'] < 0) return false;
}
return true;
}class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
vector<int> h(26, 0);
int n = s.size();
for (char c : s) {
h[c - 'a']++;
}
for (char c : t) {
h[c - 'a']--;
if (h[c - 'a'] < 0) return false;
}
return true;
}
};710. 黑名单中的随机数
给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。
优化你的算法，使它最小化调用语言 内置 随机函数的次数。
实现 Solution 类:
Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数
int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数
示例 1：
输入
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
输出
[null, 0, 4, 1, 6, 1, 0, 4]
解释
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
// 0、1、4和6的返回概率必须相等(即概率为1/4)。
solution.pick(); // 返回 4
solution.pick(); // 返回 1
solution.pick(); // 返回 6
solution.pick(); // 返回 1
solution.pick(); // 返回 0
solution.pick(); // 返回 4
答案
哈希集合 · 哈希映射 · 随机数生成
var Solution = function(n, blacklist) {
const bn = blacklist.length
this.boundary = n - bn
const blackThanBoundary = new Set
for (let i = 0; i < bn; i++) if (blacklist[i] >= this.boundary) blackThanBoundary.add(blacklist[i])
let j = this.boundary - 1
this.m = new Map
for (let i = 0; i < bn; i++) {
if (blacklist[i] < this.boundary) {
while (++j) {
if (blackThanBoundary.has(j) === false) break
}
this.m.set(blacklist[i], j)
}
}
};
Solution.prototype.pick = function() {
const t = Math.random() * this.boundary | 0
return this.m.get(t) ?? t
};class Solution {
boundary
m
constructor(n: number, blacklist: number[]) {
const bn = blacklist.length
this.boundary = n - bn
this.m = Object.create(null)
const blackThanBoundary = new Set()
for (let i = 0; i < bn; i++) {
if (blacklist[i] >= this.boundary) blackThanBoundary.add(blacklist[i])
}
for (let i = 0, j = this.boundary - 1; i < bn; i++) {
if (blacklist[i] < this.boundary) {
while (++j) {
if (blackThanBoundary.has(j) == false) break
}
this.m[blacklist[i]] = j
}
}
}
pick(): number {
const t = Math.random() * this.boundary | 0
return this.m[t] ?? t
}
}class Solution {
private $boundary = 0;
private $m = [];
function __construct($n, $blacklist) {
$bn = count($blacklist);
$this->boundary = $n - $bn;
$blackThanBoundary = [];
for ($i = 0; $i < $bn; $i++) {
if ($blacklist[$i] >= $this->boundary) $blackThanBoundary[$blacklist[$i]] = 1;
}
$j = $this->boundary - 1;
for ($i = 0; $i < $bn; $i++) {
if ($blacklist[$i] < $this->boundary) {
while ($j++) {
if ($blackThanBoundary[$j] !== 1) break;
}
$this->m[$blacklist[$i]] = $j;
}
}
}
function pick() {
$t = rand(0, $this->boundary - 1);
return $this->m[$t] ?? $t;
}
}type Solution struct {
boundary int
m map[int]int
}
type void struct {}
func Constructor(n int, blacklist []int) Solution {
bn := len(blacklist)
boundary, m, value, blackThanBoundary := n - bn, map[int]int{}, void{}, map[int]void{}
for _, b := range blacklist {
if b >= boundary {
blackThanBoundary[b] = value
}
}
j := boundary - 1
for _, b := range blacklist {
if b < boundary {
for j < n {
j++
if _, ok := blackThanBoundary[j]; ok == false {
break
}
}
m[b] = j
}
}
return Solution{
boundary,
m,
}
}
func (this *Solution) Pick() int {
t := rand.Intn(this.boundary)
if _, ok := this.m[t]; ok {
return this.m[t]
}
return t
}class Solution {
private int boundary;
private Map<Integer, Integer> m = new HashMap<Integer, Integer>();
private Random random = new Random();
public Solution(int n, int[] blacklist) {
int bn = blacklist.length;
boundary = n - bn;
Set<Integer> blackThanBoundary = new HashSet<Integer>();
for (int i = 0; i < bn; i++) {
if (blacklist[i] >= boundary) blackThanBoundary.add(blacklist[i]);
}
for (int i = 0, j = boundary - 1; i < bn; i++) {
if (blacklist[i] < boundary) {
while (++j < n) {
if (blackThanBoundary.contains(j) == false) break;
}
m.put(blacklist[i], j);
}
}
}
public int pick() {
int t = random.nextInt(boundary);
return m.containsKey(t) ? m.get(t) : t;
}
}class Solution:
def __init__(self, n: int, blacklist: List[int]):
j = self.boundary = n - len(blacklist)
self.m = {}
blackThanBoundary = {black for black in blacklist if black >= self.boundary}
for black in blacklist:
if black < self.boundary:
while j in blackThanBoundary: j += 1
self.m[black] = j
j += 1
def pick(self) -> int:
t = random.randint(0, self.boundary - 1)
return self.m.get(t, t)public class Solution {
private int boundary;
private Dictionary<int, int> m = new Dictionary<int, int>();
private Random random = new Random();
public Solution(int n, int[] blacklist) {
int bn = blacklist.Length;
boundary = n - bn;
ISet<int> blackThanBoundary = new HashSet<int>();
foreach (int black in blacklist) {
if (black >= boundary) blackThanBoundary.Add(black);
}
int j = boundary - 1;
foreach (int black in blacklist) {
if (black < boundary) {
while (j < n) {
j++;
if (blackThanBoundary.Contains(j) == false) break;
}
m.Add(black, j);
}
}
}
public int Pick() {
int t = random.Next(boundary);
return m.ContainsKey(t) ? m[t] : t;
}
}class Solution {
public:
unordered_map<int, int> m;
int boundary;
Solution(int n, vector<int>& blacklist) {
int bn = blacklist.size();
boundary = n - bn;
set<int> blackThanBoundary;
for (int black : blacklist) {
if (black >= boundary) blackThanBoundary.emplace(black);
}
int j = boundary - 1;
for (int black : blacklist) {
if (black < boundary) {
while (++j) {
if (blackThanBoundary.find(j) == blackThanBoundary.end()) break;
}
m[black] = j;
}
}
}
int pick() {
int t = rand() % boundary;
return m.count(t) ? m[t] : t;
}
};