HASH以及leetcode刷题
HASH表知识点总结
简单一句话说,就是键值对的映射。大部分都已经接触过了,这里主要就是对java的HASH,怎么申请进行一个总结。HASH表可以实现判断一个元素是否出现过,如果这个元素没有出现过,便将这个元素插入到HASH表中,方便下次的查询。
目前实现HASH表有三种方式:
- 数组
- hashmap
- hashset(不允许重复元素的插入)
数组整体实现相对比较简单,这里对hashmap和hashset进行一个介绍
HashMap使用方法
HashMap定义:可以指定键(Key)和值(Value)的类型。
HashMap<KeyType, ValueType> hashMap = new HashMap<>(); HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
添加元素:使用
put()
方法向哈希表中添加键值对。map.put(2,1);
获取元素:使用
get()
方法通过键获取对应的值。int value = map.get(2);
删除元素:使用
remove()
方法通过键删除对应的键值对。map.remove(2);
判断键是否存在:使用
containsKey()
方法检查某个键是否存在于哈希表中。map.containsKey(2);
获取哈希表大小:使用
size()
方法获取哈希表中键值对的数量。int n = map.size();
判断是否为空:使用
isEmpty()
方法检查hashmap
是否为空。map.isEmpty();
清空
hashmap
表:使用clear()
方法清空hashmap
set.clear();
HashSet使用方法
HashSet
定义:可以指定键(Key)
类型,没有值.使用HashSet
类创建一个HashSet
,用于存储特定类型的元素。用于存储不重复元素的集合。HashSet<ElementType> hashSet = new HashSet<>(); HashSet<Integer> set = new HashSet<Integer>();
添加元素:使用
add()
方法添加指定元素set.add(4);
删除元素:使用
remove()
方法删除元素set.remove(4);
判断元素是否存在:使用
contains()
方法检查元素是否存在set.contains(4);
获取
set
表大小:使用size()
方法获取哈希表中的数量。int n = set.size();
判断是否为空:使用
isEmpty()
方法检查hashset
是否为空。map.isEmpty();
清空
set
表:使用clear()
方法清空hashset
set.clear();
刷题
有效的字母异位词
题目:
给定两个字符串 *s*
和 *t*
,编写一个函数来判断 *t*
是否是 *s*
的字母异位词。
**注意:**若 *s*
和 *t*
中每个字符出现的次数都相同,则称 *s*
和 *t*
互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
提示:
1 <= s.length, t.length <= 5 * 104
s
和t
仅包含小写字母
思路:
- 由于字符串中只包含小写字符,所以可以直接通过
int
数组来模拟hash
表的实现 - 具体实现,先将字符串类型转换为字符数组类型,然后遍历两个数组,一个数组从正向统计每个字符出现的次数,另一个数组从反向统计字符出现的次数。最后面,再遍历一次数组,判断是否出现不为0的符号,如果出现,说明不符合条件。
代码:
class Solution {
public boolean isAnagram(String s, String t) {
//转为字符数组
char[] sstr = s.toCharArray();
char[] tstr = t.toCharArray();
int slen = sstr.length;
int tlen = tstr.length;
//长度不同,不符合条件
if(slen != tlen) return false;
int hash[] = new int[26];
//正向和反向统计出现的次数
for(int i = 0; i < slen; i++){
hash[sstr[i]-'a']++;
hash[tstr[i]-'a']--;
}
//hash表判断
for(int i = 0; i < 26; i++){
if(hash[i] != 0) return false;
}
return true;
}
}
两个数组的交集
题目:
给定两个数组
nums1
和nums2
,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[9,4] 解释:[4,9] 也是可通过的
思路:
- 首先先将一个数组放到
HashSet
当中,因为set
有自助去重功能,可以利用一下这个作用,然后遍历第二个数组,如果第二个数组里面的元素,出现在了HashSet
当中,便可以加到另外一个HashSet
当中。然后将新的HashSet
转为数组即可。 HashSet
有自助去重功能。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
//两个数组的交集
Set<Integer> array = new HashSet<Integer>();
Set<Integer> set = new HashSet<Integer>();
//先将一个加入到hashset当中
for(int x : nums1){
set.add(x);
}
//判断另外一个
for(int x : nums2){
if(set.contains(x)){
array.add(x);
}
}
//转换为数组
int n = array.size();
int ans[] = new int[n];
int index = 0;
for(int x : array){
ans[index++] = x;
}
return ans;
// return array.stream().mapToInt(Integer::intValue).toArray();
}
}
快乐数
题目:
编写一个算法来判断一个数 n
是不是快乐数。
「快乐数」 定义为:
- 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n
是 快乐数 就返回 true
;不是,则返回 false
。
示例 1:
输入:n = 19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2:
输入:n = 2
输出:false
思路:
- 首先,自己进行手动推导会发现,快乐数并不会一直增大,只会出现两种可能:
- 不断循环出现之前出现过的数字
- 各位数字之和为1
- 编写求各位数字之和的函数,然后利用hash表或者快慢指针进行寻找。
- 出现1,返回
true
,出现循环返回false
- 出现1,返回
class Solution {
public int nextNum(int n){
int next = 0;
//求取n各个位置上的数,然后求平方
while(n > 0){
int temp = n % 10;
next += temp*temp;
n /= 10;
}
return next;
}
public boolean isHappy(int n) {
//注意,n要么一直被循环,要么就是为1,不会一直变大
//方法一:Hash表
//每次替换成数字的平方和
// HashSet<Integer> set = new HashSet<Integer>();
// while(true){
// if(n == 1) return true;
// if(!set.contains(n)){
// set.add(n);
// }
// else return false;
// n = nextNum(n);
// }
//方法二:快慢指针
int slow = n;
int fast = n;
while(true){
slow = nextNum(slow);
fast = nextNum(fast);
fast = nextNum(fast);
if(slow == 1 || fast == 1) return true;
if(slow == fast) return false;
}
// return true;
}
}
赎金信
题目:
给你两个字符串:ransomNote
和 magazine
,判断 ransomNote
能不能由 magazine
里面的字符构成。
如果可以,返回 true
;否则返回 false
。
magazine
中的每个字符只能在 ransomNote
中使用一次。
示例 1:
输入:ransomNote = "a", magazine = "b"
输出:false
示例 2:
输入:ransomNote = "aa", magazine = "ab"
输出:false
示例 3:
输入:ransomNote = "aa", magazine = "aab"
输出:true
思路:
- 由于字符串中只包含小写字符,所以可以直接通过
int
数组来模拟hash
表的实现 - 具体实现,先将字符串类型转换为字符数组类型,然后遍历两个数组,一个数组从正向统计每个字符出现的次数,另一个数组从反向统计字符出现的次数。最后面,再遍历一次数组,判断是否数组元素中出现小于0的符号,如果出现,说明不符合条件。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int nums[] = new int[26];
char mag[] = magazine.toCharArray();
char ransom[] = ransomNote.toCharArray();
for(char x : mag){
nums[x-'a']++;
}
for(char x : ransom){
nums[x-'a']--;
if(nums[x-'a'] < 0) return false;
}
return true;
}
}
两数之和
题目:
给定一个整数数组 nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 target
的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
示例 2:
输入:nums = [3,2,4], target = 6
输出:[1,2]
示例 3:
输入:nums = [3,3], target = 6
输出:[0,1]
思路:
- 利用hash表,牺牲空间换时间,遍历数组,如果该元素第一次出现,就放入hash表当中,存入的是
target-该元素的值
- 如果不是第一次出现,判断这个数是否出现在hash表中,如果出现,说明满足条件,返回。
class Solution {
public int[] twoSum(int[] nums, int target) {
//hash表的使用刷题
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int ans[] = new int[2];
for(int i = 0; i < nums.length; i++){
if(map.containsKey(nums[i])){
return new int[]{
i,map.get(nums[i])};
}
else{
map.put(target-nums[i], i);
}
}
return new int[0];
}
}
三数之和
题目:
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请
你返回所有和为 0
且不重复的三元组。
**注意:**答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
思路:
- 排序+双指针
- 首先对数组进行排序,排序后固定一个数
nums[i]
,再使用左右指针指向nums[i]后面的两端,数字分别为nums[j]
和nums[k]
,计算三个数的和 sum 判断是否满足为 0,满足则添加进结果 - (重点)如果保证加入到结果数组里面的元素不重复:
- 如果
nums[i] == nums[i−1]
,则说明该数字重复,会导致结果重复,所以应该跳过 - 如果
nums[j] == nums[j-1]
,则说明该数字重复,会导致结果重复,所以应该跳过 - 不找k吗?因为只要有一个
k
满足之后,就会加入到结果中,后面就不会继续遍历k--
了。
- 如果
- 注意可变长的二维数组的定义
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 排序+双指针
Arrays.sort(nums);
int n = nums.length;
List<List<Integer>> ans = new ArrayList<List<Integer>>();
for(int i = 0; i < n; i++){
//保证i不重复
if( i > 0 && nums[i] == nums[i-1]) continue;
//目标值
int target = nums[i];
//遍历j
for(int j = i+1; j < n; j++){
//保证j不重复
if( j > i+1 && nums[j] == nums[j-1]) continue;
//遍历k
int k = n - 1;
while(k > j && nums[k] + nums[j] + target > 0) k--;
if(k == j) break; //没有找到
if(nums[k] + nums[j] + target == 0){
List<Integer> sum = new ArrayList<Integer>();
sum.add(nums[i]);
sum.add(nums[j]);
sum.add(nums[k]);
ans.add(sum);
}
}
}
return ans;
}
}
四数之和
题目:
给你一个由 n
个整数组成的数组 nums
,和一个目标值 target
。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
(若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a
、b
、c
和d
互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1:
输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2:
输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]
思路:
排序+双指针,思路与三数之和类似。
首先对数组进行排序,排序后固定两个个数
nums[i]
和nums[j]
,再使用左右指针指向后面的两端,数字分别为nums[left]
和nums[right]
,计算四个数的和 sum 判断是否满足为 0,满足则添加进结果(重点)如果保证加入到结果数组里面的元素不重复:
- 如果
nums[i] == nums[i−1]
,则说明该数字重复,会导致结果重复,所以应该跳过 - 如果
nums[j] == nums[j-1]
,则说明该数字重复,会导致结果重复,所以应该跳过 - 如果
nums[left] == nums[left+1]
,则说明该数字重复,会导致结果重复,所以应该跳过 - 如果
nums[right] == nums[right-1]
,则说明该数字重复,会导致结果重复,所以应该跳过
- 如果
剪枝:
- 最小的四个数大于target退出循环
- 当前的数,与最后面的三个数小于target,跳出当前循环
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
//四数之和
List<List<Integer>> ans = new ArrayList<List<Integer>>();
Arrays.sort(nums);
int n = nums.length;
//遍历第一重i
for(int i = 0; i < n-3; i++){
//排除重复项
if(i > 0 && nums[i] == nums[i-1]) continue;
//剪枝, 最小的四个数大于target退出循环
if((long)nums[i] + nums[i+1] + nums[i+2] + nums[i + 3] > target) break;
//剪枝,当前的数,与最后面的三个数小于target,跳出当前循环
if((long)nums[i] + nums[n - 3] + nums[n - 2] + nums[n -1] < target) continue;
//遍历第二重循环
for(int j = i + 1; j < n-2; j++){
//排除重复项
if(j > i+1 && nums[j] == nums[j-1]) continue;
//剪枝, 最小的四个数大于target退出循环
if((long)nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;
//剪枝,当前的数,与最后面的两个数小于target,跳出当前循环
if((long)nums[i] + nums[j] + nums[n - 2] + nums[n -1] < target) continue;
//双指针遍历第三个和第四个数
int left = j + 1, right = n - 1;
while(left < right){
long sum = (long)(nums[i] + nums[j] + nums[left] + nums[right]);
//等于目标值,加入ans中
if( sum == target){
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[left]);
list.add(nums[right]);
ans.add(list);
//排除重复项
while(left < right && nums[left] == nums[left+1]) left++;
while(left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
}
//继续往下找
else if(sum < target) left++;
else right--;
}
}
}
return ans;
}
}