1.有效的字母异位词
- LeetCode：242.有效的字母异位词
给定两个字符串s和t ，编写一个函数来判断t是否是s的字母异位词。
示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:
输入: s = “rat”, t = “car”
输出: false
- 解题思路：
由题可知，字母异位词是两个数组字母相同但是顺序不同，我们需要快速的找出某个值是否在表中，因此考虑使用哈希表。
1.使用一个大小为26的数组（对应26个英文字母）作为计数器；
2.遍历第一个字符串，将出现的字母对应增加相应字符的计数；
3.遍历第二个字符串，将出现的字母减少相应字符的计数；
4.如果两个字符串是字母异位词，最终计数器所有位置都应为0。
其中创建一个包含26个整数的数组（初始化为0），每个位置对应一个字母，如：
res[0] → ‘a’ 的计数
res[1] → ‘b’ 的计数
…
res[25] → ‘z’ 的计数
然后将字符到索引利用一个巧妙的ASCII码进行转换s[i] - 'a'，如：
‘a’ 的ASCII码是97
‘b’ 是98，
…，
‘z’ 是122
然后通过计算可得：
‘a’ - ‘a’ = 0
‘b’ - ‘a’ = 1
…
‘z’ - ‘a’ = 25
从而就得到了每个字母的对应位置。由此便可进行计算
如：
（1）有效字母异位词
s = “anagram”, t = “nagaram”
1.遍历s: a→+1, n→+1, a→+1, g→+1, r→+1, a→+1, m→+1
2.遍历t: n→-1, a→-1, g→-1,a→-1, r→-1, a→-1, m→-1
3.所有计数器归零 → 返回true
（2）无效字母异位词
s = “rat”, t = “car”
1.遍历s: r→+1, a→+1, t→+1
2.遍历t: c→-1, a→-1, r→-1
3.最终计数器中: a:0, r:0, t:+1,c:-1
t,c是非零值 ，因此返回false
class Solution {
public:
bool isAnagram(string s, string t) {
//步骤1：创建计数器数组
int res[26] = {0};
//步骤2：遍历字符串s，增加字符计数
for(int i = 0; i < s.size(); ++i)
res[s[i] - 'a']++;
//步骤3：遍历字符串t，减少字符计数
for(int i = 0; i < t.size(); ++i)
res[t[i] - 'a']--;
//步骤4：检查计数器是否全为0
for(int i = 0; i < 26; ++i) {
if(res[i] != 0)
return false; //任何非零值都表示计数不匹配
}
return true; //所有计数均为0，是字母异位词
}
};
2.两个数组的交集
- LeetCode：349.两个数组的交集
给定两个数组nums1和nums2，返回它们的交集 。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
- 解题思路：
本题要求我们找出两个数组中的相同元素，涉及到快速查找某个元素是否在表中，因此考虑用哈希表来求解，此外若题目限制了数组的大小可以选择数组来解题，但是本道题没有规定数组的大小，因此无法用数组来做哈希表，而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。因此我们考虑使用set或map，对于本题来说，我们只需返回相同的元素即可，且不要求顺序，因此我们使用unordered_set求解。
首先unordered_set中数值要求不能重复，因此会自动过滤重复元素，我们可以创建一个结果集用来存放交集元素，同时将数组nums1转换为哈希表，即：
[1,2,2,1] → {1,2}
具体操作为：
unordered_set<int> result_set; //存储结果的集合（自动去重）
unordered_set<int> nums_set(nums1.begin(), nums1.end());
//将nums1转换为哈希集合（自动去重）
然后我们遍历nums2，同时在哈希表nums1中寻找nums2中有的元素，若找着了，就把这个元素插入到结果集中即：
for (int num : nums2) {
//检查当前元素是否存在于nums1的集合中
if (nums_set.find(num) != nums_set.end()) {
result_set.insert(num); //存在则加入结果集
}
}
对于int num：是声明了一个临时变量num，类型是int，每次循环时，num会被自动赋值为nums2的当前元素。注意：这里是值拷贝，即复制元素值。nums2：则是要遍历的容器，这里是vector。编译器会自动处理迭代过程。即执行流程为：
第一次循环：num = nums2的第一个元素
第二次循环：num = nums2的第二个元素
…
直到遍历完nums2中所有元素
if (nums_set.find(num) != nums_set.end()) 是判断元素num是否存在于集合nums_set中的标准方法。
nums_set.find(num)：在集合中查找键为num的元素
若找到：返回指向该元素的迭代器
若未找到：返回一个特殊的迭代器nums_set.end()（表示集合末尾的下一个位置，为无效位置）
最后将结果集转化为vector返回，即：
return vector<int>(result_set.begin(), result_set.end());
整体C++代码为：
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//存储结果的集合（自动去重）
unordered_set<int> result_set;
//将nums1转换为哈希集合（自动去重）
unordered_set<int> nums_set(nums1.begin(), nums1.end());
//遍历nums2中的每个元素
for (int num : nums2) {
//检查当前元素是否存在于nums1的集合中
if (nums_set.find(num) != nums_set.end()) {
result_set.insert(num); //存在则加入结果集
}
}
//将结果集合转换为vector返回
return vector<int>(result_set.begin(), result_set.end());
}
3.快乐数
- LeetCode：202.快乐数
编写一个算法来判断一个数 n 是不是快乐数。「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为1，也可能是无限循环但始终变不到1。
如果这个过程 结果为1，那么这个数就是快乐数。
如果n是快乐数就返回true；不是，则返回false。
示例 1：
示例 2：
-解题思路：
由题意，对于一个正整数，重复将其替换为各位数字的平方和，最终结果变为1的数即为快乐数。而无限循环时不是快乐数，而在无限循环的过程中，一定会出现重复的结果，因此我们需要在结果集中快速寻找是否存在重复的结果，若存在即陷入循环了，就不是循环数。此外对结果的顺序不做要求，因此选择unordered_set。
首先，我们需要计算给定n的各位平方和，即：
//计算数字各位平方和的辅助函数
int getsum(int n) {
int sum = 0;
while(n) { //当n不为0时继续处理
sum += (n % 10) * (n % 10); //取最后一位数字并平方
n /= 10; //移除最后一位数字
}
return sum;
}
这是一个基本的处理一个整数各个位的方法，如：
初始：n=19
第一次循环：19 % 10 = 9, 则sum = 81, 19 / 10 = 1，即n更新为1
第二次循环：1 % 10 = 1, sum = 81 + 1 = 82, 1 / 10 = 0
不满足循环条件，返回82
然后，我们需要创建一个结果集，用来存放所有sum。并使用哈希集合检测循环，若结果等于1，则说明为快乐数；若结果重复出现，则说明非快乐数。
unordered_set<int> res; // 储出现过的计算结果
while(1) { //无限循环直到找到结果
int sum = getsum(n); //计算当前数字的平方和
//检查是否满足快乐数条件
if(sum == 1)
return true;
//检查是否出现循环（结果重复）
if(res.find(sum) != res.end())
return false;
else
res.insert(sum); //记录新结果
n = sum; //更新n为新的计算结果，确保每次迭代使用最新计算结果
}
整体代码为：
class Solution {
public:
int getsum(int n) {
int sum = 0;
while(n) { //当n不为0时继续处理
sum += (n % 10) * (n % 10); //取最后一位数字并平方
n /= 10; //移除最后一位数字
}
return sum;
}
//判断是否为快乐数
bool isHappy(int n) {
unordered_set<int> res; //存储出现过的计算结果
while(1) { // 无限循环直到找到结果
int sum = getsum(n); //计算当前数字的平方和
//检查是否满足快乐数条件
if(sum == 1)
return true;
//检查是否出现循环（结果重复）
if(res.find(sum) != res.end())
return false;
else
res.insert(sum); //记录新结果
n = sum; //更新n为新的计算结果
}
}
};
4.两数之和
- LeetCode：1.两数之和
给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值 target的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
- 解题思路
本题不是直接找两个数，而是对于每个元素nums[i]，检查target - nums[i]是否存在于之前遍历过的元素中，其思路与有效字母异位词的思路一致。即如果a + b = target
那么b = target - a。因此我们可以使用哈希表：使用unordered_map存储已遍历元素的值和索引，通过一次遍历，边遍历边检查边存储。
首先建立结果集：
unordered_map<int,int> res//键：元素值，值：元素索引
key用来存储数组元素的值，用于快速查找；value用来存储该元素的索引，用于最终返回结果。
然后通过遍历结果集查找是否存在target - a，若存在返回下标，若不存在返回空。即整体流程为：
假设我们输入：
nums = [2, 7, 11, 15], target = 9
执行流程：
第一次循环：i=0，nums[0]=2
结果集中查找9-2=7（不存在）
插入map: {2:0}
第二次循环： i=1，nums[1]=7
结果集中查找9-7=2（找到，索引为0）
返回[0,1]
for(int i = 0; i < nums.size(); i++) {
// 尝试寻找能与nums[i]配对的数
auto iter = map.find(target - nums[i]);
// 如果找到配对
if(iter != map.end()) {
return {iter->second, i}; // 返回两个索引
}
// 将当前元素存入map（先检查后存储，避免自匹配）
map.insert(pair<int, int>(nums[i], i));
}
return { };
整体代码为：
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map<int,int> res; //键：元素值，值：元素索引
for(int i = 0; i < nums.size(); i++) {
//尝试寻找能与nums[i]配对的数
auto it = res.find(target - nums[i]);
//如果找到配对
if(it != res.end()) {
return {it->second, i}; //返回两个索引
}
//将当前元素存入map（先检查后存储，避免自匹配）
res.insert(pair<int, int>(nums[i], i));
}
return {};
}
pair<int, int>中pair为是C++标准库中的模板类，用于存储两个值作为一个单元。这里相当于创建了一个临时对象，包含：first = nums[i]和second = i。当插入元素时，必须同时提供key和value，而pair正好把这两个值打包成一个对象。