题目1 242. 有效的字母异位词
给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。
字母异位词 是通过重新排列不同单词或短语的字母而形成的单词或短语，通常只使用所有原始字母一次。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
提示:
1 <= s.length, t.length <= 5 * 104s和t仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
思路
哈希表方法
这道题是经典的用空间换时间，只需要用一个额外的数组来统计两个字符串的长度就行了，时间复杂度从\(O(n*m)\)变为\(O(n+m)\)。
代码
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size())
{
return false;
}
int hash[26];
for(int i = 0; i < 26; i++)
hash[i] = -1;
vector<int> result;
for(auto c : s)
{
if(hash[c - 'a'] == -1)
{
result.push_back(1);
hash[c - 'a'] = result.size() - 1;
}
else
{
result[hash[c - 'a']]++;
}
}
for(auto c : t)
{
//如果没有初始化这个字母则说明字符串s中没有这个字符
if(hash[c - 'a'] == -1)
{
return false;
}
result[hash[c - 'a']]--;
}
for(auto &num : result)
{
if(num != 0)
return false;
}
return true;
}
};
暴力解法1（超时)
我试了嵌套循环，第35个测试用例直接超时，如果能在每次遍历t时缩小遍历范围也许能过。用暴力解法的时间复杂度为\(O(n*m)\)其中n为s的长度，m为t的长度。
代码
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size())
{
return false;
}
int tLength = t.size();
for(auto &c1 : s)
{
int length = 0;
for(auto &c2 : t)
{
if(c1 == c2)
{
c2 = 'a' - 1;
break;
}
length++;
}
if(length == tLength)
return false;
}
return true;
}
};
暴力解法2
这种方法通过调用algorithm头文件里的sort对字符串s和t进行排序，之后再进行一一比较得出结果。其复杂度为：
\[O(nlogn+nlogn+n) = O(nlogn) \]class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != s.size())
{
return false;
}
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};
题目2 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] 也是可通过的
提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
思路
这道题也是用空间换时间，暴力解法就嵌套循环遍历找交集就行了时间复杂度为\(O(n*m)\)，n为nums1的长度，m为nums2的长度。使用额外数组空间来记录可以将时间复杂度减少为\(O(n+m)\)。
当然使用随想录的模板类unordered_set的做法也是类似的思路。
代码
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int> result;
result.reserve(1001);
int hash[1001];
memset(hash,0,sizeof(hash));
for(auto &num : nums1)
{
hash[num]++;
}
for(auto &num : nums2)
{
//如果有交集则hash中的数值置0，且将该数放入result中
if(hash[num] > 0)
{
hash[num] = 0;
result.push_back(num);
}
}
return result;
}
};
题目3 202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
提示：
1 <= n <= 231 - 1
思路
这道题的解题关键在题干里的无限循环，既然无限循环的话就表明可以用set模板类来记录不重复的计算结果，并通过结果数量来判断是否循环。
代码
class Solution {
public:
bool isHappy(int n) {
int index = 0,
lst[32] = {0};
set<int> uniqueNum;
int num;
while(1)
{
index = 0;
num = uniqueNum.size();
uniqueNum.insert(n);
//如果出现无限循环则不是快乐数
if(num == uniqueNum.size())
{
return false;
}
while(n != 0)
{
lst[index] = n % 10;
n /= 10;
index++;
}
for(int i = 0; i < index; i++)
{
n += lst[i] * lst[i];
}
if(n == 1)
{
return true;
}
}
}
};
题目4 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]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
思路
这道题的思路比较唯一就是通过target-nums[i]获取另一个元素的值，保存到hash表中并继续进行数组遍历找到目标值。比较需要注意的就是hash模板类的选择，这道题如果用unordered_map的效率是最高的，因为能够同时保存目标元素值与当前元素的下标，避免了另一轮的循环。我使用的是unordered_set模板类，代价就是额外需要循环判断下标。（当然如果能将元素值与下标进行编码和解码并保存到unordered_set中，效率会更高，因为节省了空间。）我也尝试了一下编解码和unoredered_set模板类，但在处理result-nums[i] < 0的情况时出了点问题。
代码（unordered_set）
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_set<int> result;
vector<int> ret(2, INT_MAX);
for(int i = 0; i < nums.size(); i++)
{
if(find(result.begin(), result.end(), nums[i]) != result.end())
{
ret[1] = i;
ret[0] = target - nums[i];
break;
}
else
{
result.insert(target - nums[i]);
}
}
for(int i = 0; i < nums.size(); i++)
{
if(nums[i] == ret[0])
{
ret[0] = i;
break;
}
}
return ret;
}
};
代码(编解码unordered_set，未AC)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_set<long long> result;
vector<int> ret(2, INT_MAX);
for(long long i = 0; i < nums.size(); i++)
{
unordered_set<long long>::iterator iter;
iter = find_if(result.begin(), result.end(), [&](long long encoded){
return (encoded & 0xFFFF) == nums[i];
});
if(iter != result.end())
{
ret[1] = i;
ret[0] = *iter >> 32;
return ret;
}
else
{
long long encodedValue = (i << 32) | ((target - nums[i]) & 0xFFFF);
result.insert(encodedValue);
}
}
return ret;
}
};