有效的字母异位词
力扣链接
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词
示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:
输入: s = “rat”, t = “car”
输出: false
- 提示:
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母
题目理解
因为题目的要求是:
- 两个数组 仅仅包含小写字母 ⇒ 一共才26个英语字母
- 两个数组的大小是 1 <= length <= 5*10的四次方
⇒ 我们可以采用 哈希
的思想
我们可以用一个数组(利用下标
)来记录两个数组中每个字母出现的次数
然后通过比较 每个字母出现的次数 和 0 进行比较
🗨️那小写字母如何装换为数组下标?
-
通过ASCLL码来进行转化 ⇒
字母 - 'a'
代码
class Solution {
public:
bool isAnagram(string s, string t)
{
int sum[26] = {0};
// 如果两个数组的大小都不一样, 那就直接返回 false
if(s.size() != t.size())
return false;
for(int i = 0; i < s.size(); i++)
{
sum[s[i] - 'a']++; // a数组的此字母对应的下标++
sum[t[i] - 'a']--; // b数组的此字母对应的下标--
}
// 如果两个数组每个字符出现的次数是一样的, 每个下标对应的都是 0
for(int i = 0; i < 26; i++)
{
if(sum[i] != 0)
return false;
}
return true;
}
};
两数之和
力扣链接
给定一个整数数组 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
只会存在一个有效答案
题目理解(暴力篇)
这题一看就是 低配版 ⇒ 2 <= size( ) <= 10^4
, 这个数组的大小就是很巴适
暴力解法就是 两个for循环 ⇒ 最大时间也是 10^8, 不会爆时间的
代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
vector<int> sum;
for(int i = 0; i < nums.size(); i++)
{
for(int j = i + 1; j < nums.size(); j++)
{
if(nums[j] == target - nums[i])
{
sum.push_back(i);
sum.push_back(j);
break;
}
}
}
return sum;
}
};
题目理解(哈希篇)
我们就会发现, 暴力解法虽然可以, 但是执行时间很长, 那有没有执行时间短的方法呢?
我们的一个思路是:
当我们顺序遍历该数组时, 当我们遍历到一个特定的下标(nums[i])时, 我们需要知道 target - nums[i] 这个数字是否在之前遍历过的数字里面出现过
- 如果出现 — — 返回 (target - nums[i]) 的下标 和 nums[i]的下标 (i)
- 如果没有出现 — — 不返回,
- 如果直至数组的结尾, 也没有出现, 那就返回空
当我们查询一个元素是否出现过, 或者一个元素在一个集合中是否存在 — — 那就可以使用哈希
在本题中, 我们不仅需要知道 (target - nums[i])这个数是否遍历过, 也要知道 (target - nums[i]) 的下标
⇒
那么我们就不能用数组来进行存储了, 可以采用 map的方式进行存储 (key, value)
⇒ key该存储什么, value又该存储什么呢?
由于本题需要返回的是下标, 所以 key应该存储下标, valu来存储数值
⇒ 那map有三种形式, 我们应该选取哪一种呢? map, unordered_map, multimap
由于unordered_map的查询效率是三个当中最快的, 那么我们就选用 unordered_map
代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
// 选用unordered_map这个数据结构
std::unordered_map<int, int> map;
for(int i = 0; i < nums.size(); i++)
{
// 查询 target - nums[i]是否被遍历过
auto cur = map.find(target - nums[i]);
// 之前有被遍历过, 那就直接返回
if(cur != map.end())
{
return {cur->second, i};
}
// 没有遍历过, 那就收入map里面
map.insert(pair<int, int> (nums[i], i));
}
// 最后在map里面都没有找到, 那就返回空
return {};
}
};
- 这个题目要搞懂的四个点:
- 为什么要选取哈希的算法
- 哈希为啥要用map的数据结构
- map是用来干什么的
- map中的key是用来存放什么的, value是用来存放什么的
个人感觉, 搞懂这四个点, 那么此题目就理得条条顺顺喽!!!文章来源:https://www.toymoban.com/news/detail-603199.html
人是有惰性属性的动物,一旦过多地沉湎于温柔之乡,就更削弱了重新投入风暴的勇气和力量. — — 路遥<早晨从中午开始>文章来源地址https://www.toymoban.com/news/detail-603199.html
到了这里,关于C国演义 [第十一章]的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!