LeetCode ACM模式——哈希表篇（一）

刷题顺序及部分思路来源于代码随想录，网站地址：https://programmercarl.com

 部分思路来源于力扣官方题解，作者主页：https://leetcode.cn/u/leetcode-solution/

 

242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例：

输入: s = "anagram", t = "nagaram"
输出: true

import java.util.Scanner;/*** @author light* @Description 有效字母异位词* @create 2023-08-01 13:52*/
public class IsAnagramTest {public static void main(String[] args) {Scanner input=new Scanner(System.in);String str1=input.next();String str2=input.next();boolean res=isAnagram(str1,str2);System.out.println(res);}public static boolean isAnagram(String s, String t) {if(s.length()!=t.length()){return false;}int[] nums=new int[26];for (int i = 0; i < s.length(); i++) {nums[s.charAt(i)-'a']++;}for (int i = 0; i < t.length(); i++) {nums[t.charAt(i)-'a']--;if(nums[t.charAt(i)-'a']<0){return false;}}return true;}
}

49. 字母异位词分组

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

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

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

import java.util.*;/*** @author light* @Description 字母异位词分组*** 方法一：排序* 由于互为字母异位词的两个字符串包含的字母相同，* 因此对两个字符串分别进行排序之后得到的字符串一定是相同的，* 故可以将排序之后的字符串作为哈希表的键。* @create 2023-08-01 14:37*/
public class GroupAnagramsTest {public static void main(String[] args) {Scanner input=new Scanner(System.in);String[] strs=input.next().split(",");List<List<String>> res=groupAnagrams(strs);System.out.println(res);}public static List<List<String>> groupAnagrams(String[] strs){Map<String,List<String>> map=new HashMap<>();for(String str:strs){char[] array=str.toCharArray();Arrays.sort(array);String key=Arrays.toString(array);List<String> list=map.getOrDefault(key,new ArrayList<>());list.add(str);map.put(key,list);}return new ArrayList<List<String>>(map.values());}
}

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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;/*** @author light* @Description 找到字符串中所有字母异位词** 给定两个字符串s和p,找到s中所有p的异位词的子串，返回这些子串的起始索引。* 不考虑答案输出的顺序。* 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。** 滑动窗口解法* 根据题目要求，我们需要在字符串 s 寻找字符串 p 的异位词。* 因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中* 构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；* 当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。** 作者：力扣官方题解* 链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/1123971/zhao-dao-zi-fu-chuan-zhong-suo-you-zi-mu-xzin/* 来源：力扣（LeetCode）* @create 2023-08-01 15:01*/
public class FindAnagramsTest {public static void main(String[] args) {Scanner input=new Scanner(System.in);String s=input.next();String p=input.next();List<Integer> list=findAnagrams(s,p);System.out.println(list);}public static List<Integer> findAnagrams(String s, String p) {if(s.length()<p.length()){return new ArrayList<Integer>();}int[] sCount=new int[26];int[] pCount=new int[26];List<Integer> list=new ArrayList<>();for (int i = 0; i <p.length(); i++) {sCount[s.charAt(i)-'a']++;pCount[p.charAt(i)-'a']++;}if(Arrays.equals(sCount,pCount)){list.add(0);}for (int i = 0; i < s.length() - p.length(); i++) {//维护滑动窗口sCount[s.charAt(i)-'a']--;sCount[s.charAt(i+p.length())-'a']++;if(Arrays.equals(sCount,pCount)){list.add(i+1);}}return list;}
}

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;/*** @author light* @Description 两个数组的交集* @create 2023-08-01 17:34*/
public class IntersectionTest {public static void main(String[] args) {Scanner input=new Scanner(System.in);int n=input.nextInt();int[] nums1=new int[n];int m=input.nextInt();int[] nums2=new int[m];for (int i = 0; i < n; i++) {nums1[i]=input.nextInt();}for (int i = 0; i < m; i++) {nums2[i]=input.nextInt();}int[] res=intersection(nums1,nums2);System.out.println(Arrays.toString(res));}public static int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set=new HashSet<>();Set<Integer> res=new HashSet<>();for(int num:nums1){set.add(num);}for(int num:nums2){if(set.contains(num)){res.add(num);}}int[] arr=new int[res.size()];int i=0;for(int num:res){arr[i++]=num;}return arr;}
}

350. 两个数组的交集 II

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

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;/*** @author light* @Description 两个数组的交集 II* @create 2023-08-01 18:04*/
public class IntersectTest {public static void main(String[] args) {Scanner input=new Scanner(System.in);int n=input.nextInt();int[] nums1=new int[n];int m=input.nextInt();int[] nums2=new int[m];for (int i = 0; i < n; i++) {nums1[i]=input.nextInt();}for (int i = 0; i < m; i++) {nums2[i]=input.nextInt();}int[] res=intersect(nums1,nums2);System.out.println(Arrays.toString(res));}public static int[] intersect(int[] nums1, int[] nums2) {Map<Integer,Integer> map=new HashMap<>();for(int num:nums1){map.put(num,map.getOrDefault(num,0)+1);}int[] res=new int[nums1.length];int i=0;for(int num:nums2){if(map.containsKey(num)&&map.get(num)>0){res[i++]=num;map.put(num,map.get(num)-1);}}return Arrays.copyOfRange(res,0,i);}
}