代码随想录第五天 | 哈希表part01
哈希表理论基础建议：大家要了解哈希表的内部实现原理，哈希函数，哈希碰撞，以及常见哈希表的区别，数组，set 和map。
什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。这句话很重要，大家在做哈希表题目都要思考这句话。
文章讲解：https://programmercarl.com/哈希表理论基础.html
242.有效的字母异位词
建议： 这道题目，大家可以感受到 数组 用来做哈希表 给我们带来的遍历之处。
题目链接/文章讲解/视频讲解： https://programmercarl.com/0242.有效的字母异位词.html
题目感想：
1.就是相同数量的字母来组成的不同的单词嘛，我们可以通过暴力循环来得出是否是异位词，也可以通过初始化一个数组，因为全是字母且小写，所以只用26位数组就行，然后先遍历第一个字符串，在数组其对应的位置上面+1，然后再遍历第二个字符串，在数组对应位置上-1，最后再检查整个数组，看是否有不为0的位，有则不是，没有则是异位字；
/**
* 242. 有效的字母异位词 字典解法
* 时间复杂度O(m+n) 空间复杂度O(1)
*/
class Solution {
public boolean isAnagram(String s, String t) {
int[] record = new int;
for (int i = 0; i < s.length(); i++) {
record++;
// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
}
for (int i = 0; i < t.length(); i++) {
record--;
}
for (int count: record) {
if (count != 0) {
// record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
return false;
}
}
return true;
// record数组所有元素都为零0，说明字符串s和t是字母异位词
}
}<ol start="349">两个数组的交集
建议：本题就开始考虑 什么时候用set 什么时候用数组，本题其实是使用set的好题，但是后来力扣改了题目描述和 测试用例，添加了 00 && hash2 > 0) resList.add(i); int index = 0; int res[] = new int; for(int i : resList) res = i; return res; }}
[*]快乐数
建议：这道题目也是set的应用，其实和上一题差不多，就是 套在快乐数一个壳子
题目链接/文章讲解：https://programmercarl.com/0202.快乐数.html
题目感想：
1.最简单的方法就是计算然后去set里面找是否出现过，没出现就存起来，直到结果为1或者出现重复的就结束；
import java.util.HashSet;
import java.util.Set;
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
return new int;
}
Set<Integer> set1 = new HashSet<>();
Set<Integer> resSet = new HashSet<>();
//遍历数组1
for (int i : nums1) {
set1.add(i);
}
//遍历数组2的过程中判断哈希表中是否存在该元素
for (int i : nums2) {
if (set1.contains(i)) {
resSet.add(i);
}
}
//方法1：将结果集合转为数组
return resSet.stream().mapToInt(x -> x).toArray();
//方法2：另外申请一个数组存放setRes中的元素,最后返回数组
int[] arr = new int;
int j = 0;
for(int i : resSet){
arr = i;
}
return arr;
}
}2.还有一个方法就是用到了快慢指针，慢指针一次走一步，快指针一次走两步，之后比较他们的出的值是否有为1的或者他们的值是否相等，这样就不用存储了！！！是不是很熟悉，没错，我们在找链表中的环的时候也用到了这个，太有意思了。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int[] hash1 = new int;
int[] hash2 = new int;
for(int i : nums1)
hash1++;
for(int i : nums2)
hash2++;
List<Integer> resList = new ArrayList<>();
for(int i = 0; i < 1002; i++)
if(hash1 > 0 && hash2 > 0)
resList.add(i);
int index = 0;
int res[] = new int;
for(int i : resList)
res = i;
return res;
}
}3.还有一种是数学解法，这个就是找到一个三位数字可能会进入的循环链然后存起来，只要后面的计算的数字在这个循环链中那么就是不能为1的
class Solution {
public boolean isHappy(int n) {
Set<Integer> record = new HashSet<>();
while (n != 1 && !record.contains(n)) {
record.add(n);
n = getNextNumber(n);
}
return n == 1;
}
private int getNextNumber(int n) {
int res = 0;
while (n > 0) {
int temp = n % 10;
res += temp * temp;
n = n / 10;
}
return res;
}
}感兴趣的可以去力扣看看详细的题解；
[*]两数之和
建议：本题虽然是 力扣第一题，但是还是挺难的，也是 代码随想录中 数组，set之后，使用map解决哈希问题的第一题。
建议大家先看视频讲解，然后尝试自己写代码，在看文章讲解，加深印象。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0001.两数之和.html
题目感想：
1.简单的方法有两种，一种是在set中匹配自己需要的，匹配不到把自己加进去，然后循环；另外一种是，给这个数组排序，然后两个指针分布数组两端，根据和目标的大小进行缩进；
class Solution {
public int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
int slowRunner = n;
int fastRunner = getNext(n);
while (fastRunner != 1 && slowRunner != fastRunner) {
slowRunner = getNext(slowRunner);
fastRunner = getNext(getNext(fastRunner));
}
return fastRunner == 1;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/happy-number/solutions/224894/kuai-le-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。class Solution {
private static Set<Integer> cycleMembers =
new HashSet<>(Arrays.asList(4, 16, 37, 58, 89, 145, 42, 20));
public int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
while (n != 1 && !cycleMembers.contains(n)) {
n = getNext(n);
}
return n == 1;
}
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/happy-number/solutions/224894/kuai-le-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。//使用双指针public int[] twoSum(int[] nums, int target) { int m=0,n=0,k,board=0; int[] res=new int; int[] tmp1=new int; //备份原本下标的nums数组 System.arraycopy(nums,0,tmp1,0,nums.length); //将nums排序 Arrays.sort(nums); //双指针 for(int i=0,j=nums.length-1;i
页:
[1]