当前位置：首页 > news >正文

【力扣/代码随想录】哈希表

news 2025/4/30 5:54:11

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
力扣
🤔：使用数组作为哈希表，记录出现的每个字母和次数

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 cur:record){if(cur!=0){return false;}}return true;}
}

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
力扣
🤔：“能否构成”表明magazine可提供的字母和次数需要更多，所以一旦record的元素有<0，就返回false

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] record = new int[26];for(int i=0; i<magazine.length(); i++){record[magazine.charAt(i)-'a']++;}for(int i=0; i<ransomNote.length(); i++){record[ransomNote.charAt(i)-'a']--;if(record[ransomNote.charAt(i)-'a']<0){return false;}}return true;}
}

49. 字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
异位词是由重新排列源单词的所有字母得到的一个新单词。
力扣

❌：使用for循环遍历，List<List<String>>存储结果，使用之前的“有效的字母异位词”判断被遍历的两个字符串，测试用例可以通过，但提交后出现了超时。

❓：
1️⃣ Arrays.sort(Object[] a) 可以对一个数组的所有元素进行排序，并且是按从小到大的顺序。字母异位词排序后的数组是相同的，可以作为哈希表的key。
2️⃣key是否存在、出现过需要用到Java HashMap containsKey() 方法
containsKey() 方法检查 hashMap 中是否存在指定的 key 对应的映射关系。
containsKey() 方法的语法为：
hashmap.containsKey(Object key)
注：hashmap 是 HashMap 类的一个对象。
参数说明：key - 键
返回值：如果 hashMap 中存在指定的 key 对应的映射关系返回 true，否则返回 false。
3️⃣字符串转换为字符的数组；toCharArray()
4️⃣map转换为List；Java HashMap values() 方法，返回 HashMap 中所有 value 值所组成的 collection view(集合视图)。

🤔：使用HashMap，使用排序后的值作为key，判断排序后的值是否在哈希表中出现过，如果没出现，保存key并存储字符串；否则存储到对应的value中

class Solution {public List<List<String>> groupAnagrams(String[] strs) {// 对字符串进行排序，字母异位词的结果相同==》key// 排序：Arrays.sort    是否存在：map.containsKeyMap<String, List<String>> map = new HashMap<>();for(String cur:strs){char[] chars = cur.toCharArray();Array.sort(chars);String key = new String(array);if(!map.containsKey(key)){map.put(key, new ArrayList<>());}map.get(key).add(cur);}return new ArrayList<>(map.values());}
}

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
力扣
🤔：for循环截取子串，参考之前的string转为char[]，然后排序，然后转为string比较进行判断

class Solution {public List<Integer> findAnagrams(String s, String p) {List<Integer> ans = new ArrayList<>();int len = p.length();char[] char_p = p.toCharArray();Arrays.sort(char_p);String array_p = new String(char_p);// substring()for (int i = 0; i < s.length() - len + 1; i++) {String sub_s = s.substring(i, i + len);char[] char_sub = sub_s.toCharArray();Arrays.sort(char_sub);String array_sub = new String(char_sub);if (array_p.equals(array_sub)) {ans.add(i);}}return ans;}
}

🤔：使用滑动窗口

349. 两个数组的交集

给定两个数组 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] 也是可通过的
力扣

🤔：使用set

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set1 = new HashSet<>();for (int i : nums1) {set1.add(i);}Set<Integer> ansSet = new HashSet<>();for (int j : nums2) {if (set1.contains(j)) {ansSet.add(j);}}// 将List<Integer>转换为int[]int[] ans = new int[ansSet.size()];int i =0;for (int cur : ansSet) {ans[i] = cur;i++;}return ans;}
}

350. 两个数组的交集 II

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

class Solution {public int[] intersect(int[] nums1, int[] nums2) {Map<Integer,Integer> map1 = new HashMap<>();for(int key:nums1){if(!map1.containsKey(key)){map1.put(key, 0);}map1.put(key, map1.get(key)+1);}List<Integer> list = new ArrayList<>();for(int key:nums2){if(map1.containsKey(key)&&map1.get(key)>0){list.add(key);map1.put(key, map1.get(key)-1);}}int[] ans = new int[list.size()];for(int i =0; i<list.size(); i++){ans[i]=list.get(i);}return ans;}
}