哈希表题目 | 彩潭有鲤的札记

type

status

date

slug

summary

设计哈希集合

题目：不使用任何内建的哈希表库设计一个哈希集合（HashSet），实现MyHashSet类：

void add(key) 向哈希集合中插入值 key

bool contains(key) 返回哈希集合中是否存在这个值 key

void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例：

设哈希表的大小为，则可以设计一个简单的哈希函数：

开辟一个大小为的数组，数组的每个位置是一个链表。当计算出哈希值之后，就插入到对应位置的链表当中。由于使用整数除法作为哈希函数，为了尽可能避免冲突，应当将取为一个质数。在这里，取`

设计哈希映射

题目：不使用任何内建的哈希表库设计一个哈希映射（HashMap）。实现 MyHashMap 类：

MyHashMap() 用空映射初始化对象

void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。

int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 1 。

void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。

示例：

数组中重复的数字

题目：在一个长度为 n 的数组nums里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例：

数组中重复的数据

题目：给一个长度为 n 的整数数组nums，其中nums的所有整数都在范围[1, n] 内，且每个整数出现一次或两次。请找出所有出现两次的整数，并以数组形式返回。设计并实现一个时间复杂度为O(n)且仅使用常量额外空间的算法解决此问题。

示例：

多数元素

题目：给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素

示例：

存在重复元素

题目：给一个整数数组nums。如果任一值在数组中出现至少两次 ，返回true ；如果数组中每个元素互不相同，返回false 。

示例：

存在重复元素 II

题目：给你一个整数数组nums和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例：

存在重复元素 III

题目：给一个整数数组 nums 和两个整数k和t 。请判断是否存在两个不同下标i和j，使得abs(nums[i] - nums[j]) <= t ，同时又满足abs(i - j) <= k 。如果存在则返回 true，不存在返回 false。

示例：

对于序列中每一个元素左侧的至多个元素，如果这个元素中存在一个元素落在区间中，就找到了一对符合条件的元素。注意到对于两个相邻的元素，它们各自的左侧的个元素中有个是重合的。于是可以使用滑动窗口的思路，维护一个大小为的滑动窗口，每次遍历到元素时，滑动窗口中包含元素前面的最多个元素，检查窗口中是否存在元素落在区间中即可。

缺失的第一个正数

题目：给一个未排序的整数数组nums ，请你找出其中没有出现的最小的正整数。实现时间复杂度为 O(n) 并且只使用常数级别额外空间。

示例：

检查是否所有字符出现次数相同

题目：给一个字符串s，如果s是一个好字符串，请返回true，否则返回false。如果s中出现过的所有字符的出现次数相同，那么称字符串s是好字符串

示例：

只出现一次的数字

题目：给一个非空整数数组nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例：

扑克牌中的顺子

题目：从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为14。

示例：

赎金信

题目：给两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。

示例：

两个数组的交集

题目：给定两个数组nums1和nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。可以不考虑输出结果的顺序 。

示例：

两个数组的交集

题目：

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。

数字 1-9 在每一列只能出现一次。

数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。

只需要根据以上规则，验证已经填入的数字是否有效即可。

空白格用 '.' 表示。

示例：

有效的字母异位词

题目：给定两个字符串 s 和 t ，编写一个函数来判断t是否是s的字母异位词。若s和t中每个字符出现的次数都相同，则称s和t互为字母异位词。

示例：