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 #include 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 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 #include #include using namespace std;int main(){ unordered_map cnt; int n; cin >> n; for(int i=0; i> s; cnt[s] = 1; } cout << cnt.size() << endl; // 请在此输入您的代码 return 0;}代码练习三，对应蓝桥，优质数对，代码见下
#include #include using namespace std;#define SB 1000000001#define ll long longint n;int A[100001];int B[100001];int main(){ cin >> n; for(int i=0; i> A[i]; } for(int i=0; i> B[i]; } unordered_map 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 #include 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 #include using namespace std;int n;int A[100001];int main(){ cin >> n; for(int i=0; i> 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 #include 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 1){ ret += \")\"; ret += \"(\"; cnt = 1; } } ret += s[i]; } ret += \")\"; if(flag == false){ ret = s; } // 请在此输入您的代码 cout << ret; return 0;}
