参考代码随想录/LeetCode作的学习笔记。
特别赞同卡子哥的一句话，初学者刚开始学习算法的时候，看到简单题目没有思路很正常，千万别怀疑自己智商，学习过程都是这样的，大家智商都差不多。慢慢来，一切都会好起来~
哈希函数： 如将姓名通过HashCode 编码成数字。
哈希表： 通过哈希法可以实现一对一映射和O(1)的查找复杂度。如果在做面试题目的时候遇到需要判断一个元素是否出现过的场景应该第一时间想到哈希法！
LeetCode 242. 有效的字母异位词 难度级别 easy
题目： 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母
思路： 首先要知道一共26个字母，需要大小为26的数组来存储数据。思路1：分别在s和t中统计每个字符出现的次数，然后对比次数是否相同；思路2：在s中统计每个字符出现的次数，在t中再次遇到这个次数时数组中做相应的减 *** 作,最后判断数组是否每个元素都为0；我们采用思路2来做更节省空间。初始条件，长度不同肯定不符。
注意点： 这里要-‘a’，因为a的ASCII在前,a-z 97-122。虽然这里需要的是一个相对位置， 但是如果-'b’就不行，因为当遇到a字符时record索引为负值，会溢出。
关键词： 字符串，数组做哈希表
知识点： 对字符串的长度计算为s.length()，对数组的长度计算为record.length，取字符串中下标为i的字符char c = s.charAt(i)
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length()!=t.length()) return false;
int[] record = new int[26];
for(int i = 0;i
LeetCode 349. 两个数组的交集 难度级别 easy
题目： 给定两个数组，编写一个函数来计算它们的交集。
思路： 使用两个hashset，第一个记录nums1元素方便使用Hashset的包含方法，第二个记录结果，最后复制到数组中。条件为是否存在空数组。
关键词： 交集，Set做哈希表
知识点： Set使用 Set set1 = new HashSet<>();，添加值 set1.add(值)，包含判断set1.contains(值)，计算大小set1.size()，循环遍历值for(int i:set1)，返回空数组return new int[0];
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
//1、结果集是不重复的元素，也不考虑顺序
//2、数字不像英文那样限定就只有26个，它可能是1000，多位的，所以无法用数组来解答了
//3、注意：set的使用耗时较大，不能无脑使用
//思路：使用两个hashset，第一个记录nums1元素方便使用包含方法，第二个记录结果
if(nums1.length == 0||nums2.length ==0) return new int[0];
Set set1 = new HashSet<>();
Set resSet = new HashSet<>();
//将nums1复制到set中
for(int i = 0;i
LeetCode 202. 快乐数 难度级别 easy
题目： 编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false
思路： 题目中提到可能是限循环，所以可能会遇到相同的n陷入死循环。很容易想到使用哈希表来检查是否n重复，即每次将遇到的n添加到哈希表中。循环条件为n>0。如何获取各个位的位数的和是需要思考的。
关键词： 位数平方和，Set做哈希表
知识点： 位数平方和
class Solution {
public boolean isHappy(int n) {
//快乐数，替换为数平方和，变为1就为true，否则为false
//思路1：这个数可能会非常的大，但是最大就10位，那位数可以用一个数组来存储
//System.out.println((1 << 31) -1);2147483647
//正确思路2：
Set ns = new HashSet<>();//记录n
while(n>0){
if(ns.contains(n)) return false;//如果n重复死循环,返回false
ns.add(n);
//更新n
n = getSum(n);
if(n==1) return true;
}
return false;
}
//如何获取每个数的各个位呢，或者如何更新n呢？
int getSum(int n){
int sum = 0;
while(n > 0){
sum +=(n%10)*(n%10);
n/=10;
}
return sum;
}
}
LeetCode 1. 两数之和 难度级别 easy
题目： 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
思路： 遍历数组，每次将值和下标插入Map中，同时判断Map中是否包含差值，
关键词： Map做哈希表
知识点： Map用法，判断是否存在值map.containsKey(值)，添加值和下标map.put(值，下标);，取值的下标map.get(值);
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
Map map = new HashMap<>();
for(int i = 0;i
LeetCode 454. 四数相加 II 难度级别 Mid
题目： 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
思路： 四个数组是无法直接暴力求解的，所以将他们分为两组。第一组得到求和的值，以及该值出现的次数。然后从遍历第二组时，每次，注意是每次得到的一个求和sum，在Map中去搜索-sum，然后将Map中的-sum的次数累加进结果中。因为是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，我们得到的目标是下标，所以不用考虑有重复的四个元素相加等于0的情况。
注意点： 不应该统计A+B的次数和-(C+D)的次数的乘积吗？其实这里很巧妙，它是对应每个第二组的C+D从A+B中找-(C+D)，比如A+B = 2，当你在C+D中找到了-2，每次找到-2都会统计一次Map中2的次数，其实就是相乘。
关键词： 分组，Map做哈希
知识点： Map包含两部分，第一个是键值，第二个可以是索引，也可以是次数等数据。
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
//4个数组，长度都是n，有多少个元组能满足
//元组不能重复，这个如何保证？
//其次如何遍历？
//思路：将a+b存储到一个Map中，每单次找到-(c+d)，就统计Map中的次数
Map map = new HashMap<>();
int temp = 0;
int res = 0;
for(int i:nums1){//统计数组之和以及出现的次数，存入map中
for(int j:nums2){
temp = i + j;
if(map.containsKey(temp)){
map.put(temp,map.get(temp) + 1);
}
else map.put(temp,1);
}
}
for(int i:nums3){
for(int j:nums4){
temp = i+j;
if(map.containsKey(0-temp)){
res +=map.get(0-temp);
}
}
}
return res;
}
}
LeetCode 383. 赎金信 难度级别 easy
题目： 给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
思路： 先后统计r,m中字符的次数，如果r中出现了m中没出现过的字符，或者r中某个字符出现的次数比b中的同样的字符出现的次数多则返回false。遍历结束，都满足则返回true。但是这种思路用的Map，底层用的红黑树，非常费时。所以下面介绍数组的方法。
关键词： 字符串、Map做哈希
知识点： 字符串与字符串数组 String str1 = "11dad166E8EH你好99"; String[] s = str1.split("");
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
//b中的字符打乱拼成a，所以要确保b字符串的字符在a中仅仅出现过一次
//确切的说是a中的字符出现的次数不能比b中的同样的字符出现的次数多
//如果a中包含了b中没出现过的字符，也不行
//用什么存储结构？因为需要统计次数，所以用Map
Map map = new HashMap<>();
Map map1 = new HashMap<>();
//思路：先统计r,m中字符的次数
String[] r = ransomNote.split("");
String[] m = magazine.split("");
for(String i: m){
if(map.containsKey(i)) map.put(i,map.get(i)+1);
else map.put(i,1);
}
for(String i: r){
if(map1.containsKey(i)) map1.put(i,map1.get(i)+1);
else map1.put(i,1);
if(!map.containsKey(i) || map1.get(i) > map.get(i)) return false;
}
return true;
}
}
对比强烈！！
本题与LeetCode 242. 有效的字母异位词 均是处理字母，有一些相似之处。
数组思路： 因为是英文字母，所以设置一个数组来存储，依托的思路也很简单，ransomNote存在magazine中不存在的字符或相同的字符出现更多次时，count会小于0，返回false，这里的实现方式是基于对次数的++，–，非常好用。
关键词： 字符串、数组做哈希
知识点： 取字符串String中的字符magazine.charAt(下标)
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
//记录杂志字符串出现的次数
int[] count = new int[26];
for (int i = 0; i < magazine.length(); i++) {
count[magazine.charAt(i) - 'a']++;
}
for (int i = 0; i < ransomNote.length(); i++) {
count[ransomNote.charAt(i) - 'a']--;
if(count[ransomNote.charAt(i) - 'a'] < 0) return false;
}
return true;
}
}
LeetCode 15. 三数之和 难度级别 Mid
题目： 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组
思路： 三元组使用哈希去 *** 作非常复杂，去重过程难以处理，故采用先固定第一个元素，然后剩下两个元素使用两个指针来遍历的方法。另外两个元素做相似的去重处理。
关键词： 双指针，同一个数组中的三数之和
知识点： 将数组的一部分元素合为list，并返回这个list，Arrays.asList(nums[i], nums[left], nums[right]));数组排序，Arrays.sort(nums);
class Solution {
public List> threeSum(int[] nums) {
//注意一个条件，不包含重复的三元组,这个条件无法或者说很难通过哈希来解决（需要三重去重）
//思想：如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
List> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {//如果第一个元素大于0，因为递增的性质，无论如何都无法=0了
return result;
}
if (i > 0 && nums[i] == nums[i - 1]) {//兼顾考虑[-1,-1,2]的情况
continue;
}
int left = i + 1;//left，right前闭后闭区间
int right = nums.length - 1;
while (right > left) {//常规 循环条件
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {//大于0则缩小right
right--;
} else if (sum < 0) {//小于0则增大left
left++;
} else {//满足条件
result.add(Arrays.asList(nums[i], nums[left], nums[right]));//将数组的一部分元素合为list
while (right > left && nums[right] == nums[right - 1]) right--;//去重尾部分
while (right > left && nums[left] == nums[left + 1]) left++;//去重头部分
//找到一个符合条件的list之后，收缩指针
right--;
left++;
}
}
}
return result;
}
}
LeetCode 18. 四数之和 难度级别 Mid
题目： 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
思想： 四数之和是在三数之和的基础上多加了一个数，自然能够想到使用双重循环来确定前面一个值。三数之和 可以通过 nums[i] > 0 就返回了，而四数之和这道题目 target是任意值，就不需要做这个处理了。
关键词： 双指针，同一个数组中的四数之和
知识点： 将数组的一部分元素合为list，并返回这个list，Arrays.asList(nums[i], nums[left], nums[right]));数组排序，Arrays.sort(nums);
class Solution {
public List> fourSum(int[] nums, int target) {
//{a1,b1,c1,d1}与{a2,b2,c2,d2}不完全相同即可
List> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i - 1] == nums[i]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {//这里多了一层循环
if (j > i + 1 && nums[j - 1] == nums[j]) {
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (right > left) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
left++;
right--;
}
}
}
}
return result;
}
}
复盘
数组、Set、Map做哈希表的优劣对比：
数组的大小是受限制的，而且如果元素很少，而哈希值太大，数据的存储会非常稀疏，造成内存空间的浪费；set是一个集合，里面放的元素只能是一个key；Map是同时存储索引值和键值的存储结构。能用数组尽量用数组，尤其是处理像字母这种种类有限的情况。
多元组
此外对于像三数之和、四数之和这样的题目，需要存储多元组，需要用到列表，和Arrays.asList(值，值，值..)方法
完结~
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）