随想录Day5|242. 有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和
242. 有效的字母异位词
给定两个字符串 s
和 t
,编写一个函数来判断 t
是否是 s
的字母异位词。
注意:若 s
和 t
中每个字符出现的次数都相同,则称 s
和 t
互为字母异位词。
1 <= s.length, t.length <= 5 * 104
s
和t
仅包含小写字母
来自卡尔的提示:用数组
第一想法
只要两个字符串的无序版本是一样的就可以了,本来脑子里浮现出的是类似Python的dict
,形如{char: frequency, ...}
,然后再判断是否一致。但是既然只包含小写字母那就可以只开一个长度为26的数组,分别记录26个字母的出现次数。
悄悄看了一眼题解,更方便的方法是遍历s
时在freq
数组中++
,遍历t
时在freq
数组中--
,当且仅当数组最终全为0的时候两个字符串是异位词。数组第i
个位置的值就是第i
个字母出现的次数。
用时9min~
bool isAnagram(string s, string t)
{
int freq[26] = {0};
for (int i = 0; i < s.size(); i++)
freq[s[i] - 'a']++;
for (int i = 0; i < t.size(); i++)
freq[t[i] - 'a']--;
for (int i = 0; i < 26; i++)
{
if (freq[i] != 0)
return false;
}
return true;
}
349. 两个数组的交集
给定两个数组 nums1
和 nums2
,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
来自卡尔的提示:用set
直接看题解了
感觉这个就是学用容器的事情,以及学到了range-based for循环的写法。主要就是熟悉接口和写法用的。
用时9min~
vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
{
unordered_set<int> result;
unordered_set<int> nums1_set(nums1.begin(), nums1.end());
for (int num : nums2)
{
if (nums1_set.find(num) != nums1_set.end()) // nums2中的元素nums1中出现过
result.insert(num);
}
return vector<int>(result.begin(), result.end());
}
202. 快乐数
编写一个算法来判断一个数 n
是不是快乐数。
「快乐数」 定义为:
- 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n
是 快乐数 就返回 true
;不是,则返回 false
。
提示:1 <= n <= 2^31 - 1
来自卡尔的提示:用set
第一想法
有点没头绪,由于是int
类型,取得每一个数位的值,就是while
循环不断除以10直到最高位?那是不是专门写个处理这个逻辑的函数比较好,输入数字,输出每个数位的平方和。然后在isHappy
中循环,如果有1就直接true
,如果无限循环怎么办呢?
那就把之前的中间结果都存在unordered_set
中,如果出现重复的就说明循环?并不是,不一定有重复结果就说明陷入了无限循环。
看了随想录题解的想法
题目中说了会 无限循环,那么也就是说求和的过程中,sum会重复出现,这对解题很重要!
所以这道题目使用哈希法,来判断这个sum是否重复出现,如果重复了就是return false, 否则一直找到sum为1为止。
所以可以保证这个过程得到的数字总是无限循环的,相当于题目告诉我们这个性质总是成立,所以确实一旦有重复结果就说明陷入了无限循环。1的平方还是1,所以1不会出现在这个循环中。
用时20min~
int getSum(int n)
{
int sum = 0;
while (n)
{
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n)
{
unordered_set<int> set;
while (true)
{
int sum = getSum(n);
if (sum == 1)
return true;
// sum重复了,已经陷入无限循环
if (set.find(sum) != set.end())
return false;
else
set.insert(sum);
n = sum;
}
}
1. 两数之和
给定一个整数数组 nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 target
的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
- 只会存在一个有效答案
来自卡尔的提示:用map
第一想法
如果暴力扫描就是\(O(n^2)\),那就没意思了!如果化为map则按照“值:下标”的格式,在数值num
的时候在map中寻找target - num
,如果不存在则下一个,否则返回答案。感觉很合理!
看了随想录题解的想法
可以用auto
写iter
好方便!并且学到了返回的比较好的写法!问了poe assistant,得到如下回答:
在C++中,
return {i, j}
表示返回一个初始化了两个值i
和j
的匿名对象。这个匿名对象的类型是根据花括号中的值进行推断的。如果
i
和j
具有相同的类型,那么返回的匿名对象类型将是一个std::pair
(或者是其它的元组类型,具体取决于编译器的实现)。例如,如果i
和j
都是整数类型,那么返回的类型将是std::pair<int, int>
。如果
i
和j
具有不同的类型,那么返回的匿名对象类型将是一个std::tuple
(或者是其它的元组类型)。例如,如果i
是整数类型,而j
是浮点数类型,那么返回的类型将是std::tuple<int, float>
。
时空复杂度均为\(O(n)\)。
用时13min~
vector<int> twoSum(vector<int> &nums, int target)
{
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++)
{
auto iter = map.find(target - nums[i]);
// auto其实是unordered_map<int, int>::iterator
if (iter != map.end())
return {iter->second, i};
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
碎碎念
今天好像也是速通流的,主要还是学习C++里面的一些写法,思路没有特别麻烦的。
再懒一天,从明天开始就要带上时空复杂度分析了!
标签:map,set,return,int,sum,随想录,202,数组,两数 From: https://www.cnblogs.com/alouette/p/17729025.html