今日学习的视频和文章
- 代码随想录 哈希表基础
- 代码随想录 有效的字母异位词
- 代码随想录 两个数组的交集
- 代码随想录 快乐数
- 代码随想录 两数之和
- C++Primer 容器的知识
LeetCode242 有效的字母异位词
- 初见题目时的想法：
- 直接使用
unordered_map，效率应该是不如使用数组的，不过题目的进阶提示里提到了考虑Unicode字符，使用unordered_map可以更好处理离散的键值，会比使用数组方便处理Unicode字符。但这道题目能取到的键值是连续的a-z，所以使用数组应该效率更好。
- 直接使用
初见题目时的题解（使用一个unordered_map，最后还要再遍历一次看各个字母对应的值是否是0，较慢）
bool isAnagram(string s, string t) {
unordered_map<char, int> charMap;
int n = s.length();
if (n != t.length()) return false;
for (int i = 0; i < n; i++) {
if (charMap.find(s[i]) == charMap.end()) {
charMap.insert({s[i], 1});
}
else {
charMap[s[i]]++;
}
if (charMap.find(t[i]) == charMap.end()) {
charMap.insert({t[i], -1});
}
else {
charMap[t[i]]--;
}
}
for (auto& iter : charMap) {
if (iter.second) {
return false;
}
}
return true;
}
使用两个unordered_map会快一些，但使用的内存空间更大。
bool isAnagram(string s, string t) {
unordered_map<char, int> charMapS, charMapT;
int n = s.length();
if (n != t.length()) return false;
for (int i = 0; i < n; i++) {
if (charMapS.find(s[i]) == charMapS.end()) {
charMapS.insert({s[i], 1});
}
else {
charMapS[s[i]]++;
}
if (charMapT.find(t[i]) == charMapT.end()) {
charMapT.insert({t[i], 1});
}
else {
charMapT[t[i]]++;
}
}
if (charMapS == charMapT) {
return true;
}
else {
return false;
}
}
- 看了代码随想录讲解后，既然这题能方便的看出哈希函数，而且也不需要处理哈希碰撞，那么直接使用数组作为哈希表就可以了。
完整的题解代码如下：
bool isAnagram(string s, string t) {
int hashArr[26] = { 0 };
if (s.length() != t.length()) {
return false;
}
int n = s.length();
for (int i = 0; i < n; i++) {
hashArr[s[i]-'a']++;
hashArr[t[i]-'a']--;
}
for (int i = 0; i < 26; i++) {
if (hashArr[i]) {
return false;
}
}
return true;
}
LeetCode349 两个数组的交集
- 初见题目时的想法：使用
unorder_set<int> set1来保存nums1中的元素，使用unorder_set<int> resSet在遍历nums2时来保存nums2在nums1中的元素，由于题解模板要求返回vector<int>，所以再将resSet中的元素放入res中。
题解代码如下：
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> set1;
unordered_set<int> resSet;
vector<int> res;
for (auto& iter : nums1) {
set1.insert(iter);
}
for (auto& iter : nums2) {
if (set1.find(iter) != set1.end()) {
resSet.insert(iter);
}
}
for (auto& iter : resSet) {
res.push_back(iter);
}
return res;
}
- 看了讲解之后，发现自己对C++STL的使用还是很不熟悉，需要多学习多理解。
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> set1(nums1.begin(), nums1.end());
/*
* 直接使用迭代器进行初始化，这和带范围的for循环的作用是一样的，但语句更简洁
* 直观的理解和带范围的for循环也是一样的，
* 即从容器的头一直循环到容器的尾来给set1进行insert操作来初始化set1
*/
unordered_set<int> resSet;
for (auto& iter : nums2) {
if (set1.find(iter) != set1.end()) {
resSet.insert(iter);
}
}
return vector<int>(resSet.begin(), resSet.end());
}
LeetCode202 快乐数
- 初见题目时的疑惑：怎么从无限循环中判断这个数不是快乐数呢？题目说了会无限循环但始终变不到
1，意思就是，只有有一个不为1的平方和出现两次，那么这个数就不是快乐数。至于严格的数学证明，那就超出我的能力范畴了。
顺便学习了一下C++STL的基础知识，不过这道题不需要保存各个数位，在分解数位时直接求平方和即可，所以不需要使用vector来保存各个数位。以下为初见题目时的题解：
class Solution {
public:
vector<int> splitDigits(int n) {
vector<int> res;
while (n) {
res.push_back(n % 10);
n /= 10;
}
return vector<int>(res.rbegin(), res.rend());
}
bool isHappy(int n) {
int sum = 0;
set<int> sumSet;
vector<int> digit = splitDigits(n);
while (true) {
for (auto& iter : digit) {
sum += pow(iter, 2);
}
if (sum == 1) {
return true;
}
else {
if (sumSet.find(sum) != sumSet.end()) {
return false;
}
else {
sumSet.insert(sum);
}
}
digit = splitDigits(sum);
sum = 0;
}
}
};
直接把求平方和写在循环内的题解：
class Solution {
public:
int getPowSum(int n) {
int sum = 0;
while (n) {
sum += pow(n % 10, 2);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
int sum = n;
set<int> sumSet;
while (true) {
sum = getPowSum(sum);
if (sum == 1) {
return true;
}
else {
if (sumSet.find(sum) != sumSet.end()) {
return false;
}
else {
sumSet.insert(sum);
}
}
}
}
};
LeetCode1 两数之和
- （噩）梦开始的地方，小时候最害怕的一集。
- 这题很早就尝试过了，也是从这题开始接触到了代码随想录，发现在课堂上听不懂学不会的算法，在代码随想录都有很详细的讲解（谢谢 Carl 哥）。
当时自己尝试的代码：时间复杂度显然为O(n^2)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int slow = 0;
int fast = 1;
int lth = nums.size();
vector<int> res;
while (slow < lth - 1) {
if (nums[slow] + nums[fast] == target) {
res.push_back(slow);
res.push_back(fast);
return res;
}
else if (fast < lth - 1) {
fast++;
}
else {
slow++;
fast = slow + 1;
}
}
return res;
}
};
- 这道题目，用哈希表的思想去考虑，就是在遍历数组的时候，用哈希表去存放遍历过的元素的下标，然后通过哈希表判断当前元素是否可以和某个遍历过的元素加起来等于
target。- 例如：现在
i指向的元素是6，target是9，那么我们只要去哈希表里找一下有没有存放过3的下标即可。
- 例如：现在
看了讲解之后的题解：
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashmap;
vector<int> res;
int lth = nums.size();
for (int i = 0; i < lth; i++) {
hashmap.insert({nums[i], i});
auto temp = hashmap.find(target - nums[i]);
if (temp != hashmap.end()) {
if (temp->second != i) {
res.push_back(temp->second);
res.push_back(i);
return res;
}
}
}
return res;
}
- 对
set和map的区别的思考
| set | map |
|---|---|
| 只关心 key 是否在 set 中，但不能保存 key 按某种规则对应的值 | 除了可以知道 key 是否在 map 中，还可以保存 key 按某种规则对应的值 |
| 这里的哈希表相当于把 key 映射到一个 bool 数组的下标，每个 key 对应的值只有出现过（true）和没出现过（false） | 这里的哈希表相当于把 key 映射到一个 T 类型数组的下标，每个 key 可以根据给定的模板对应到一个 T 类型的值 |
