leetCode - - - 哈希表

目录

1.模拟行走机器人（LeetCode 874）

2.数组的度（LeetCode 697）

3.子域名访问次数（LeetCode 811）

4.字母异位词分组（LeetCode 49）

5.小结

1.常见的哈希表实现

2.遍历Map

---

1.模拟行走机器人（LeetCode 874）

机器人在一个无限大小的 XY 网格平面上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 commands ：

• -2 ：向左转 90 度
• -1 ：向右转 90 度
• 1 <= x <= 9 ：向前移动 x 个单位长度

在网格上有一些格子被视为障碍物 obstacles 。第 i 个障碍物位于网格点  obstacles[i] = (xi, yi) 。

机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，并继续执行下一个命令。

返回机器人距离原点的 最大欧式距离 的 平方 。（即，如果距离为 5 ，则返回 25 ）

注意：

• 北方表示 +Y 方向。
• 东方表示 +X 方向。
• 南方表示 -Y 方向。
• 西方表示 -X 方向。
• 原点 [0,0] 可能会有障碍物。

示例 1：

输入：commands = [4,-1,3], obstacles = []
输出：25
解释：
机器人开始位于 (0, 0)：
1. 向北移动 4 个单位，到达 (0, 4)
2. 右转
3. 向东移动 3 个单位，到达 (3, 4)
距离原点最远的是 (3, 4) ，距离为 32 + 42 = 25

