机试准备第10天

首先学习二分搜索法。使用二分查找需要先排序。第一题是查找，现学现卖。

//二分查找
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main(){int n;scanf("%d", &n);vector<int> a(n);for(int i = 0; i < n;i++){scanf("%d", &a[i]);}sort(a.begin(), a.end());int m;scanf("%d", &m);int b;for(int i = 0; i < m;i++){scanf("%d", &b);int left = 0;int right = n-1;while(left<=right){int mid = (left+right)/2;if(b == a[mid]) {printf("Yes\n");break;}else if(b < a[mid]) right = mid -1;else left = mid+1;}if(left > right) printf("NO\n");}}

使用map优化二分查找，把所有查找的数据放入map中，用map的键查找值，基于红黑树的map性能较好，但是会占用空间，如果map的时间性能依然不能满足，则选择unordered_map优化时间，unordered_map基于哈希查找，代价是更多的额外空间。

#include <vector>
#include <stdio.h>
#include <map>
#include <algorithm>
using namespace std;
int main(){int n;scanf("%d" , &n);map<int, int> map1;for(int i = 0; i < n;i++){int mid;scanf("%d", &mid);map1.insert({mid, i});}int m;scanf("%d", &m);for(int i = 0; i < m;i++){int b;scanf("%d", &b);if(map1.find(b) == map1.end()) printf("NO\n");else printf("YES\n");}
}

第二题是找位置，本题亮点在于使用map<char, vector<int>> map1，用vector作为键值对中的值，记录各个字符出现的下标位置。

