机试准备第10天

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

1. //二分查找
2. #include <stdio.h>
3. #include <vector>
4. #include <algorithm>
5. using namespace std;
6. int main(){
7.     int n;
8.     scanf("%d", &n);
9.     vector<int> a(n);
10.     for(int i = 0; i < n;i++){
11.         scanf("%d", &a[i]);
12.     }
13.     sort(a.begin(), a.end());
14.     int m;
15.     scanf("%d", &m);
16.     int b;
17.     for(int i = 0; i < m;i++){
18.         scanf("%d", &b);
19.         int left = 0;
20.         int right = n-1;
21.         while(left<=right){
22.             int mid = (left+right)/2;
23.             if(b == a[mid]) {
24.                 printf("Yes\n");
25.                 break;
26.             }
27.             else if(b < a[mid]) right = mid -1;
28.             else left = mid+1;
29.         }
30.         if(left > right) printf("NO\n");
31.     }
32.    
33. }

复制代码

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

1. #include <vector>
2. #include <stdio.h>
3. #include <map>
4. #include <algorithm>
5. using namespace std;
6. int main(){
7.         int n;
8.         scanf("%d" , &n);
9.         map<int, int> map1;
10.         for(int i = 0; i < n;i++){
11.                 int mid;
12.                 scanf("%d", &mid);
13.                 map1.insert({mid, i});
14.         }
15.         int m;
16.         scanf("%d", &m);
17.         for(int i = 0; i < m;i++){
18.                 int b;
19.                 scanf("%d", &b);
20.         if(map1.find(b) == map1.end()) printf("NO\n");
21.         else printf("YES\n");
22.         }
23. }

复制代码

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

1. #include <stdio.h>
2. #include <map>
3. #include <vector>
4. using namespace std;
5. int main(){
6.         char str[100];
7.         scanf("%s", str);
8.         map<char, vector<int>> timesMap;//记录每个字符的位置与次数
9.         vector<char> charseq;//记录每个字符出现的先后顺序
10.         string cstr = str;
11.         for(int i = 0; str[i] != '\0';i++){
12.                 timesMap[str[i]].push_back(i);
13.                 //如果是第一次出现
14.                 if(timesMap[str[i]].size() == 1){
15.                         charseq.push_back(str[i]);
16.                 }}
17.        
18.         for(int i = 0; i < charseq.size();i++){
19.                 if(timesMap[charseq[i]].size()>=2){
20.                         printf("%c:%d", charseq[i], timesMap[charseq[i]][0]);
21.                         for(int j = 1;j < timesMap[charseq[i]].size();j++){
22.                                 printf(",%c:%d", charseq[i], timesMap[charseq[i]][j]);
23.                         }
24.                         printf("\n");
25.                 }
26.                
27.         }
28.        
29. }

复制代码

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

1. #include <future>
2. #include <stdio.h>
3. #include <vector>
4. #include <algorithm>
5. using namespace std;
6. struct  Num {
7.     int val1;
8.     int val2;
9. };
10. bool cmp(Num left, Num right) {
11.     if (left.val1 < right.val1) return true;
12.     else if (left.val1 == right.val1 && left.val2 < right.val2) return true;
13.     else return false;
14. }
15. int main() {
16.     int n;
17.     while (scanf("%d", &n) != EOF) {
18.         vector<Num> vec1(n);
19.         for (int i = 0; i < n; i++) {
20.             scanf("%d%d", &vec1[i].val1, &vec1[i].val2);
21.         }
22.         sort(vec1.begin(), vec1.end(), cmp);
23.         printf("%d %d\n", vec1[0].val1, vec1[0].val2);
24.     }
25. }

复制代码

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

1. #include <stdio.h>
2. #include <vector>
3. #include <algorithm>
4. using namespace std;
5. int main(){
6.         int n;
7.         scanf("%d", &n);
8.         vector<int> vec(n);
9.         for(int i = 0; i < n;i++){
10.                 scanf("%d", &vec[i]);//读入数组
11.         }
12.         vector<int> res;//结果数组
13.         if(n==1) printf("0\n");
14.         else {
15.                 if(vec[0]!=vec[1]) res.push_back(0);
16.                 for(int i = 1; i <=(n-2);i++){
17.                         if((vec[i]<vec[i-1]&&vec[i]<vec[i+1])||(vec[i]>vec[i-1]&&vec[i]>vec[i+1]))
18.                                 res.push_back(i);
19.                 }
20.                 if(vec[n-2]!=vec[n-1]) res.push_back(n-1);
21.                 sort(res.begin(), res.end());
22.                 for(int i = 0; i<res.size();i++){
23.                         printf("%d ", res[i]);
24.                 }
25.                 printf("\n");
26.         }
27.        
28. }

复制代码

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

1. #include <unordered_map>
2. #include <stdio.h>
3. #include <vector>
4. using namespace std;
5. int main(){
6.         int n,x;
7.         scanf("%d%d", &n,&x);
8.         vector<int> vec(n);
9.         for(int i =0;i < n;i++){
10.                 scanf("%d", &vec[i]);
11.         }
12.         unordered_map<int, long long> diffCount;
13.         for(int j = 0; j < n;j++){
14.                 ++diffCount[vec[j] + x];
15.         }
16.         long long count = 0;
17.         for(int i = 0; i < n; i++){
18.                 count += diffCount[vec[i]];
19.         }
20.         printf("%lld\n", count);
21. }

