科大讯飞7.31笔试思路
四道题全AC，分享一下自己的思路。
1.贪心算法，直接从最大面额开始求解
网上有类似
2.快速排序
#include <iostream>
#include<vector>
using namespace std;
void sort(vector<int>& arr,int left,int right)
{
if(left>=right)
return;
int tem=arr[left];
int i=left;
int j=right;
while(i!=j)
{
while(arr[j]>=tem&&i<j)
j--;
while(arr[i]<=tem&&i<j)
i++;
if(i!=j)
{
int k=arr[i];
arr[i]=arr[j];
arr[j]=k;
}
}
arr[left]=arr[i];
arr[i]=tem;
for(int k=0;k<arr.size();k++)
{
if(k==arr.size()-1)
cout<<arr[k]<<endl;
else
{
cout<<arr[k]<<" ";
}
}
sort(arr,left,i-1);
sort(arr,i+1,right);
}
int main()
{
int num;
vector<int> arr(num);
for(int i=0;i<num;i++)
cin>>arr[i];
sort(arr,0,arr.size()-1);
return 0;
}
3.相交条件：两个矩形的x和y的区间，都应该有交集
#include <iostream>
#include <vector>
using namespace std;
bool judge(pair<int,int>&s1,pair<int,int>&s2)
{
if((s1.second<s2.first)||(s2.second<s1.first))
return false;
return true;
}
int main()
{
vector<int> vec(8);
for(int i=0;i<8;i++)
cin>>vec[i];
vector<pair<int,int>> arr(4);
if(vec[0]>vec[2])
arr[0]=make_pair(vec[2],vec[0]);
else
{
arr[0]=make_pair(vec[0],vec[2]);
}
if(vec[1]>vec[3])
arr[1]=make_pair(vec[3],vec[1]);
else
{
arr[1]=make_pair(vec[1],vec[3]);
}
if(vec[4]>vec[6])
arr[2]=make_pair(vec[6],vec[4]);
else
{
arr[2]=make_pair(vec[4],vec[6]);
}
if(vec[5]>vec[7])
arr[3]=make_pair(vec[7],vec[5]);
else
{
arr[3]=make_pair(vec[5],vec[7]);
}
if(judge(arr[0],arr[2])&&judge(arr[1],arr[3]))
cout<<1<<endl;
else
{
cout<<-1<<endl;
}
return 0;
}
4.字符串转数字，一直向后寻找数字就行，然后累加
#include <iostream>
using namespace std;
int main()
{
string str;
getline(cin,str);
int i=0,flag=1;
long res=0;
while(str[i]==' ')
i++;
if(str[i]=='-')
flag=-1;
if(str[i]=='-'||str[i]=='+')
i++;
for(;i<str.size();i++)
{
if(isdigit(str[i]))
res=res*10+str[i]-'0';
if(res>=INT32_MAX&&flag==1)
{
cout<<INT32_MAX<<endl;
return 0;
}
if(res>INT32_MAX&&flag==-1)
{
cout<<INT32_MIN<<endl;
return 0;
}
}
cout<<res*flag<<endl;
return 0;
}
查看9道真题和解析
