首页 > 编程语言 >PAT_甲级_1050 String Subtraction (20分) (C++)【签到题/二分查找/字符串处理】

PAT_甲级_1050 String Subtraction (20分) (C++)【签到题/二分查找/字符串处理】

时间:2022-10-27 16:01:29浏览次数:51  
标签:1050 20 String s2 s1 mid return include scanf


目录

​1,题目描述​

​ 题目大意​

​2,思路​

​3,代码​

​4,测试效果​


1,题目描述

PAT_甲级_1050 String Subtraction (20分) (C++)【签到题/二分查找/字符串处理】_C++

Sample Input:

They are students.
aeiou

 

Sample Output:

Thy r stdnts.

 题目大意

将一个字符串s1中出现在另一个字符串s2的字符全部删除。

 

2,思路

题意很明确,所以关键在如何高效判断一个字符是否在s2中。

可以考虑先将s2进行排序,然后对字符串s1中每个字符c,利用二分查找判断是否在s2中。

 (效率完全OK!)

 

3,代码

#include<iostream>
#include<vector>
#include<string.h>
#include<map>
#include<math.h>
#include<algorithm>
#include<climits>
using namespace std;

bool cmp1(char a, char b){
return a < b;
}

vector<char> s1, s2;
bool find(char c){ //二分查找
int i = 0, j = s2.size() - 1, mid;
while(i <= j){
mid = (i + j) / 2;
if(s2[mid] == c)
return true;
else if(s2[mid] < c)
i = mid + 1;
else
j = mid - 1;
}
return false;
}
int main(){
//#ifdef ONLINE_JUDGE
//#else
// freopen("1.txt", "r", stdin);
//#endif

char c;
scanf("%c", &c);
while(c != '\n'){
s1.push_back(c);
scanf("%c", &c);
}
scanf("%c", &c);
while(c != '\n'){
s2.push_back(c);
scanf("%c", &c);
}


sort(s2.begin(), s2.end(), cmp1);

for(int i = 0; i < s1.size(); i++){
if(find(s1[i]) == false)
printf("%c", s1[i]);
}
return 0;
}

4,测试效果

PAT_甲级_1050 String Subtraction (20分) (C++)【签到题/二分查找/字符串处理】_二分查找字符串处理_02

标签:1050,20,String,s2,s1,mid,return,include,scanf
From: https://blog.51cto.com/u_15849465/5801392

相关文章