哈希表理论基础
1.根据关键码的值而直接进行访问的数据结构(直白来讲其实数组就是一张哈希表,哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素);
2.哈希表都是用来快速判断一个元素是否出现集合里;
3.哈希函数:把值对应到哈希表的函数;哈希碰撞:映射到哈希表同一个索引下标的位置
4.HashMap,HashSet。
242.有效的字母异位词
题目链接:242.有效的字母异位词
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰有效的字母异位词
日期:2024-09-02
想法:用大小为26数组做哈希表,存s中的字母个数,然后遍历t做减法,再判断数组里是不是全为0即可。
Java代码如下:
class Solution {
public boolean isAnagram(String s, String t) {
int[] record = new int[26];
for (int i = 0; i < s.length(); i++) {
record[s.charAt(i) - 'a']++;
}
for (int i = 0; i < t.length(); i++) {
record[t.charAt(i) - 'a']--;
}
for(int count : record){
if(count != 0){
return false;
}
}
return true;
}
}
总结:哈希表最简单的形式-数组,还有ASC码的运用。
349. 两个数组的交集
题目链接:349. 两个数组的交集
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰两个数组的交集
日期:2024-09-02
想法:可以用数组,但要考虑数组里数字的大小,数字太大了导致数组太长,这里用HashSet,将nums1的值加到集合里,对比nums2的内容,最后注意输出数组就行
Java代码如下:
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
Set<Integer> resSet = new HashSet<>();
for (int i : nums1) {
set1.add(i);
}
for (int i : nums2) {
if (set1.contains(i)) {
resSet.add(i);
}
}
int[] result = new int[resSet.size()];
int j = 0;
for(int i : resSet){
result[j++] = i;
}
return result;
}
}
总结:初见用集合做哈希表,一次只存一个数。
202. 快乐数
题目链接:202. 快乐数
文档讲解︰代码随想录(programmercarl.com)
日期:2024-09-02
想法:快乐数的计算方法一直走下去只会有两种结果,一是确定能变成1,二是循环,而循环就是看有没有值重复,用哈希表记录下就行了。
Java代码如下:
class Solution {
private int getSum(int n) {
int sum = 0;
while (n > 0) {
sum += (n % 10)* (n % 10);
n = n / 10;
}
return sum;
}
public boolean isHappy(int n) {
Set<Integer> record = new HashSet<>();
while (true) {
int sum = getSum(n);
if(sum == 1){
return true;
}
if(record.contains(sum)){
return false;
}else{
record.add(sum);
}
n = sum;
}
}
}
总结:注意下计算各位的平方和计算。
1. 两数之和
题目链接:1. 两数之和
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰两数之和
日期:2024-09-02
想法:对于数组里的一个数,我们要确定有没有另外一个数能和它加起来得到target,这个数是可以算出来的。我们就考虑依次遍历数组,用一个数据结构来保存遍历过的数,如果有能对上的数就输出,问题在于要知道这个数及其它的在原本数组中的角标,需要2个值,set这是就不行了,得用map。
Java代码如下:
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> indexMap = new HashMap<>();
for(int i = 0; i < nums.length; i++){
if(indexMap.containsKey(target - nums[i])){
int[] result = new int []{i, indexMap.get(target - nums[i])};
return result;
} else{
indexMap.put(nums[i], i);
}
}
return null;
}
}
总结:思路是比较简单的,注意Java一些表达的问题,用的比较少。
标签:202,return,数组,int,sum,随想录,哈希,new,两数 From: https://www.cnblogs.com/wowoioo/p/18393577