复制代码

下面进行字符串的学习，C风格的字符串不能支持赋值(=)，比力巨细(><)，和判断相等(==)，因此在使用方面有贫苦。C++风格字符串支持比力运算符，雷同于vector<char>，同样支持push_back等操纵，缺点是不能printf与scanf。

1. #include <stdio.h>
2. #include <string>
3. using namespace std;
4. int main(){
5.         string str1 = "hello";
6.         string str2 = "world!";
7.         string str3;
8.         str3 = "hello";//string 支持 = 赋值
9.         //string支持==判断内容是否相同
10.         bool issame = false;
11.         issame =(str1==str3);
12.         //if(issame == true) printf("OK");
13.         //string支持 + 连接操作
14.         str3 = str1+str2;
15.         //printf("%s", str3.c_str());
16.         //string支持使用< <=比较大小，利用字典序
17.         //if(str2>str1) printf("OK");
18.        
19.                
20.         //string 非常像vector<char>
21.         string str4 = "abcdefg";
22.         char ch = str4[0];
23.         str4.push_back('F');
24.         //printf("%s", str4.c_str());
25.         string::iterator it;
26. //        for(it = str4.begin();it!=str4.end();it++){
27. //                printf("*it = %c\n", *it);
28. //        }
29.         it = str4.begin();
30.         str4.insert(it, 'A');
31.         it = str4.end()-1;
32.         str4.erase(it);
33. //        for(it = str4.begin();it!=str4.end();it++){
34. //                printf("*it = %c\n", *it);
35. //        }
36.         //string 对比vector 拓展了insert和erase的用法
37.         //string使用整数下标，插入删除多个字符
38.         str4.insert(0, "xyz");//整数下标 字符串常量
39.         str4.erase(0, 3);//两个整数下标，删除范围[0，3）
40.         //获取字串
41.         string str5;
42.         str5 = str4.substr(0, 3);//从0开始 长度为3
43.         //字符串匹配
44.         string str6 = "howdoyoudo";
45.         int pos = str6.find("dd", 0);
46.         printf("%d", pos);
47.         if(pos == string::npos) printf("找不到");
48.         //string与数值相互转换，to_string，Sto系列函数 Stoi , Stol...
49.         int i= 1234;
50.         string str7 = to_string(i);
51.         float j = 2.41;
52.         str7 = to_string(j);
53.         string str8 = "3.14159";
54.         j = stof(str8);
55.         //输入使用字符数组转化，输出使用string.c_str()
56. }

复制代码

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

1. #include <stdio.h>
2. #include <string>
3. using namespace std;
4. int main(){
5.         char str1[1000];//单词数组
6.         int word = 0;
7.         int res[26] = {0};
8.         int letternum=0;
9.         while(scanf("%s", str1)!=EOF){
10.                 word++;
11.                 string str2 = str1;
12.                 for(int i = 0; i<str2.size();i++){
13.                         if(str2[i]>='a'&&str2[i]<='z') res[str2[i]-'a']++;
14.                         else if(str2[i]>='A'&&str2[i]<='Z') res[str2[i]-'A']++;
15.                         letternum++;
16.                 }
17.         }
18.         int max = 0;
19.         printf("%d\n", letternum);
20.         printf("%d\n", word);
21.         for(int i = 0;i < 26;i++){
22.                 if(res[i]>max) max = res[i];
23.         }
24.         for(int i = 0; i < 26;i++){
25.                 if(res[i]==max) printf("%c ",'a'+i);
26.         }
27.         printf("\n");
28.         printf("%d", max);
29. }

复制代码

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

1. #include <stdio.h>
2. #include <string>
3. #include <iostream>
4. using namespace std;
5. int main(){
6.     string str;
7.     while(getline(cin, str)){
8.         int res[26] = {0};
9.         for(int i = 0; i < str.size();i++){
10.             if(str[i] >= 'A' && str[i] <= 'Z')
11.             res[str[i] - 'A']++;
12.         }
13.         for(int i = 0;i < 26;i++){
14.             printf("%c:%d\n", 'A'+i, res[i]);
15.         }
16.     }
18.    
19. }

复制代码

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

1. #include <stdio.h>
2. #include <vector>
3. #include <string>
4. using namespace std;
5. int main(){
6.     char word[100];
7.     vector<string> res;
8.     while(scanf("%s", word)!=EOF){
9.         string str = word;
10.         res.push_back(str);
11.     }
12.     string before = res[res.size() - 2];
13.     string after = res[res.size() - 1];
14.     res.pop_back();
15.     res.pop_back();
16.     for(int i = 0; i < res.size();i++){
17.         if(res[i] == before) res[i] = after;
18.     }
19.     for(int i = 0; i < res.size();i++){
20.         printf("%s ", res[i].c_str());
21.     }
23. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。