class Solution {public int robotSim(int[] commands, int[][] obstacles) {// 初始化结果int result = 0;// 从原点（ 0 ，0 ）位置开始出发int x = 0, y = 0;// 机器人前进的方向// 初始方向：正北int direction = 0;// 定义四个方向int[][] direxy = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 障碍物有多个，所以需要有一个障碍物坐标点集合// 使用 集合 Set 存储障碍物的坐标，用来检查下一步是否受阻// 机器人每试图走一个位置，就用此位置与障碍物集合列表里的坐标进行比较，看是否刚好是障碍物坐标点HashSet<String> obstaclesSet = new HashSet<String>();// 存储障碍物坐标点for (int[] obs : obstacles) {// 以坐标的形式存储obstaclesSet.add(obs[0] + "," + obs[1]);}// 机器人开始行走for (int com : commands) {// -2：向左转 90 度if (com == -2) {direction = (direction == 0) ? 3 : direction - 1;// -1：向右转 90 度} else if (com == -1) {direction = (direction == 3) ? 0 : direction + 1;// 1 <= x <= 9 ：向前移动 x 个单位长度} else {// 没有遇到障碍物，一直往前走 com 个单位长度while (com-- > 0 && !obstaclesSet.contains((x + direxy[direction][0]) + "," + (y + direxy[direction][1]))) {x += direxy[direction][0];y += direxy[direction][1];}// 机器人停下来后开始计算最大欧式距离的平方// 更新结果result = Math.max(result, x * x + y * y);}}return result;}
}

知识点：

1. 二维数组的使用
定义：int[] obs 表示一个一维数组，每个 obs 是 obstacles 数组的元素。obstacles 是一个二维数组，其中的每个元素都是表示障碍物坐标的数组。
访问元素：通过 obs[0] 和 obs[1] 可以访问障碍物的 x 和 y 坐标。
2. 集合（HashSet）的使用
定义：HashSet 是一个集合类，它不允许重复的元素，并且提供了高效的查找、添加和删除操作。
用法：在这里，obstaclesSet 被用来存储障碍物的坐标，以便快速查找。这种存储方式提高了查找效率，尤其是在处理大量障碍物数据时。
3. 字符串的连接
操作：obs[0] + "," + obs[1] 将 x 和 y 坐标值转换为字符串格式 "x,y"。这种格式使得坐标可以被轻松地存储和比较。
应用：将坐标以字符串形式存储到 HashSet 中，便于进行后续的查找和操作。
4. 增强的 for 循环
定义：for (int[] obs : obstacles) 是 Java 的增强型 for 循环（或称为 foreach 循环），它用于遍历数组或集合中的每一个元素。
用法：这使得遍历 obstacles 数组中的每个障碍物坐标变得简单和直观。
5. 坐标系统
概念：x 和 y 坐标用于表示二维空间中的位置。在代码中，obs[0] 和 obs[1] 分别代表 x 和 y 坐标值。

---

2.数组的度（LeetCode 697）

给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1：

输入：nums = [1,2,2,3,1]
输出：2
解释：
输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
连续子数组里面拥有相同度的有如下所示：
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。

示例 2：

输入：nums = [1,2,2,3,1,4,2]
输出：6
解释：
数组的度是 3 ，因为元素 2 重复出现 3 次。
所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。

解题思路：

1.哈希表：使用 HashMap 存储每个元素的出现次数及其最早和最后出现的位置。
2.数组遍历：通过遍历数组来填充哈希表的信息。
3.度量最大出现次数：在哈希表中查找出现次数最多的元素。（第一次遍历）
4.计算最短子数组长度：遍历哈希表，找到包含出现次数最多元素的最短子数组。（第二次遍历）

知识点运用：

Map.Entry 是 Map 接口中的一个嵌套接口，表示 Map 中的一个键值对。
1.主要方法：
getKey()：获取 Map.Entry 的键。
getValue()：获取 Map.Entry 的值。
setValue(V value)：设置 Map.Entry 的值。
2.遍历 Map：最常用的方式是通过 entrySet() 方法，该方法返回 Map 中所有键值对的集合（Set<Map.Entry<K, V>>）。

Map<String, Integer> map = new HashMap<>();
map.put("apple", 3);
map.put("banana", 2);for (Map.Entry<String, Integer> entry : map.entrySet()) {String key = entry.getKey();Integer value = entry.getValue();System.out.println(key + ": " + value);
}

解题代码： 

class Solution {public int findShortestSubArray(int[] nums) {// 初始化长度为一个大数值，方便后续更新int minLength = Integer.MAX_VALUE;// Map存储每个元素的出现次数及其最早和最晚出现位置Map<Integer, int[]> map = new HashMap<>();// 遍历数组，统计每个元素的信息for (int i = 0; i < nums.length; i++) {if (map.containsKey(nums[i])) {int[] value = map.get(nums[i]);value[0]++; // 增加出现次数value[2] = i; // 更新最后出现的位置} else {// 第一次出现该元素map.put(nums[i], new int[]{1, i, i});}}// 计算数组中出现次数最多的元素int maxTimes = 0;for (int[] value : map.values()) {maxTimes = Math.max(maxTimes, value[0]);}// 再次遍历map来找到最短长度for (Map.Entry<Integer, int[]> entry : map.entrySet()) {int[] value = entry.getValue();if (value[0] == maxTimes) {minLength = Math.min(minLength, value[2] - value[1] + 1);}}return minLength;}
}

---

3.子域名访问次数（LeetCode 811）

网站域名 "discuss.leetcode.com" 由多个子域名组成。顶级域名为 "com" ，二级域名为 "leetcode.com" ，最低一级为 "discuss.leetcode.com" 。当访问域名 "discuss.leetcode.com" 时，同时也会隐式访问其父域名 "leetcode.com" 以及 "com" 。

计数配对域名 是遵循 "rep d1.d2.d3" 或 "rep d1.d2" 格式的一个域名表示，其中 rep 表示访问域名的次数，d1.d2.d3 为域名本身。

• 例如，"9001 discuss.leetcode.com" 就是一个 计数配对域名 ，表示 discuss.leetcode.com 被访问了 9001 次。

给你一个 计数配对域名 组成的数组 cpdomains ，解析得到输入中每个子域名对应的 计数配对域名 ，并以数组形式返回。可以按 任意顺序 返回答案。

示例 1：

输入：cpdomains = ["9001 discuss.leetcode.com"]
输出：["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
解释：例子中仅包含一个网站域名："discuss.leetcode.com"。
按照前文描述，子域名 "leetcode.com" 和 "com" 都会被访问，所以它们都被访问了 9001 次。

示例 2：

输入：cpdomains = ["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
输出：["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
解释：按照前文描述，会访问 "google.mail.com" 900 次，"yahoo.com" 50 次，"intel.mail.com" 1 次，"wiki.org" 5 次。
而对于父域名，会访问 "mail.com" 900 + 1 = 901 次，"com" 900 + 50 + 1 = 951 次，和 "org" 5 次。

class Solution {public List<String> subdomainVisits(String[] cpdomains) {// 使用哈希表记录每个子域名的计数Map<String, Integer> map = new HashMap<>();// 遍历数组for (String s : cpdomains) {// 获取当前字符串的长度int n = s.length();// 每个字符串都是由数字 + 域名组成// 先去获取这个字符串中的数字// 从 0 开始，向后扫描到空格位置int idx = 0;// 从前向后扫描到空格位置while (idx < n && s.charAt(idx) != ' ') idx++;// 截取出数字来// tips: substring() 方法返回字符串的子字符串// beginIndex -- 起始索引（包括）, 索引从 0 开始// endIndex -- 结束索引（不包括）int cnt = Integer.parseInt(s.substring(0, idx));// 从后往前处理域名部分，直到处理完毕int start = idx + 1; // 从后往前处理域名部分idx = n - 1;// 直到处理完毕while (idx >= start) {// 每个域名由多个子域名组成// 通过 . 来截取while (idx >= start && s.charAt(idx) != '.') idx--;// 获取当前子域名String cur = s.substring(idx + 1);// 更新这个子域名的计数map.put(cur, map.getOrDefault(cur, 0) + cnt);// idx 继续向前移动idx--;}}// 从哈希表中构造出数组答案来List<String> ans = new ArrayList<>();// keySet() 方法返回映射中所有 key 组成的 Set 视图for (String key : map.keySet()) {// key 是域名，map.get(key) 获取 valueans.add(map.get(key) + " " + key);}// 返回结果return ans;}
}

区别keySet() 和 entrySet()
keySet():
返回 Map 中所有键的集合 (Set<K>).
适合只需要处理键的情况。例如，只需要检查键是否存在或者只需要获取键的列表。
entrySet():
返回 Map 中所有键值对的集合 (Set<Map.Entry<K, V>>).
更适合同时需要访问键和值的情况。通过 Map.Entry<K, V> 对象可以直接访问键和值，提高效率

for (String key : map.keySet()) {System.out.println(key + " -> " + map.get(key));
}for (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + " -> " + entry.getValue());
}

---

4.字母异位词分组（LeetCode 49）

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

做题思路：

1.遍历所有字符串，计算每个字符串的字符频次。
2.将频次转换为唯一的键，并使用哈希表将具有相同键的字符串分组。
3.返回哈希表中所有分组的值，即字母异位词的分组结果

较为严谨的解法：不确定每个字符串是否可以有重复的字符，这里计算了每个字符出现的频次

class Solution {public List<List<String>> groupAnagrams(String[] strs) {Map<String,List<String>> map=new HashMap<String,List<String>>();for(String str:strs){// count 代表每个小写字母出现的频次int[] count=new int[26];// 利用 for 循环，统计 str 当中每个字母出现的频次for(int i=0;i<str.length();i++){count[str.charAt(i) -'a']++;}StringBuffer sb=new StringBuffer();// // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键for(int i=0;i<26;i++){if(count[i]!=0){// 先记录字母，比如记录了字母 ksb.append((char)(i+'a'));// 再记录次数，比如记录了次数 9sb.append(count[i]);}}// 转换为字符串的形式，比如为 a1c9q7String key=sb.toString();// 在哈希表 map 当中找出这个 key 对应的字符串 str 来// 1、如果有这个 key，那么这个 key 对应的 数组 会新增一个 str 进去// 2、如果没有这个 key，那么会初始化一个数组，用来新增这个 strList<String> list=map.getOrDefault(key,new ArrayList<String>());list.add(str);map.put(key,list);}//return new ArrayList<>(map.values());return  new ArrayList<List<String>>(map.values()); }
}

力扣给的通过率最高的解法：默认每个字符串中不会出现重复的字母

class Solution {public List<List<String>> groupAnagrams(String[] strs) {HashMap<String, List<String>> hashMap = new HashMap<>();for (String str : strs) {char[] charArray = str.toCharArray();Arrays.sort(charArray);String key = new String(charArray);List<String> list = hashMap.getOrDefault(key, new ArrayList<String>());list.add(str);hashMap.put(key, list);}return  new ArrayList<>(hashMap.values());}
}

---

5.小结

1.常见的哈希表实现

HashMap:

用于存储键值对，每个键（key）与一个值（value）相关联。

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);
int value = map.get("apple");

使用：使用 HashMap 统计元素出现的次数

Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {map.put(num, countMap.getOrDefault(num, 0) + 1);
}

HashSet：

适用于需要存储唯一元素的场景（类似于 HashMap 的键部分）

Set<String> set = new HashSet<>();
set.add("apple");
boolean exists = set.contains("apple"); // true

使用：通过 HashSet 快速查找元素是否出现过

Set<Integer> set = new HashSet<>();
for (int num : nums) {if (!set.add(num)) {// 如果返回 false，说明 num 已经存在}

2.遍历Map

entrySet() 是最常用的方法，适合遍历 Map 中的键值对。
keySet() 和 values() 方法适合只需要键或值时使用。

 // 遍历 entrySet()for (Map.Entry<String, Integer> entry : map.entrySet()) {String key = entry.getKey();Integer value = entry.getValue();System.out.println("Key: " + key + ", Value: " + value);}// 遍历 keySet()
for (String key : map.keySet()) {Integer value = map.get(key);System.out.println("Key: " + key + ", Value: " + value);
}// 遍历 values()
for (Integer value : map.values()) {System.out.println("Value: " + value);
}