跟着carl哥的第五天
一般哈希表都是用来快速判断一个元素是否出现集合里
哈希表基础
HashSet简单的理解就是HashSet对象中不能存储相同的数据，存储数据时是无序的。但是HashSet存储元素的顺序并不是按照存入时的顺序（和List显然不同） 是按照哈希值来存的所以取数据也是按照哈希值取得。
做算法题中set的基本用法
Set<Integer> set = new HashSet<>();
set.add(1);
set.contain(i);
set.remove(i);
set.clear();
set.size();
HashMap是一个集合，键值对的集合,源码中每个节点用Node<K,V>表示（键值对）。K唯一
做算法题中map的基本用法
Map<Integer, Integer> map = new HashMap<>();
map.put(key, value);
map.containsKey();
最主要就是记得 它们是能在一个集合中最快查询到某一元素的就行，而且key都是唯一。
先看第一道题
leetcode242.有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例1：
输入：s = "anagram", t = "nagaram"
输出: true
示例2：
输入: s = "rat", t = "car"
输出: false
思路：
这道题只需要记得只有26位小写字母，只需要用数组下标代表每一个字母，且数组的值表示该字母出现多少次并统计即可，最后再遍历一次，检查是否符合题目要求
答案：：：
public class test01 {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String s = in.readLine();
String t = in.readLine();
boolean flag = isAnagram(s, t);
System.out.println(flag);
out.flush();
out.close();
}
private static 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 count : record) {
if (count != 0)
return false;
}
return true;
}
}
再看第二道题
leetcode349. 两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
示例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] 也是可通过的
思路：因为我们要判断数组相交的元素，所以我们就考虑用数组，还是hashset，或者hashmap，数组的话就是O(n2) 如果时hashset或者hashmap会快一点，而且可以注意到的是hashset或者hashmap刚好key都是不可重复的，刚好符合实例1，同时也不用考虑输出顺序，最后用hashset也是因为我们只需要存一个元素，而不需要存储一对，故使用hashset
答案：
public class test02 {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String[] s = in.readLine().split(",");
String[] t = in.readLine().split(",");
int[] arr1 = new int[s.length];
int[] arr2 = new int[t.length];
for (int i = 0; i < s.length; i ++) {
arr1[i] = Integer.parseInt(s[i]);
}
for (int i = 0; i < t.length; i ++) {
arr2[i] = Integer.parseInt(t[i]);
}
int[] result = intersection(arr1, arr2);
out.write(result.toString());
out.flush();
out.close();
}
private static int[] intersection(int[] arr1, int[] arr2) {
if (arr1 == null || arr1.length == 0 || arr2 == null || arr2.length == 0)
return new int[0];
Set<Integer> set = new HashSet<>();
for (int i : arr1) {
set.add(i);
}
Set<Integer> resultSet = new HashSet<>();
for (int i : arr2) {
if (set.contains(i)) {
resultSet.add(i);
}
}
int[] result = new int[resultSet.size()];
int index = 0;
for (Integer item : resultSet) {
result[index ++] = item;
}
return result;
}
}
第三道题
leetcode202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。如果 n 是快乐数就返回 True ；不是，则返回 False 。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
示例：
输入：19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
思路：
题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现。如果重复出现的话用set.contain()就可以判断这个数是不是快乐数
答案：
public class test03 {
static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
Integer n = Integer.parseInt(in.readLine());
boolean flag = isHappy(n);
System.out.println(flag);
}
private static boolean isHappy(Integer n) {
Set<Integer> record = new HashSet<>();
while(n != 1 && !record.contains(n)) {
record.add(n);
n = getNextNumber(n);
}
return n == 1;
}
private static int getNextNumber(Integer n) {
int res = 0;
while(n > 0) {
int temp = n % 10;
res += temp * temp;
n = n / 10;
}
return res;
}
}
最后一道坚持一下！！！！
leetcode1.两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
所以返回 [0, 1]
示例2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例3：
输入：nums = [3,3], target = 6
输出：[0,1]
思路：
这道题就要用hashmap了，因为要返回数组的下标，然后我们还要匹配两个整数，所以用map的key存储整数值，value存储下标。
！！！记住实例三，你错的可能会是这个地方！！！
用for循环遍历一遍数组，然后再判断之前遍历过的元素中的Key有没有刚好时等于（target-nums[i]），有的话存入新数组并返回
答案：
public class test04 {
public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
String s = in.readLine();
String[] str = s.split(",");
int[] nums = new int[str.length];
for (int i = 0; i < str.length; i ++) {
nums[i] = Integer.parseInt(str[i]);
}
int target = Integer.parseInt(in.readLine());
int[] arr = twoSum(nums, target);
out.write(Arrays.toString(arr));
out.flush();
out.close();
}
private static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
int[] res = new int[2];
if (nums.length < 2 || nums == null)
return null;
for (int i = 0; i < nums.length; i ++) {
if (map.containsKey(target - nums[i])) {
res[0] = map.get(target - nums[i]);
res[1] = i;
}
map.put(nums[i], i);
}
return res;
}
}
自我总结
学习了哈希表的基础用法
朋友仍需努力 一起加油
兄弟萌冲啊！
大概就是这样，大家懂了吗 有什么不懂的评论区评论或者私信我吧！！
|