网站建设存在四个问题,html国庆节网页制作代码,怎么设置网站的关键字,更改wordpress前缀哈希表基础知识
哈希表
哈希表关键码就是数组的索引下标#xff0c;然后通过下标直接访问数组中的元素#xff1b;数组就是哈希表的一种 一般哈希表都是用来快速判断一个元素是否出现集合里。例如要查询一个名字是否在班级里#xff1a;
要枚举的话时间复杂度是O(n)…哈希表基础知识
哈希表
哈希表关键码就是数组的索引下标然后通过下标直接访问数组中的元素数组就是哈希表的一种 一般哈希表都是用来快速判断一个元素是否出现集合里。例如要查询一个名字是否在班级里
要枚举的话时间复杂度是O(n)但如果使用哈希表的话 只需要O(1)
哈希函数
把学生的姓名直接映射为哈希表上的索引然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。哈希函数如下图所示通过hashCode把名字转化为数值一般hashcode是通过特定编码方式可以将其他数据格式转化为不同的数值这样就把学生名字映射为哈希表上的索引数字了。 如果hashCode得到的数值大于 哈希表的大小了此时为了保证映射出来的索引数值都落在哈希表上会在再次对数值做一个取模的操作这样我们就保证了学生姓名一定可以映射到哈希表上了。
但就算哈希函数计算的再均匀也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。这就造成了哈希碰撞 哈希碰撞
如图所示小李和小王都映射到了索引下标 1 的位置这一现象叫做哈希碰撞。 一般哈希碰撞有两种解决方法 拉链法和线性探测法。
拉链法
当小李和小王在索引1的位置发生了冲突发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了数据规模是dataSize 哈希表的大小为tableSize 线性探测法
使用线性探测法一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置放了小李那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize 要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示 常见的三种哈希结构 在Java中哈希结构是一种基于哈希表的数据结构主要用于快速查找和存取数据。常见的哈希结构包括数组、集合和映射。以下是它们的定义、特性以及使用场景的介绍。 数组Array
定义数组是一种线性数据结构用于存储固定数量的同类型元素。它提供了通过索引快速访问元素的能力。特性数组的大小在创建时就已确定且之后不能改变。数组在内存中连续分配空间这有助于快速访问元素。使用场景当你需要快速随机访问元素并且知道元素的数量时数组是一个不错的选择。例如处理固定大小的列表、缓冲区或矩阵。 集合Collection)
定义集合是Java集合框架的一部分它提供了一组接口和类用于存储和操作一组对象。集合框架包括List、Set等多种类型。
特性集合框架提供了丰富的操作如添加、删除、遍历元素等。集合可以动态增长和缩小不需要预先指定大小。
使用场景集合适用于存储和管理一组对象的场景尤其是当对象的数量未知或可能变化时。例如存储用户列表、日志消息或任何动态集合的数据。 映射Map
定义映射是一种键值对的集合它允许通过唯一的键快速检索值。Java中的Map接口及其实现类如HashMap、TreeMap等提供了这种功能。
特性每个键最多映射到一个值键不能重复。映射提供了快速的查找、插入和删除操作。
使用场景映射适用于需要通过键来快速检索值的场景。例如在数据库查询结果映射、实现属性文件解析、缓存数据等方面非常有用。 算法题
Leetcode 242.有效的字母异位词
题目链接:242.有效的字母异位词
大佬视频讲解有效的字母异位词视频讲解 个人思路
利用哈希表结构先遍历一遍a存字符数量到辅助数组然后再遍历一遍b查值并删除对应字符数量最后遍历一遍这个辅助数组如果有字符数量不为0则不为异位词。 解法
哈希数组
定义一个数组叫做help用来上记录字符串s里字符出现的次数。因为只包括小写字母所以直接字符a映射为下标0相应的字符z映射为下标25。再遍历 字符串s的时候只需要将 s[i] - ‘a’ 所在的元素做1 操作即可就能求出一个字母对应出现次数。 然后在遍历字符串t 的时候对t中出现的字符映射哈希表索引上的数值做-1的操作。那么最后检查一下help数组如果有的元素不为零0说明字符串s和t一定是谁多了字符或者谁少了字符。最后如果help数组所有元素都为零0说明字符串s和t是字母异位词return true。
class Solution {public boolean isAnagram(String s, String t) {int[] helpnew int[26];//辅助数组for(int i 0;is.length();i){ // 求出字符串s对应字母的存在个数help[s.charAt(i) -a] ;}for(int i 0;it.length();i){help[t.charAt(i) -a] --;}for(int i0;ihelp.length;i){ // help数组如果有的元素不为零0说明字符串s和t 一定是谁多了字符或者谁少了字符。if(help[i]!0){return false;}}return true; // help数组所有元素都为零0说明字符串s和t是字母异位词}
}
时间复杂度:O(nlog n)3个for循环
空间复杂度:O(1);没常量大小的辅助数组 Leetcode 349. 两个数组的交集
题目链接:349.两个数组之间的交集
大佬视频讲解两个数组之间的交集视频讲解 个人思路
因为结果要求不重复那可以用set集合先用一个hashSet存取数组1的值再看这个hashSet中是否包含数组2的值如果包含则将数字放入结果集中 解法
哈希集合
这道题目没有限制数值的大小就无法使用数组来做哈希表了。而且如果哈希值比较少、特别分散、跨度非常大使用数组就造成空间的极大浪费。
但如果所有题目都直接使用set 不仅占用空间比数组大而且速度要比数组慢set把数值映射到key上都要做hash计算的。在数据量大的情况差距是非常明显的。 class Solution {public int[] intersection(int[] nums1, int[] nums2) {//nums1 null判断数组引用是否被初始化//nums1.length 0 判断数组已经初始化后是否有元素if(nums1 null || nums1.length 0 || nums1 null || nums1.length 0 ){return new int[0];}SetInteger setNum1new HashSet();SetInteger resultnew HashSet();for(int i0;inums1.length;i){//遍历数组1存值setNum1.add(nums1[i]);}for(int num:nums2){ //遍历数组2的过程中判断哈希表中是否存在该元素if(setNum1.contains(num)){result.add(num);}}return result.stream().mapToInt(x - x).toArray();//将结果集合转为数组}
}
//最后return的数组也可以另外申请一个数组存放setRes中的元素int[] arr new int[resSet.size()];int j 0;for(int i : resSet){arr[j] i;} 时间复杂度:O(n)两个不嵌套的for循环
空间复杂度:O(n);使用多两个set Leetcode 202. 快乐数
题目链接:https://leetcode.cn/problems/happy-number/description/ 个人思路
快乐数中一个很重要的定义平方和就是不能重复否则会无限循环那可以使用hashSet来解决这道题。 解法
哈希集合
当遇到了要快速判断一个元素是否出现集合里的时候就要考虑哈希法。所以这道题目使用哈希法来判断这个sum是否重复出现如果重复了就是return false 否则一直找到sum为1为止。 class Solution {public boolean isHappy(int n) {SetInteger resnew HashSet();//1本身就是快乐数//这个过程结果不能重复出现不然会无限循环while(n!1 !res.contains(n)){res.add(n);ncomput(n);//计算每个位置上的平方和}return n1;}public int comput(int n){int sum0;while(n0){int temp n%10;//求余数sumtemp*temp;//累加平方和nn/10;//从个位到十位到百位到...}return sum;}
}
时间复杂度:O( n)模内层循环comput对于每个n它会执行n次因为它是对n的每一位数字进行平方然后求和
空间复杂度:O(n); 在最坏的情况下HashSet可能会存储所有小于等于n的数字因此空间复杂度为O(n Leetcode 1. 两数之和
题目链接:1. 两数之和 大佬视频讲解两数之和 视频讲解 个人思路
因为既要求下标又要求值可以考虑使用哈希映射这个结构 解法
哈希映射
在使用map时要明确两点
1.map用来做什么
map目的用来存放我们访问过的元素因为遍历数组的时候需要记录我们之前遍历过哪些元素和对应的下标这样才能找到与当前元素相匹配的也就是相加等于target
2.map中key和value分别表示什么
因为需要判断元素是否出现还要真的元素的下标所以 map中的存储结构为 {key数据元素value数组元素对应的下标}。
然后在遍历数组的时候只需要向map去查询是否有和目前遍历元素匹配的数值如果有就找到的匹配对如果没有就把目前遍历的元素放进map中 class Solution {public int[] twoSum(int[] nums, int target) {int[] resnew int[2]; //nums null判断数组引用是否被初始化//nums.length 0 判断数组已经初始化后是否有元素if(numsnull || nums.length0){return res;}MapInteger,Integer mapXnew HashMap();//key存数组值value存数组下标for(int i0;inums.length;i){int temptarget-nums[i];if(mapX.containsKey(temp)){// 遍历当前元素并在map中寻找是否有匹配的keyres[0]i;res[1]mapX.get(temp);break;}mapX.put(nums[i],i); // 如果没找到匹配对就把访问过的元素和下标加入到map中}return res;}
}
时间复杂度:O(n)一个for循环
空间复杂度:O(n);使用map 以上是个人的思考反思与总结若只想根据系列题刷参考卡哥的网址代码随想录算法官网
