我是安卓开发的,今天携程三个编程题都挺简单呐。。。(第一次有装逼的机会,第一次笔试ak啊啊啊,8:28搞定的~~)
1、 求最大字串和序列,经典的dp
怕超int,所以用了long long
#include <bits/stdc++.h>
using namespace std;
typedef int LL;
LL a[1000005];
int n;
/*请完成下面这个函数,实现题目要求的功能*/
/*当然,你也可以不按照下面这个模板来作答,完全按照自己的想法来 ^-^ */
/******************************开始写代码******************************/
int maxSum()
{
LL b=0;
int sum=-(1<<31);
cout<<sum;
for(int i=1;i<=n;i++)
{
if(b>0)
{
b+=a[i];
}
else
{
b=a[i];
}
cout<<b<<endl;
if(b>sum)
{
sum=b;
}
}
return sum;
}
/******************************结束写代码******************************/
int main() {
LL res;
int i=1;
while(~scanf("%lld",&a[i]))
{
i++;
}
n=i;
res = maxSum();
cout << res << endl;
return 0;
}
2、 找第一个单次出现的数字,复杂度要O(n),其实只要用map来hash一下就够了。对了,我的数字分解是自己写的,先在末尾加上一个逗号,然后遇到逗号就是一个数,再存起来。
#include <bits/stdc++.h>
using namespace std;
char s[1000005];
int a[1000005];
map<int ,int > m;
int n;
/*请完成下面这个函数,实现题目要求的功能*/
/*当然,你也可以不按照下面这个模板来作答,完全按照自己的想法来 ^-^ */
/******************************开始写代码******************************/
int findOnlyOneElment(int a[]) {
for(int i=0;i<n;i++)
{
if(m[a[i]]==1)
{
return a[i];
break;
}
}
}
/******************************结束写代码******************************/
int main() {
int res;
scanf("%s",s);
int len=strlen(s);
s[len]=',';
int b=0;
int j=0;
for(int i=0;i<=len;i++)
{
if(s[i]==',')
{
a[j++]=b;
m[b]++;
b=0;
}
else
{
b=b*10+(s[i]-'0');
}
}
n=j;
res = findOnlyOneElment(a);
cout << res << endl;
return 0;
}
3、 一开始没有看懂题目,看懂了就好办了。我是用暴力匹配,匹配上了标记为1,没有匹配上标记为0,补全9位(后面是补1)。
比如给的例子ABC,那么对于我来说就是
ABC 111111111
ABCD 111011111
ABDC 110111111
ABDCF 110101111
ABDFCG 110010111
ABDFGC 110001111
ADBCF 101101111
GABCEFG 011100011
所以其实就是暴力的去匹配resources,然后转成01串,排序输出就ok~
见代码~~
#include<bits/stdc++.h>
using namespace std;
struct node{
int a;
string b;
};
vector < string > res;
vector < node > v;
bool cmp( const node &v1, const node &v2)//注意:本函数的参数的类型一定要与vector中元素的类型一致
{
return v1.b > v2.b;//升序排列
}
/*请完成下面这个函数,实现题目要求的功能*/
/*当然,你也可以不按照下面这个模板来作答,完全按照自己的想法来 ^-^ */
/******************************开始写代码******************************/
void doFilter(string a)
{
int length=a.length();
for(int i=0;i<res.size();i++)
{
int k=0;
string b=res[i];
int len=b.length();
string ans="";
int f=0;
for(int j=0;j<len;j++)
{
if(b[j]==a[k])
{
ans=ans+"1";
k++;
}
else
{
ans=ans+"0";
}
if(k==length)
{
f=1;
for(int t=j+1;t<len;t++)
{
ans=ans+"0";
}
break;
}
}
if(f==0)
{
continue;
}
int si=ans.length();
for(int j=si;j<=8;j++)
{
ans=ans+"1";
}
node tt;
tt.a=i;
tt.b=ans;
v.push_back(tt);
}
if(v.size()==0)
{
cout<<-1<<endl;
return;
}
sort(v.begin(),v.end(),cmp);
for(int i=0;i<v.size();i++)
{
int k=v[i].a;
cout<<res[k]<<endl; }
}
/******************************结束写代码******************************/
int main()
{
res.push_back("AB");
res.push_back("ABC");
res.push_back("ACB");
res.push_back("ABCD");
res.push_back("ADBCF");
res.push_back("ABDCF");
res.push_back("ABDC");
res.push_back("ABDFCG");
res.push_back("ABDFGC");
res.push_back("ABDEFG");
res.push_back("GABCEFG");
string a;
cin>>a;
doFilter(a);
return 0;
}