您的位置:首页 > 房产 > 建筑 > 代码随想录算法训练营第六天|242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

代码随想录算法训练营第六天|242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

2024/12/23 8:50:10 来源:https://blog.csdn.net/Yinems/article/details/139981971  浏览:    关键词:代码随想录算法训练营第六天|242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

打卡Day6

  • 1.哈希表理论基础
  • 2.242.有效的字母异位词
  • 2.349. 两个数组的交集
  • 3.202. 快乐数
  • 4.1. 两数之和

1.哈希表理论基础

文档讲解: 代码随想录

当遇到要快速判断一个元素是否出现在集合中时,要考虑哈希法。但是哈希法牺牲了空间换取了时间,因为要使用额外的数组、set、map来存放数据,才能实现快速的查找。

2.242.有效的字母异位词

题目链接:有效的字母异位词
文档讲解: 代码随想录

思路:新建两个数组存储s和t中字符出现的频率,依次进行比较。我用了之前209.长度最小的子数组的思路。

class Solution {public boolean isAnagram(String s, String t) {char[] sAr = s.toCharArray();char[] tAr = t.toCharArray();int sLen = s.length();int tLen = t.length();int[] ss = new int[128];int[] tt = new int[128];for(int i = 0; i < sLen; i++){ss[sAr[i]]++;}for(int i = 0; i < tLen; i++){tt[tAr[i]]++;}for(int i = 0; i < 128; i++){if(ss[i] != tt[i]){return false;}}return true;}
}

标答的思路改进:新建一个数组,记录s中字符出现的频率,数组的大小只需要26就行。数组是一个简单的哈希表,需要把字符映射到数组也就是哈希表的索引下标上。在遍历t的时候,对t中出现的字符映射到哈希表索引上的数值做-1操作。最后检查记录数组的元素是否全为0。

class Solution {public boolean isAnagram(String s, String t) {int[] record = new int[26];int sLen = s.length();int tLen = t.length();for(int i = 0; i < sLen; i++){record[s.charAt(i) - 97]++;}for(int i = 0; i < sLen; i++){record[t.charAt(i) - 97]--;}//for(variable : collection) statementfor(int i: record){if(i != 0){return false;}}return true;}
}

时间复杂度都为O(M+N)

2.349. 两个数组的交集

题目链接:两个数组的交集
文档讲解: 代码随想录

注意点:
(1)nums1 == null 和 nums.length == 0 的区别
nums1 = null 意味着数组变量并没有指向任何有效的数组对象,不占用内存空间,指针为空;
nums.length = 0 意味着nums 是一个有效的数组对象,但数组中并没有任何元素。
(2)使用数组来做哈希的题目是因为题目限制了数值的大小。这道题如果用数组做,思路为统计每个数出现的频率,若某个数字出现的频率在两个数组中都大于0,则该数字属于交集。

import java.util.HashSet;
import java.util.Set;class Solution {public int[] intersection(int[] nums1, int[] nums2) {if(nums1 == null || nums1.length == 0 || nums2.length == 0 || nums2 == null){return new int[0];}Set<Integer> set1 = new HashSet();Set<Integer> resSet = new HashSet();for(int i : nums1){set1.add(i);}for(int i : nums2){if(set1.contains(i)){resSet.add(i);}}//将结果集合转变为数组//方法1//return resSet.stream().mapToInt(x -> x).toArray();//方法2int[] arr = new int[resSet.size()];int j = 0;for(int i : resSet){arr[j++] = i;}return arr;}
}

3.202. 快乐数

题目链接:快乐数
文档讲解: 代码随想录

class Solution {public boolean isHappy(int n) {Set<Integer> record = new HashSet<>();while(n != 1 && !record.contains(n)){record.add(n);n = getSum(n);}return n == 1;     }private int getSum(int n){int res = 0;while(n > 0){int temp = n % 10;res += temp * temp;n = n / 10; }return res;}
}

4.1. 两数之和

题目链接:两数之和
文档讲解: 代码随想录

//暴力求解
class Solution {public int[] twoSum(int[] nums, int target) {int[] arr = new int[2];for(int i = 0; i < nums.length - 1; i++){for(int j = i + 1; j < nums.length; j++){if(nums[i] + nums[j] == target){arr[0] = i;arr[1] = j;}}}return arr;}
}

(1)为什么会想到用哈希表
需要查询一个元素是否出现过,或者一个元素是否在集合中。在此题中,对于元素A,我们需要找是否存在另一个元素B,使得A + B =9。
(2)哈希表为什么用map
由于题目需要返回下标,则需要记录值与下标,需要使用key value结构来存放,key放值,value放下标。map用来存放我们遍历访问过的元素。

//哈希表
class Solution {public int[] twoSum(int[] nums, int target) {//哈希表int[] res = new int[2];if(nums == null || nums.length == 0){return res;} Map<Integer, Integer> map = new HashMap<>();for(int i = 0; i < nums.length; i++){int temp = target - nums[i];if(map.containsKey(temp)){res[0] = i;res[1] = map.get(temp);break;}map.put(nums[i], i);}return res;}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com