#include <stdio.h>
#include <map>
#include <vector>
using namespace std;
int main(){char str[100];scanf("%s", str);map<char, vector<int>> timesMap;//记录每个字符的位置与次数vector<char> charseq;//记录每个字符出现的先后顺序string cstr = str;for(int i = 0; str[i] != '\0';i++){timesMap[str[i]].push_back(i);//如果是第一次出现if(timesMap[str[i]].size() == 1){charseq.push_back(str[i]);}}for(int i = 0; i < charseq.size();i++){if(timesMap[charseq[i]].size()>=2){printf("%c:%d", charseq[i], timesMap[charseq[i]][0]);for(int j = 1;j < timesMap[charseq[i]].size();j++){printf(",%c:%d", charseq[i], timesMap[charseq[i]][j]);}printf("\n");}}}

第三题是找最小数，经典的结构体sort排序。

#include <future>
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct  Num {int val1;int val2;
};
bool cmp(Num left, Num right) {if (left.val1 < right.val1) return true;else if (left.val1 == right.val1 && left.val2 < right.val2) return true;else return false;
}
int main() {int n;while (scanf("%d", &n) != EOF) {vector<Num> vec1(n);for (int i = 0; i < n; i++) {scanf("%d%d", &vec1[i].val1, &vec1[i].val2);}sort(vec1.begin(), vec1.end(), cmp);printf("%d %d\n", vec1[0].val1, vec1[0].val2);}
}

第四题是打印极值点下标，主要注意两侧特殊情况的判定。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main(){int n;scanf("%d", &n);vector<int> vec(n);for(int i = 0; i < n;i++){scanf("%d", &vec[i]);//读入数组}vector<int> res;//结果数组if(n==1) printf("0\n");else {if(vec[0]!=vec[1]) res.push_back(0);for(int i = 1; i <=(n-2);i++){if((vec[i]<vec[i-1]&&vec[i]<vec[i+1])||(vec[i]>vec[i-1]&&vec[i]>vec[i+1]))res.push_back(i);}if(vec[n-2]!=vec[n-1]) res.push_back(n-1);sort(res.begin(), res.end());for(int i = 0; i<res.size();i++){printf("%d ", res[i]);}printf("\n");}}

第五题是差分计数，又是华东师范的恶心题。

#include <unordered_map>
#include <stdio.h>
#include <vector>
using namespace std;
int main(){int n,x;scanf("%d%d", &n,&x);vector<int> vec(n);for(int i =0;i < n;i++){scanf("%d", &vec[i]);}unordered_map<int, long long> diffCount;for(int j = 0; j < n;j++){++diffCount[vec[j] + x];}long long count = 0;for(int i = 0; i < n; i++){count += diffCount[vec[i]];}printf("%lld\n", count);
}

下面进行字符串的学习，C风格的字符串不能支持赋值(=)，比较大小(><)，和判断相等(==)，因此在使用方面有麻烦。C++风格字符串支持比较运算符，类似于vector<char>，同样支持push_back等操作，缺点是不能printf与scanf。

#include <stdio.h>
#include <string>
using namespace std;
int main(){string str1 = "hello";string str2 = "world!";string str3; str3 = "hello";//string 支持 = 赋值//string支持==判断内容是否相同bool issame = false;issame =(str1==str3);//if(issame == true) printf("OK");//string支持 + 连接操作str3 = str1+str2;//printf("%s", str3.c_str());//string支持使用< <=比较大小，利用字典序//if(str2>str1) printf("OK");//string 非常像vector<char>string str4 = "abcdefg";char ch = str4[0];str4.push_back('F');//printf("%s", str4.c_str());string::iterator it;
//	for(it = str4.begin();it!=str4.end();it++){
//		printf("*it = %c\n", *it);
//	}it = str4.begin();str4.insert(it, 'A');it = str4.end()-1;str4.erase(it);
//	for(it = str4.begin();it!=str4.end();it++){
//		printf("*it = %c\n", *it);
//	}//string 对比vector 拓展了insert和erase的用法//string使用整数下标，插入删除多个字符str4.insert(0, "xyz");//整数下标 字符串常量str4.erase(0, 3);//两个整数下标，删除范围[0，3）//获取字串string str5;str5 = str4.substr(0, 3);//从0开始 长度为3//字符串匹配string str6 = "howdoyoudo";int pos = str6.find("dd", 0);printf("%d", pos);if(pos == string::npos) printf("找不到");//string与数值相互转换，to_string，Sto系列函数 Stoi , Stol...int i= 1234;string str7 = to_string(i);float j = 2.41;str7 = to_string(j);string str8 = "3.14159";j = stof(str8);//输入使用字符数组转化，输出使用string.c_str()
}

第六题是单词个数统计，没啥说的，简单模拟。

#include <stdio.h>
#include <string>
using namespace std;
int main(){char str1[1000];//单词数组int word = 0;int res[26] = {0};int letternum=0;while(scanf("%s", str1)!=EOF){word++;string str2 = str1;for(int i = 0; i<str2.size();i++){if(str2[i]>='a'&&str2[i]<='z') res[str2[i]-'a']++;else if(str2[i]>='A'&&str2[i]<='Z') res[str2[i]-'A']++;letternum++;}}int max = 0;printf("%d\n", letternum);printf("%d\n", word);for(int i = 0;i < 26;i++){if(res[i]>max) max = res[i];}for(int i = 0; i < 26;i++){if(res[i]==max) printf("%c ",'a'+i);}printf("\n");printf("%d", max);
}

第七题是字母统计，主要是搞清楚一行字符串的输入方法，getline(cin, str)。多行输入为while(getline(cin,str))。

#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
int main(){string str;while(getline(cin, str)){int res[26] = {0};for(int i = 0; i < str.size();i++){if(str[i] >= 'A' && str[i] <= 'Z')res[str[i] - 'A']++;}for(int i = 0;i < 26;i++){printf("%c:%d\n", 'A'+i, res[i]);}}}

第八题是替换单词，取巧成功哈哈哈。

#include <stdio.h>
#include <vector>
#include <string>
using namespace std;
int main(){char word[100];vector<string> res;while(scanf("%s", word)!=EOF){string str = word;res.push_back(str);}string before = res[res.size() - 2];string after = res[res.size() - 1];res.pop_back();res.pop_back();for(int i = 0; i < res.size();i++){if(res[i] == before) res[i] = after;}for(int i = 0; i < res.size();i++){printf("%s ", res[i].c_str());}}