什么是哈希表?直白来讲数组就是一张哈希表,哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素。
那么哈希表能解决什么问题呢, 一般哈希表都是用来快速判断一个元素是否出现集合里。
三种使用哈希解决问题的数据结构:
- 数组
- set undered_set
- map undered_map
当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。
有效的字母异位词
可以定义一个record数组,来记录字符串s里字符出现的次数,大小为26.
遍历的时候,只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可,并不需要记住字符a的ASCII,只要求出一个相对数值就可以了。
#include <iostream>
#include <string>
using namespace std;
bool result( string s, string t) {
int record[26] = {0};
for ( int i = 0; i < s.size(); i++) {
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) {
// cout << record[i] << endl;
return false;
}
return true;
}
}
int main() {
string s, t;
cout << "请输入第一个字符串:" << endl;
cin >> s;
cout << "请输入第二个字符串:" << endl;
cin >> t;
bool ans = result(s, t);
if (ans) {
cout << "是字母异位词。" << endl;
} else {
cout << "不是字母异位词。" << endl;
}
return 0;
}
两个数组的交集
#include <iostream>
#include <set>
#include<unordered_set>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> intersection( vector<int> &num1, vector<int> &num2) {
unordered_set<int> result;
unordered_set<int> num1_set(num1.begin(), num1.end());
for( int num : num2) {
if ( num1_set.find(num) != num1_set.end()) {
result.insert(num);
}
}
return vector<int>(result.begin(), result.end());
}
void myprint(int val) {
cout << val << " " ;
}
int main() {
vector<int> s( 3, 0); //初始化为包含10个0的方法
vector<int> t( 5, 0);
cout << "请输入第一个数组:" << endl;
for ( int &cnt : s) {
cin >> cnt;
}
cout << "请输入第二个数组:" << endl;
for ( int &cnt : t) {
cin >> cnt;
}
vector<int> ans = intersection(s, t);
for_each(ans.begin(), ans.end(), myprint);
return 0;
}
快乐数
无限循环,那么也就是说求和的过程中,sum会重复出现,这对解题很重要!
#include <iostream>
#include<unordered_set>
#include <algorithm>
using namespace std;
int getsum( int n) {
int sum = 0;
while (n) {
sum += ( n%10) * (n%10);
n /= 10;
}
return sum;
}
bool funct( int num) {
unordered_set<int> res;
while (1) {
int sum = getsum(num);
if ( sum == 1) {
return true;
}
if( res.find(sum) != res.end()) {
return false;
} else {
res.insert(sum);
}
num = sum;
// cout << num << endl;
}
}
int main() {
int num = 0;
cout << "请输入数值:" << endl;
cin >> num;
bool ans = funct(num);
if ( ans) {
cout << "该数值是快乐数。" << endl;
} else {
cout << "该数值不是快乐数。" << endl;
}
return 0;
}
//测试:19
两数之和
#include <iostream>
#include<unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
void myprint( int val) {
cout << val << " ";
}
vector<int> funct( vector<int>& v, int num) {
unordered_map<int,int> res;
for ( int i = 0; i < v.size(); i++) {
auto val = res.find(num - v[i]);
if ( val != res.end()){
return {val->second, i};
} else {
res.insert(pair<int, int>(v[i], i));
}
}
return {};
}
int main() {
int num = 0;
vector<int>v(4, 0);
cout << "请输入数组:" << endl;
for ( int& cnt : v) {
cin >> cnt;
}
cout << "请输入数值:" << endl;
cin >> num;
vector<int> ans = funct(v, num);
for_each(ans.begin(), ans.end(), myprint);
return 0;
}
四数相加
#include <iostream>
#include<unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
int funct( vector<int>& A, vector<int>& B, vector<int>& C,vector<int>& D) {
unordered_map<int, int> res;
int count = 0;
for( int a : A)
for (int b : B)
res[a+b]++;
for( int c : C){
for ( int d : D){
if( res.find(0 - (c+d)) != res.end()){
count += res[0 - (c+d)];
// cout << "count的值:"<< count << "对。" << endl;
}
}
}
return count;
}
int main() {
int num = 0;
vector<int>A(2, 0);
vector<int>B(2, 0);
vector<int>C(2, 0);
vector<int>D(2, 0);
cout << "请输入第一个数组:" << endl;
for ( int& cnt : A) {
cin >> cnt;
}
cout << "请输入第二个数组:" << endl;
for ( int& cnt : B) {
cin >> cnt;
}
cout << "请输入第三个数组:" << endl;
for ( int& cnt : C) {
cin >> cnt;
}
cout << "请输入第四个数组:" << endl;
for ( int& cnt : D) {
cin >> cnt;
}
int ans = funct( A, B, C, D);
cout << "一共有:"<< ans << "对。" << endl;
return 0;
}
赎金信
在这里插入图片描述
#include <iostream>
#include <string>
using namespace std;
bool funct( string a, string b) {
int record[26] = {0};
if ( a.size() > b.size()) {
return false;
}
for ( int i = 0; i < b.size(); i ++) {
record[a[i] - 'a']++;
}
for ( int i = 0; i < b.size(); i ++) {
record[a[i] - 'a']--;
if ( record[a[i] - 'a'] < 0) {
return false;
}
}
return true;
}
int main(){
string a, b;
cout << "请输入第一个字符串:" << endl;
cin >> a;
cout << "请输入第二个字符串:" << endl;
cin >> b;
bool ans = funct( a, b);
if (ans) {
cout << "字符串可以匹配。" << endl;
} else {
cout << "字符串不足以匹配。" << endl;
}
return 0;
}
三数之和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//打印二维数组的第一种方法
void myprint( vector<int>& val) {
for ( int num : val) {
cout << num << " ";
}
cout << endl;
}
//-1 0 1 2 -1 -4
vector<vector<int>> funct( vector<int>& A) {
vector<vector<int>> res;
sort(A.begin(), A.end());
for ( int i = 0; i < A.size(); i++) {
if( A[i] > 0) {
return res;
}
if( i > 0 && A[i] == A[i-1]){
continue;
}
int left = i+1;
int right = A.size()-1;
while( right > left) {
if (A[i] + A[left] + A[right] > 0) right--;
else if(A[i] + A[left] + A[right] < 0) left++;
else {
res.push_back(vector<int>{A[i], A[left], A[right]});
while(right > left && A[right] == A[right-1]) right--;
while(right > left && A[left] == A[left+1]) left++;
right--;
left++;
}
}
}
return res;
}
int main() {
int num = 0;
vector<int>A(6);
cout << "请输入数组:" << endl;
for ( int& cnt : A) {
cin >> cnt;
}
vector<vector<int>> ans = funct(A);
for_each(ans.begin(), ans.end(), myprint);
//打印二维数组的第二种方法
// for (vector<vector<int>>::iterator it = ans.begin(); it != ans.end(); it++) {
//
// for (vector<int>::iterator vit = (*it).begin(); vit != (*it).end(); vit++) {
// cout << *vit << " ";
// }
// cout << endl;
// }
return 0;
}
四数之和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//1 0 -1 0 -2 2
void myprint( vector<int>& val) {
for ( int num : val) {
cout << num << " ";
}
cout << endl;
}
vector<vector<int>> funct(vector<int>& nums, int target) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++) {
if (nums[k] > target && nums[k] >= 0) {
break;
}
// 对nums[k]去重
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
// 2级剪枝处理
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
break;
}
// 对nums[i]去重
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
right--;
// nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
} else if ((long) nums[k] + nums[i] + nums[left] + nums[right] < target) {
left++;
} else {
result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
// 对nums[left]和nums[right]去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时,双指针同时收缩
right--;
left++;
}
}
}
}
return result;
}
int main() {
int num = 0;
vector<int>A(6);
cout << "请输入数组:" << endl;
for ( int& cnt : A) {
cin >> cnt;
}
cout << "请输入和:" << endl;
cin >> num;
vector<vector<int>> ans = funct(A, num);
for_each(ans.begin(), ans.end(), myprint);
return 0;
}