Java LeetCode 哈希专题 基础总结

发布于:2023-01-04 ⋅ 阅读:(278) ⋅ 点赞:(0)

以下仅为我在刷leetcode时遇到的一些个人问题,仅为之后二刷复习用。可能不会涉及比较具体的解题方法,若要看具体解题方法,可以去leetcode 看题解

@1.字符串转换成数组::

String s;
s.toCharArray();

@2.返回一个空数组
return new int[ 0 ];

@3 数组的长度:length , not lenghth

@4 新建一个值为正数的哈希Set4 新建一个值为正数的哈希Set

 Set<Integer> hashSet = new HashSet<>(); //True
 Set<int> hashSet = new HashSet<>();  // False

@5.集合的大小

@6.将一个集合转换成一个数组

int index = 0;
for(int c : resultSet){
  resultArray[index++]=c;
} 

@7.对一个数n的各个位数取平方再求和: 7.对一个数n的各个位数取平方再求和:

private int getSquarSum(int n){
int sum=0;
while(n>0){
	sum+=(n%10)*(n%10);
	n=n/10;
}
return sum;
}

@8, 循环,哈希法 202-快乐数8, 循环,哈希法 202-快乐数

@9 新建HashMap9 新建HashMap

Map<Integer,Integer> hashMap = new HashMap<>();

@10 Map是否包含值为n的key?10 Map是否包含值为n的key?

public boolean containsKey (Map<Key>)

hashmap.containsKey(n)  

@11 取出Map中key 为n对应的value

public Map<value> get(Map<key>) ; 

hashmap.get(n);

@[12 两数之和]12 两数之和
两数之和 力扣
四个点:1,为什么使用哈希 2.为什么使用Map 3.Map的作用
4, Map中存放的key 是什么,value又是什么

@13 HashMap 添加键值对

map.put(key,value);

@14.HashMap中将key为n 的值加一14.HashMap中将key为n 的值加一

map.put(key,map.get(key)+1);

15, 力扣454 四数相加
1.为什么用哈希法?
答:因为思路与 242 有效的字母异位词大致。
2.为什么采用 map 的哈希数据结构来存储两个参数数组的合并,而不是采用一个n*n的数组?
答:两种数据结构都可以做,只是复杂度的问题。采用map数据结构,不仅可以存储两个数组的合并,还可以存储两个数组合并后的新数共有多少次。而数组不行,之后判断的时候又不知道如何去取该数有多少个。当然,用数组,暴力解也是可以的。
3. map 的key 和value 分别存储什么?
答: map的key存储两个数组合并后产生的新数, value存储两个数组在合并过程中,若产生相同的数,那么出现了多少次。
这样存储的目的是,将来若要找n这样的数出现了多少次,只要map.get(n)查询就可以了。
4. 细节处理:
在第二次合并nums3和nums4的处理时,就可以加上找 0-(nums3[i]+nums4[j]) 的判断,而不是再使用第三次两层for循环判断。

使用了3个for 循环: 3n^
在这里插入图片描述

使用2 个for 循环 : 2n^ :
在这里插入图片描述

  1. 多个三元组在一个集合中,每个元组是一个集合。如:下面截图中的输出形式
    在这里插入图片描述
List<List<Integer>> result  = new ArrayList<>();

17,对数组nums进行从小到大排序

Arrays.sort(nums);

18,将一个元组(数组)以集合的形式添加到结果集合result中。

result.add(Arrays.asList(nums[i],nums[left],nums[right]));
  1. 关于条件判断中的一些细节:

    在这里插入图片描述
    两张截图的不同地方在于: 判断中的两个条件的顺序。

20 力扣15 三数之和
关于去重的细节:
以下为错误的去重:
在这里插入图片描述
错误的原因在于两个while循环对right,left的去重条件判断是放在找到符合条件的元组的if else 分支外面。但这是不合逻辑的。对right , left 的去重就是要找找到符合条件的元组之后再进行去重。

以下为正确的去重截图:
在这里插入图片描述

21 .力扣18 四数之和

关于这道题的剪枝和去重是最关键的。将这道题看作升级版的三数之和。同样是用双指针法。在两层for循环下,使用双指针法。注意第二层for循环j 的去重。如下截图:

在这里插入图片描述
在 第一个 if 条件判断 剪枝时,就不能直接return result ,这样会忽略第一次for 循环 i 之后的测试案例。应该是break 。这里我当时没有想明白,用idea 调试了挺久。

还有双指针法中的left , right 两个变量, 在去重时 条件判断要默认 right > left ,不然会数组溢出。

本文含有隐藏内容,请 开通VIP 后查看

网站公告

今日签到

点亮在社区的每一天
去签到