C++ 哈希算法、贪心算法
哈希算法：辅助数组h[1001]， h[x]代表x出现的次数，整数技术器c。
算法：遍历这n个数，对于遍历到的第i个数x，计算出以下数字 y = h[x - 1] + h[x + 1]直接累加到计数器c上（因为h[x]代表x的出现次数），把当前遍历到的x这个数，执行以下操作，h[x] = h[x] + 1，代表增加x的计数。（缺点：如果数字范围很大很散，就会导致开不出这么大的空间）。
为了解决上述提到的缺点，会采取取模等方式，也会出现哈希冲突等情况，也会有对应的哈希冲突解决方案。
代码分析：
1 初始化哈希表
function hashInit(){
for i -> (0, HMAX-1)
hash[i] = -1;
}
2 哈希插入
function hashInsert(x){
y = x % HMAX;
while(1)
if(hash[y] == -1)
hash[y] = x
cnt[y] = 1
return
else if(hash[y] == x)
cnt[y]++
return
if(++y >= HMAX)
y = 0
}
哈希查找
function hashGet(x)
y = x % HMAX
while(1)
if(hash[y] == -1)
return 0
else if(hash[y] == x)
return cnt[y]
if(++y >= HMAX)
y = 0
在C++中，unordered_map 是对应的哈希表
代码练习，对应蓝桥云课 字符统计 代码见下
#include <iostream>
#include <string>using namespace std;
int main()
{string s;int hash[256] = {0};cin >> s;for(int i=0; i<s.size(); ++i){hash[s[i]]++;}int maxc = 0;char ret[256];int retSize = 0;for(char c = 'A'; c <= 'Z'; c++){if(hash[c] > maxc){maxc = hash[c];retSize = 0;ret[retSize++] = c;}else if(hash[c] == maxc){ret[retSize++] = c;}}ret[retSize] = '\0';cout << ret << endl;// 请在此输入您的代码return 0;
}代码练习 2 对应蓝桥云课 字符串统计，代码见下
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int main()
{unordered_map<string, int> cnt;int n;cin >> n;for(int i=0; i<n; ++i){string s;cin >> s;cnt[s] = 1;}cout << cnt.size() << endl;// 请在此输入您的代码return 0;
}代码练习三，对应蓝桥，优质数对，代码见下
#include <iostream>
#include <unordered_map>
using namespace std;#define SB 1000000001
#define ll long long
int n;
int A[100001];
int B[100001];int main()
{cin >> n;for(int i=0; i<n; ++i){cin >> A[i];}for(int i=0; i<n; ++i){cin >> B[i];}unordered_map<ll, int> h;long long ret = 0;for(int j=0; j<n; ++j){ll y = (ll)B[j]*SB + A[j];ret += h[y];ll x = (ll)A[j]*SB + B[j];h[x]++;}cout << ret << endl;// 请在此输入您的代码return 0;
}贪心算法在每一步均采取当前状态下的最优（局部最优）策略，以期望获得全局最优解
代码练习 对应蓝桥云课 翻硬币，代码见下
#include <iostream>
#include <string>
using namespace std;string s, t;int main()
{cin >> s;cin >> t;int n = s.size();int ret = 0;for(int i=0; i<n; ++i){if(s[i] != t[i]){s[i] = (s[i] == 'o' ? '*' : 'o');s[i+1] = (s[i+1] == 'o' ? '*' : 'o');++ret;}}cout << ret << endl;// 请在此输入您的代码return 0;
}代码练习，对应蓝桥云课 一键3连，代码见下
#include <iostream>
#include <algorithm>
using namespace std;int n;
int A[100001];int main()
{cin >> n;for(int i=0; i<n; ++i){cin >> A[i];}sort(A, A+n);int l=1, r=1;while(r < n){if(A[r] != A[l-1]){A[l++] = A[r];}r++;}int res = 0;for(int i=0; i+2<l; ++i){int a = A[i];if(A[i+1] == a+1 && A[i+2] == a+2){++res;}}cout << res << endl;// 请在此输入您的代码return 0;
}代码练习，对应蓝桥云课 分开元音字母，代码见下
#include <iostream>
#include <string>
using namespace std;bool isYuanyin(char c){return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}string s;
string ret;int main()
{cin >> s;ret = "(";bool flag = false;int cnt = 0;for(int i=0; i<s.size(); ++i){if(isYuanyin(s[i])){cnt++;flag = true;if(cnt > 1){ret += ")";ret += "(";cnt = 1;}}ret += s[i];}ret += ")";if(flag == false){ret = s;}// 请在此输入您的代码cout << ret;return 0;
}