新的一周开始啦！
哈希表的关键：快速查找用哈希
242.有效的字母异位词
题目描述：
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
题解：Hashmap
class Solution {
public boolean isAnagram(String s, String t) {
int[] record = new int[26];
for (char c: s.toCharArray()){
record[c-'a'] = record[c-'a']+1;
}
for (char c: t.toCharArray()){
record[c-'a'] = record[c-'a']-1;
}
// for (int i = 0; i<record.length ; i++){
// if (record[i] !=0) return false;
//迭代器，i为record中存的值，不是index
for(int i: record) {
if (i!=0) return false;
}
return true;
}
}
思考：
为什么使用s.toCharArray()来遍历字符串数组，而不是用length()来循环？
- 因为前者只需要遍历数组一次即可，而如果使用for (int i = 0; i<record.length ; i++)，则每次循环都需要遍历数组一次，如果字符串很长，则时间复杂度较大。
toCharArray和CharAt的区别 - 前者是将原来的数组进行复制，再将复制的数组返回给函数；后者则直接返回数组中的某个字符；
349. 两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序.
解题思路：
1.遍历数组1。
2.再去遍历数组2，判断数组2中的每一个元素是否在数组1中出现；
·如果出现，则存入结果
·如果没出现，就跳过
3.返回结果list
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
Set<Integer> res = new HashSet<>();
for (int i : nums1) {
set1.add(i);
}
for (int i : nums2) {
if (set1.contains(i)) {
res.add(i);
}
}
//将结果几何转成数组
//数组定义时要设定数组的长度
int[] resArr = new int[res.size()];
int index = 0;
for (int i : res) {
resArr[index++] = i;
}
return resArr;
}
}
202.快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
- 如果 n 是 快乐数 就返回 true ；不是，则返回 false.
解题思路：
通过哈希表来检测循环。
1.用哈希表来检测sum是否重复出现
2.通过取余操作来获取int整数的各个单位数，来计算每个单位数的平方和
class Solution {
//设置函数来获取下一个值每一单位数的平方和
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
//取余操作：1223 % 10 = 3；1223/10=122 122%10=2...
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
Set<Integer> record = new HashSet<>();
//如果之前计算的sum没有出现过，则写入哈希表；如果出现过，则表明会进入循环，得不到1；
while (n != 1 && !record.contains(n)) {
record.add(n);
n = getNext(n);
}
return n==1;
}
}
解法二：龟兔赛跑/快慢指针
解题思路：
判断是否有循环，可以看着这个链表是否存在cycle，也就是环形链表这一题
1.设置快慢指针，初始值不能相同
2.快指针走两步，这边看成嵌套调用2次getNext函数；
慢指针走一步，调用一次getNext；
3.如果存在循环，快慢指针一定会在环内相遇，则这个数不是快乐数
4.如果不存在循环，快指针一定先一步成为1，返回fast即可
class Solution {
//设置函数来获取下一个值每一单位数的平方和
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
//取余操作：1223 % 10 = 3；1223/10=122 122%10=2...
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
//龟兔赛跑算法，与题142思想相同
public boolean isHappy(int n) {
//fast和slow初始值不能相同，原因见题141
int slow = n;
int fast = getNext(n);
while (fast != 1 && fast != slow) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return fast == 1;
}
}
1. 两数之和
题目描述：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
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> hashTable = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int temp = target-nums[i];
//查看target-x的值是否在哈希表中，在的话写入res表内
if (hashTable.containsKey(temp)) {
res[1] = i;
res[0] = hashTable.get(temp);
}
hashTable.put(nums[i],i);
}
return res;
}
}
