day06_理论_有效的字母异位词_两个数组的交集_快乐数_两数:和
理论基础
一般哈希表都是用来快速判断一个元素是否出现在集合里。
哈希函数
哈希碰撞
一般哈希碰撞有两种解决方法,拉链法和线性探测法。
拉链法
拉链法就是要选择适当的哈希表的大小,这样既不会因为数组空值而浪费大量内存,也不会因为链表太长而在查找上浪费太多时间。
线性探测法
例如冲突的位置,放了小李,那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ,要不然哈希表上就没有空置的位置来存放冲突的数据了。
力扣242.有效的字母异位词
题目链接:https://leetcode.cn/problems/valid-anagram/
思路
1.两个字符串,当s有某个字母时,该字母次数 1;当t也有这个字母时,该字母次数-1。当每个字母的次数都为0时,说明这两个字符串时字母异位词。反之,则不是。
2.a-z有26个字母,由于ASCII码的26个字母是连续的,所以-‘a’相当于以a为参照。例如’a’-'a’就等于0,a字母的次数被记录在record[0]里。
完整代码
class Solution {
public boolean isAnagram(String s, String t) {
int[] record=new int[26];//a-z只有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;
}
}
力扣349.两个数组的交集
题目链接:https://leetcode.cn/problems/intersection-of-two-arrays/description/
思路
判断两个数组里有没有重复的元素,输出可以无序,使用set的效率是最高的。因为我们无法确定这两个数组有多大,如果使用数组可能会造成空间的浪费。
完整代码
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set= new HashSet<>();
Set<Integer> resset= new HashSet<>();
for(int i:nums1){
set.add(i);
}
for(int i:nums2){
if(set.contains(i)){
resset.add(i);
}
}
return resset.stream().mapToInt(i->i).toArray();
}
}
set方法
1.add(i):向集合中加入元素i
2.contains(i):集合中包含i
3.stream():为集合创建串行流。
4.mapToInt():将map里的元素转换为int型
5.toArray():转换为数组
力扣202.快乐数
题目链接:https://leetcode.cn/problems/happy-number/
思路
1.“无限循环”的意思就是会在set里面再找到n。
2.没出现过的n要加进set里,再更新计算n的值。
2.如何处理数位,见getnextnumber方法。
完整代码
class Solution {
public boolean isHappy(int n) {
Set<Integer> set=new HashSet<>();
while(n!=1 && !set.contains(n)){
set.add(n);
n=getnextnumber(n);
}
return n==1;
}
public int getnextnumber(int n){
int res=0;
int temp=n;
res =temp*temp;
n=n/10;
return res;
}
}
力扣1.两数之和
题目链接:https://leetcode.cn/problems/two-sum/description/
思路
1.为什么会想到用哈希法?
我们需要一个集合存我们遍历过的元素,再对数组遍历时,我们需要知道是否已经遍历过这个元素。
2.哈希法为什么用map?
我们不仅要知道遍历过的元素,还要知道它的下标。因此用map结构,key存放元素值,value存放元素下标。
3.本题map是用来存什么的?
map用来存放遍历过的元素,我们需要查询当前元素我们是否遍历过。
4.map中的key和value用来存什么?
key存放元素值,value存放元素下标。在遍历数组的时候,只需要向map去查询是否有和目前遍历元素匹配的数值,如果有,就找到了匹配对,如果没有,就把目前遍历的元素放进map中。
完整代码
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res= new int[2];
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i ){
int temp=target-nums[i];
if(map.containsKey(temp)){
res[1]=i;
res[0]=map.get(temp);
}
map.put(nums[i],i);
}
return res;
}
}
map方法
1.containsKey(i):map里是否包含key值为i的元素。
2.get(i):获取key值为i的value值。
3.put(i,j):存放i作为key值,j作为value值。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhficfae
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13