湖北seo网站多少钱,wordpress怎么映射到外网,wordpress支付宝付费,大品牌vi设计哈希表基础课程笔记
1. 什么是哈希表
哈希表#xff08;Hash Table#xff09;又称为散列表#xff0c;是一种基于关键码#xff08;Key#xff09;直接进行访问的数据结构。简单理解#xff0c;数组其实也是一种哈希表。哈希表通过关键码映射到数组的索引#xff0c;…哈希表基础课程笔记
1. 什么是哈希表
哈希表Hash Table又称为散列表是一种基于关键码Key直接进行访问的数据结构。简单理解数组其实也是一种哈希表。哈希表通过关键码映射到数组的索引从而实现快速访问。
1.1 哈希表的应用
哈希表主要用于快速判断某个元素是否存在于集合中。例如查询一个名字是否在学校名单中。哈希表可以将查找时间复杂度降低到 ( O(1) )。
2. 哈希函数
哈希函数用于将关键码如学生姓名映射到哈希表的索引位置。常见做法是将关键码通过特定编码转化为数值hashCode再通过取模操作将其限制在哈希表范围内。
2.1 哈希函数处理
如果 hashCode 得到的数值大于哈希表大小需要取模操作 hashCode % tableSize。哈希表大小过小时即使哈希函数均匀分布仍可能导致多个关键码映射到相同索引形成哈希碰撞。
3. 哈希碰撞
哈希碰撞是指不同的关键码映射到相同的哈希表索引位置。例如小李和小王都映射到索引 1。常用的解决方法包括
3.1 拉链法
将发生冲突的元素存储在链表中通过索引快速访问链表即可。
3.2 线性探测法
利用哈希表中的空位解决碰撞问题。如果索引位置发生冲突则继续查找下一个空位放置数据。
242. 有效的字母异位词
题目描述
给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s anagram, t nagaram 输出: true
示例 2:
输入: s rat, t car 输出: false
说明: 你可以假设字符串只包含小写字母。
解题思路 创建一个大小为 26 的数组 record用于记录每个字母出现的次数。 因为题目说明字符串只包含小写字母所以每个字母都可以通过 char - a 得到一个 0 到 25 之间的索引对应到数组 record 中。 遍历字符串 s增加对应字母的计数。 对于 s 中的每个字符通过 record[s.charAt(i) - a] 来记录每个字母的出现次数。 遍历字符串 t减少对应字母的计数。 对于 t 中的每个字符通过 record[t.charAt(i) - a]-- 来减少每个字母的出现次数。如果在此过程中发现某个字符的计数小于 0说明 t 中出现了 s 中没有的字符返回 false。 遍历数组 record 检查所有计数是否为 0。 如果数组中每个位置的计数都是 0则说明 t 是 s 的字母异位词否则返回 false。
代码实现
class Solution {public boolean isAnagram(String s, String t) {// 如果两个字符串长度不相等直接返回 falseif (s.length() ! t.length()) {return false;}int[] record new int[26];// 记录 s 中每个字符的出现次数for (int i 0; i s.length(); i) {record[s.charAt(i) - a];}// 减去 t 中每个字符的出现次数for (int i 0; i t.length(); i) {record[t.charAt(i) - a]--;// 如果出现某个字符计数小于 0说明 t 中有多余字符if (record[t.charAt(i) - a] 0) {return false;}}// 检查所有计数是否为 0for (int count : record) {if (count ! 0) {return false;}}return true;}
}349. 两个数组的交集
题目描述
给定两个数组编写一个函数来计算它们的交集。
示例:
输入: nums1 [1,2,2,1], nums2 [2,2] 输出: [2]
输入: nums1 [4,9,5], nums2 [9,4,9,8,4] 输出: [9,4] (结果中的每个元素都是唯一的顺序可以是任意的)
解题思路 处理特殊情况 首先判断输入数组是否为空或长度为 0如果是则直接返回空数组。 使用集合Set去重并快速查找 使用 Set 数据结构将 nums1 中的所有元素存入 set1从而去重。遍历 nums2 数组检查其中每个元素是否在 set1 中如果在将其添加到结果集合 resultset 中。Set 可以确保结果中的元素都是唯一的。 将结果集合转换为数组并返回 最后将 resultset 中的元素转换成数组返回。
反思
命名规范
在编写代码时应当遵循驼峰命名法。例如resultset 应改为 resultSet以提高代码的可读性。
length 属性不需要小括号
在 Java 中数组的 length 是一个属性而不是一个方法因此不需要小括号。要注意区分这类细节避免出现不必要的错误。
代码优化
resultset.stream().mapToInt(x - x).toArray() 是一种方便的方式将集合转换为数组比手动遍历转换更简洁和高效。
这道题展示了集合在处理数组去重和交集问题中的高效性是一个典型的应用案例。
代码实现
import java.util.Set;
import java.util.HashSet;class Solution {public int[] intersection(int[] nums1, int[] nums2) {// 处理特殊情况if (nums1 null || nums1.length 0 || nums2 null || nums2.length 0) {return new int[0];}// 使用集合去重并存储元素SetInteger set1 new HashSet();SetInteger resultset new HashSet();// 将 nums1 中的元素添加到 set1 中for (int i : nums1) {set1.add(i);}// 检查 nums2 中的元素是否在 set1 中for (int i : nums2) {if (set1.contains(i)) {resultset.add(i);}}// 将结果集合转换为数组并返回return resultset.stream().mapToInt(x - x).toArray();}
}202. 快乐数
题目描述
编写一个算法来判断一个数 n 是不是快乐数。
快乐数 定义为对于一个正整数每一次将该数替换为它每个位置上的数字的平方和然后重复这个过程直到这个数变为 1也可能会进入一个无限循环始终变不到 1。如果可以变为 1那么这个数就是快乐数。
如果 n 是快乐数就返回 true不是则返回 false。
示例
输入: 19输出: true
解释 1² 9² 82 8² 2² 68 6² 8² 100 1² 0² 0² 1
解题思路 定义一个辅助函数 pingfanghe(int n) 该函数用于计算 n 每一位数字的平方和。例如19 的平方和为 1² 9² 82。 使用一个循环将 n 逐位处理并计算每位的平方和。 使用集合 (Set) 检测循环 为了避免程序进入无限循环我们可以用 Set 来存储每次计算得到的平方和。如果在计算过程中发现某个平方和已经存在于 Set 中说明进入了循环直接返回 false。 循环判断 在每次循环中计算 n 的平方和。如果平方和等于 1返回 true表示是快乐数。如果平方和已经存在于 Set 中说明进入了无限循环返回 false。
反思
得更新 n 的值在每次循环中必须更新 n 的值为当前的平方和确保能够继续正确地进行计算。注意 pingfanghe 方法的除法逻辑应直接使用 n / 10 来更新 n 的值从而正确计算每一位数字。
代码实现
class Solution {public int pingfanghe(int n){int sum0;int num n;int dis 0;while(num0){dis num%10;sum sum dis*dis;num (num-dis)/10;}return sum;}public boolean isHappy(int n) {SetInteger set1 new HashSet();int sum pingfanghe(n);while(sum!1){if(set1.contains(sum)){return false;}else{set1.add(sum);sum pingfanghe(sum);}}return true;}
}1. 两数之和
题目描述
给定一个整数数组 nums 和一个目标值 target请你在该数组中找出和为目标值的那 两个 整数并返回它们的数组下标。
注意
你可以假设每种输入只会对应一个答案。数组中同一个元素不能使用两遍。
示例:
输入: nums [2, 7, 11, 15], target 9输出: [0, 1] 解释: nums[0] nums[1] 2 7 9
解题思路 使用哈希表 (HashMap) 记录已经遍历过的元素 遍历数组 nums对于每个元素 nums[i]计算 target - nums[i] 的差值 diff。检查哈希表中是否存在 diff。 如果存在则说明找到了两个数返回它们的下标。如果不存在则将当前的元素 nums[i] 及其下标 i 存入哈希表中。 使用哈希表的优势 通过哈希表可以在遍历过程中立即找到与当前元素配对的目标数从而在 O(1) 时间复杂度内完成查找。整体算法的时间复杂度为 O(n)。
代码实现
class Solution {public int[] twoSum(int[] nums, int target) {MapInteger,Integer map1 new HashMap();for(int i0;inums.length;i){int dis target-nums[i];if(map1.containsKey(dis)){return new int []{i, map1.get(dis)};}else{map1.put(nums[i],i);}}return null;}
}
