总结leetcode75中哈希表/哈希集合的算法题解题思路。
上一篇:力扣75——滑动窗口
以下代码大部分为本人所写,少部分为官方示例代码。
1 找出两数组的不同
题目:
给你两个下标从 0 开始的整数数组 nums1 和 nums2 ,请你返回一个长度为 2 的列表 answer ,其中:
answer[0] 是 nums1 中所有 不 存在于 nums2 中的 不同 整数组成的列表。
answer[1] 是 nums2 中所有 不 存在于 nums1 中的 不同 整数组成的列表。
注意:列表中的整数可以按 任意 顺序返回。
题解:先用哈希表分别记录各自的元素,然后各自检测是否有不存在于对方的元素。
class Solution {
public:
vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> set1, set2; // nums1 与 nums2 所有元素的哈希集合
for (int num: nums1) {
set1.insert(num);
}
for (int num: nums2) {
set2.insert(num);
}
vector<vector<int>> res(2);
for (int num: set1) {
if (!set2.count(num)) {
res[0].push_back(num);
}
}
for (int num: set2) {
if (!set1.count(num)) {
res[1].push_back(num);
}
}
return res;
}
};
2 独一无二的出现次数
题目:
给你一个整数数组 arr,请你帮忙统计数组中每个数的出现次数。
如果每个数的出现次数都是独一无二的,就返回 true;否则返回 false。
题解:先用unordered_map记录每个字母出现的次数,然后把次数存日哈希表,如果哈希表的长度与map的长度一致,则证明次数都是独一无二的。
class Solution {
public:
bool uniqueOccurrences(vector<int>& arr) {
unordered_map<int,int> umap;
for (auto a : arr) {
if (umap.count(a)) {
umap[a] += 1;
}
else {
umap[a] = 1;
}
}
unordered_set<int> uset;
for (auto iter = umap.begin(); iter != umap.end(); iter++) {
uset.insert(iter->second);
}
return umap.size() == uset.size();
}
};
3 确定两个字符串是否接近
题目:
如果可以使用以下操作从一个字符串得到另一个字符串,则认为两个字符串 接近 :
操作 1:交换任意两个 现有 字符。
例如,abcde -> aecdb
操作 2:将一个 现有 字符的每次出现转换为另一个 现有 字符,并对另一个字符执行相同的操作。
例如,aacabb -> bbcbaa(所有 a 转化为 b ,而所有的 b 转换为 a )
你可以根据需要对任意一个字符串多次使用这两种操作。
给你两个字符串,word1 和 word2 。如果 word1 和 word2 接近 ,就返回 true ;否则,返回 false 。
题解:根据题目意思,字符串接近有2个条件:第一个:2个字符串的字符种类一致;第二个:2个字符串中各类字符出现次数的集合相等。
class Solution {
public:
bool closeStrings(string word1, string word2) {
// 验证word1和word2长度相同
if(word1.length() != word2.length()) return false;
// 验证word1和word2包含的字母相同
vector<int> v1(26, 0), v2(26, 0);
for(char c : word1) v1[c - 'a']++;
for(char c : word2) v2[c - 'a']++;
for(int i = 0; i < 26; ++i){
if((v1[i] == 0 && v2[i] != 0)
||(v1[i] != 0 && v2[i] == 0)) return false;
}
// 验证word1和word2“结构”相同
sort(v1. begin(), v1.end());
sort(v2. begin(), v2.end());
if(v1 != v2) return false;
return true;
}
};
4 相等行列对
题目:
给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ,返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目。
如果行和列以相同的顺序包含相同的元素(即相等的数组),则认为二者是相等的。
题解:将行存入哈希表,然后遍历每一列。文章来源:https://www.toymoban.com/news/detail-604171.html
class Solution {
public:
int equalPairs(vector<vector<int>>& grid) {
int n = grid.size();
map<vector<int>, int> cnt;
for (auto row : grid) {
cnt[row]++;
}
int res = 0;
for (int j = 0; j < n; j++) {
vector<int> arr;
for (int i = 0; i < n; i++) {
arr.emplace_back(grid[i][j]);
}
if (cnt.find(arr) != cnt.end()) {
res += cnt[arr];
}
}
return res;
}
};
1-4 解题总结
这几道题都比较简单。
特点:当需要对一串数据做统计时,可以考虑用哈希表。文章来源地址https://www.toymoban.com/news/detail-604171.html
到了这里,关于力扣75——哈希表/哈希集合的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!