| LeetCode题目 | 相关题目类型 | 相关链接 |
|---|---|---|
| 383 | 赎金信（简单难度） | 383. 赎金信 - 力扣（LeetCode） (leetcode-cn.com) |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int record[26]={0};
// 记录magazine里各个字符出现的次数
for(int i=0;i<magazine.length();i++){
record[magazine[i]-'a']++;
}
// 遍历ransomNote，在record里对应的字符个数做--操作
for(int j=0;j<ransomNote.length();j++){
record[magazine[i]-'a']--;
// 如果小于零，说明ransomNote里出现的字符，magazine里没有
if(record[magazine[i]-'a']<0){
return false;
}
}
return true;
}
};
类似题目：
| LeetCode题目 | 相关题目类型 | 相关链接 |
|---|---|---|
| 242 | 有效的字母异位词（简单难度） | 242. 有效的字母异位词 - 力扣（LeetCode） (leetcode-cn.com) |
数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。
定义一个数组叫做record用来上记录字符串s里字符出现的次数。
1、需要把字符映射到数组也就是哈希表的索引下表上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下表0，相应的字符z映射为下表25。
再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。
2、那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。
3、那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。
最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。
时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
for (int i = 0; i < s.size(); i++) {
// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
record[s[i] - 'a']++;
}
for (int i = 0; i < t.size(); i++) {
record[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (record[i] != 0) {
// record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
return false;
}
}
// record数组所有元素都为零0，说明字符串s和t是字母异位词
return true;
}
};
知识补充：
1、c++ memset()函数
memset 函数是内存赋值函数，用来给某一块内存空间进行赋值的；
包含在
原型为 ：
void *memset(void *s, int v, size_t n);
这里s可以是数组名，也可以是指向某一内在空间的指针；
v为要填充的值；
n为要填充的字节数；
示例1：
1
2
3
4
5
6
7
8
9
10
struct data
{
char num[100];
char name[100];
int n;
};
struct data a, b[10];
memset( &a, 0, sizeof(a) ); //注意第一个参数是指针类型，a不是指针变量，要加&
memset( b, 0, sizeof(b) ); //b是数组名，就是指针类型，不需要加&
示例2：
1
2
3
4
5
6
7
char str[9];
//我们用memset给str初始化为“00000000”，用法如下
memset(str,0,8);
//注意，memset是逐字节 拷贝的。
示例3：
1
2
3
4
5
6
7
8
9
10
11
int num[8];
//我们用memset给str初始化为{1,1,1,1,1,1,1,1}，
memset(num,1,8);//这样是不对的
//一个int是4个字节的，8个int是32个字节，所以首先要赋值的长度就不应该为8而是32。
//因为memset是 逐字节 拷贝，以num为首地址的8字节空间都被赋值为1，
//即一个int变为0X00000001 00000001 00000001 00000001，显然，把这个数化为十进制不会等于1的
2、 常见的 string 类构造函数有以下几种形式：
strings(num, c) //生成一个字符串，包含num个c字符
| LeetCode题目 | 相关题目类型 | 相关链接 |
|---|---|---|
| 1002 | 查找常用字符（简单难度） | 1002. 查找共用字符 - 力扣（LeetCode） (leetcode-cn.com) |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
vector<string> commonChars(vector<string>& words) {
vector<string> result;
if (words.size() == 0) return result;
int hash[26] = {0}; // 用来统计所有字符串里字符出现的最小频率
for (int i = 0; i < words[0].size(); i++) { // 用第一个字符串给hash初始化
hash[words[0][i] - 'a']++;
}
int hashOtherStr[26] = {0}; // 统计除第一个字符串外字符的出现频率
for (int i = 1; i < words.size(); i++) {
memset(hashOtherStr, 0, 26 * sizeof(int));
for (int j = 0; j < words[i].size(); j++) {
hashOtherStr[words[i][j] - 'a']++;
}
// 更新hash，保证hash里统计26个字符在所有字符串里出现的最小次数
for (int k = 0; k < 26; k++) {
hash[k] = min(hash[k], hashOtherStr[k]);
}
}
// 将hash统计的字符次数，转成输出形式
for (int i = 0; i < 26; i++) {
while (hash[i] != 0) { // 注意这里是while，多个重复的字符
string s(1, i + 'a'); // char -> string
result.push_back(s);
hash[i]--;
}
}
return result;
}
};
知识补充：
哈希数据结构：unordered_set
参考链接： C++ STL unordered_set容器完全攻略 (biancheng.net)
注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果是去除了重复的元素， 同时可以不考虑输出结果的顺序
那么用数组来做哈希表也是不错的选择，例如242. 有效的字母异位词
但是要注意，使用数组来做哈希的题目，是因为题目都限制了数值的大小。
而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
此时就要使用另一种结构体了，set ，关于set，C++ 给提供了如下三种可用的数据结构：
- std::set
- std::multiset
- std::unordered_set
std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。
c++ unordered_set容器的成员方法：
find(key): 查找以值为 key 的元素，如果找到，则返回一个指向该元素的正向迭代器；反之，则返回一个指向容器中最后一个元素之后位置的迭代器（如果 end() 方法返回的迭代器）。
思路如图所示：
| LeetCode题目 | 相关题目类型 | 相关链接 |
|---|---|---|
| 349 | 两个数组的交集（简单难度） |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set; // 存放结果
unordered_set<int> nums_set(nums1.begin(), nums1.end());
for (int num : nums2) {
// 下面的代码表示：发现nums2的元素 在nums_set里又出现过
//不理解的话，复习unordered_set的成员方法
if (nums_set.find(num) != nums_set.end()) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
拓展
那有同学可能问了，遇到哈希问题我直接都用set不就得了，用什么数组啊。
直接使用set 不仅占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。
不要小瞧 这个耗时，在数据量大的情况，差距是很明显的。
| LeetCode题目 | 相关题目类型 | 相关链接 |
|---|---|---|
| 350 | 两个数组的交集2（简单难度） | 350. 两个数组的交集 II - 力扣（LeetCode） (leetcode-cn.com) |
这道题和349不一样，没有要求 输出不能重复
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
// 对两个数组进行排序
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
int i=0,j=0;
vector<int> res;
//同时对两个数组遍历，有一个遍历完就结束
while(i<nums1.size() && j<nums2.size()){
// 相等，则添加到结果里
if(nums1[i]==nums2[j]){
res.push_back(nums1[i]);
++i;
++j;
}
else if(nums1[i]<nums2[j])
++i;
else
++j;
}
return res;
}
};
| LeetCode题目 | 相关题目类型 | 相关链接 |
|---|---|---|
| 202 | 快乐数（简单难度） | 202. 快乐数 - 力扣（LeetCode） (leetcode-cn.com) |
题目中说了会无限循环，即在求和的过程中，sum会重复出现，这一点对解题很重要。
正如：关于哈希表，你该了解这些！中所说，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。
这道题用哈希法，来判断这个sum是否重复出现，重复则return false， 否则一直找到sum为1为止。
判断sum是否重复出现就可以使用unordered_set。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
// 取数值各个位上的单数之和
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(1) {
int sum = getSum(n);
if (sum == 1) {
return true;
}
// 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
if (set.find(sum) != set.end()) {
return false;
} else {
set.insert(sum);
}
n = sum;
}
}
};
| LeetCode题目 | 相关题目类型 | 相关链接 |
|---|---|---|
| 1 | （简单难度） | 1. 两数之和 - 力扣（LeetCode） |
则要使用map，那么来看一下使用数组和set来做哈希法的局限。
数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下表。
C++中map，有三种类型：
映射 底层实现 是否有序 数值是否可以重复 能否更改数值 查询效率 增删效率 std::map 红黑树 key有序 key不可重复 key不可修改 O(logn) O(logn) std::multimap 红黑树 key有序 key可重复 key不可修改 O(logn) O(logn) std::unordered_map 哈希表 key无序 key不可重复 key不可修改 O(1) O(1) std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。
同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。 更多哈希表的理论知识请看关于哈希表，你该了解这些！。
这道题目中并不需要key有序，选择std::unordered_map 效率更高！
解题思路：
例如：nums=[2,7,11,15],target=9
遍历数组
1、寻找target-nums[i]是否在map中，
2、没有，9-2=7,7不在map中，把2和对应下标0放进map中
3、有，9-7=2,2在map中，找到了数值2和7相加等于9，返回其下标
遍历结束后，没有返回值，则返回空的数组
参考链接： C++ STL unordered_map容器用法详解 (biancheng.net)
C++代码：
>class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { std::unordered_map <int,int> map;//创建空的umap容器 for(int i = 0; i < nums.size(); i++) { //查找target - nums[i]是否在map中， 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 {}; } };
| LeetCode题目 | 相关题目类型 | 相关链接 |
|---|---|---|
| 49 | （中等难度） | 49. 字母异位词分组 - 力扣（LeetCode） (leetcode-cn.com) |
参考链接：https://blog.csdn.net/fuqiuai/article/details/83589593
解题思路：
1、对字符串每个词的字母按照字典序进行排序，异位词对字母进行排序后有相同的字母序列。
用排序后的字母序列作为map的key，将所有异位词都保存到字符串数组中，用map建立key和字符串数组之间的映射（不需要结果有序，所以用unordered map)
2、最后把归纳好的字符串数组存入结果res中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
vector<vector<string>> res;
if(strs.size()==0)return res;
// 键为string字符串类型，值为字符串数组类型
unordered_map<string,vector<string>> map1;
for(int i=0;i<strs.size();i++){
string s=strs[i];
sort(s.begin(),s.end());
// 排序后相同的字符串放到一个数组里，键为排序后的字符串
map1[s].push_back(strs[i]);//map1[s]是一个值类型为字符串的数组
}
for(auto v:map1){
res.push_back(v.second);
}
return res;
}
};