一、在相邻差为 1 的整数数组中进行有效搜索
时间限制： 1000MS
内存限制： 65536KB
题目描述：
给定一个由n 个整数组成的数组。每个数组元素是通过将 +1 或 -1 添加到前一个元素获得的，即任意两个连续元素之间的绝对差为 1。
任务是搜索具有最少比较次数的元素索引（小于简单的逐元素搜索） . 如果元素多次出现，则打印最小的索引。如果元素不存在，则打印 -1。
例子：
输入描述
输入： arr[] = {5, 4, 5, 6, 5, 4, 3, 2} x = 4。
输入： arr[] = { 5, 4, 5, 6, 4, 3, 2, 3 } x = 9。
输出描述
输出： 1 //元素 x 第一次出现在 索引 1。
输出： -1 //元素 x 不存在于 arr[]
样例输入
5, 4, 5, 6, 5, 4, 3, 2
4
样例输出
1
AC代码：
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<set>
#include<map>
using namespace std;
int main()
{
vector<int> a;//arr数组
int num;//输入的数
char c;//存入空格或回车，如果是回车则arr数组输入完毕，退出while循环
while(scanf("%d",&num)!=EOF){
a.push_back(num);
if(c=getchar()=='\n')
break;
}
int len=a.size();
int found=0;
//int count=0;
int to_search;//to_search为要找的数
scanf("%d",&to_search);
int i,next;//i为arr数组的index，next为i的下一个值
for( i=0;i<len;i+=next){
//++count;
if(a[i]==to_search){
found=1;
break;
}
else{
next=abs(a[i]-to_search);//因为任意两个连续元素之间的绝对差为 1，所以next的值
}
}
if(found){
printf("%d\n",i);
}
else{
printf("-1\n");
}
return 0;
}
二、字符串匹配，其中一个字符串包含通配符
时间限制： 1000MS
内存限制： 65536KB
题目描述：
给定两个字符串，其中第一个字符串可能包含通配符，第二个字符串是普通字符串。编写一个函数，如果两个字符串匹配则返回 true。以下是第一个字符串中允许的通配符。
- *–> 匹配任何字符或字符集的 0 个或多个实例。
- ? --> 匹配任意一个字符。
如，“f* sh”匹配与“fish”匹配。并且字符串“fu?anm * ”与“fudanmicro”匹配(注意第一个字符串末尾的’* ')。但是“f *a”与“fish”不匹配，因为第二个字符串中不存在字符“a”。
输入描述
第一个字符串可能包含通配符，第二个字符串是普通字符串
输出描述
匹配输出yes，反之输出no
样例输入
fu?anm*
fudanmicro
样例输出
yes
下面代码虽然考试的时候AC了，但有缺陷，待修改，仅供参考，如果有修改建议，欢迎评论指出：
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<set>
#include<map>
using namespace std;
string s1,s2;
bool match(int s1loc,int s2loc){
if(s1loc>=s1.size())
return true;
if(s1[s1loc]=='?' || s1[s1loc]==s2[s2loc] ){
return match(s1loc+1,s2loc+1);
}
else if(s1[s1loc]=='*'){
int flag=0;
for(int i=s2loc;i<=s2.size();i++){
flag+=match(s1loc+1,i);
}
return flag;
}
else
return false;
}
int main()
{
cin>>s1>>s2;
if(match(0,0)){
cout<<"yes\n";
}
else {
cout<<"no\n";
}
return 0;
}
三、找出所有零和的三元组
时间限制： 1000MS
内存限制： 65536KB
题目描述：
输入int数组。任务是编写C/C++程序在数组中找到总和为零的三元组，要求时间复杂度为 O(n2 )。
例子 ：
输入： arr[] = {0, -1, 2, -3, 1}
输出： 0 -1 1, 2 -3 1
说明：总和为零的三元组是0 + -1 + 1 = 0 和 2 + -3 + 1 = 0
输入： arr[] = {1, -2, 1, 0, 5}
输出： 1 -2 1
解释：总和为零的三元组是1 + -2 + 1 = 0
输入描述
一：
0, -1, 2, -3, 1
二：
1, -2, 1, 0, 5
三：
-5 6 7 -3 1
输出描述
一：
0 -1 1
2 -3 1
二：
1 -2 1
三：
No Triplet Found
AC代码：
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<map>
using namespace std;
vector<vector<int>> result;
void findTriplets(vector<int>& arr,int n){
bool found=false;
for(int i=0;i<n-1;i++){
unordered_set<int> s;
for(int j=i+1;j<n;j++){
int x=-(arr[i]+arr[j]);
if(s.find(x)!=s.end()){
result.push_back({arr[i],x,arr[j]});
found=true;
}else{
s.insert(arr[j]);
}
}
}
// if(found==false){
//
// }
}
int main()
{
int num;
vector<int> arr;
char c;
while(scanf("%d",&num)!=EOF){
arr.push_back(num);
if(c=getchar()=='\n')
break;
}
int n=arr.size();
findTriplets(arr,n);
if(result.size()==0){
cout<<"No Triplet Found\n"<<endl;
}
else{
for(int i=0;i<result.size();i++){
for(int j=0;j<3;j++){
if(j!=0) cout<<" ";
cout<<result[i][j];
}
cout<<endl;
}
}
return 0;
}
