我是后端开发岗位，题目大家可能不太一样，第一题是链表删除，第二题字符串第K大，第三题拆分位数和，第四题水桶，第五题回文串。
我是4AC，把代码贴出来感觉有点卖弄的意思了，不过因为私下问代码的同学实在是太多了，就发一下吧，一会就要考试了涨涨欧气。
1.pass
2.这里注意长度范围小于5000，但是k的范围是小于5的。
思路是先找a，如果存在找aa，否则找b……直到找到k个数为止。（这里应该有其他思路，不过因为K不大所以我的能过）
#include<bits/stdc++.h>
using namespace std;
int sum=0;
string s;
int k;
string ans="";
void dfs(int i,string str){
if(k==0)return;
if(str.size()!=0){
if(s.find(str)!=-1){
k--;
if(k==0)ans=str;
}else{
return;
}
}
str+='a';
for(char j='a';j<='z';j++){
str[i]=j;
dfs(i+1,str);
}
}
int main(){
cin>>s>>k;
dfs(0,"");
cout<<ans<<endl;
}
3.对于这个数的每一位，如果不是9的话向上一位借10,即是当前位最优解。不过这道题处理起来有点边界数据（因为9的存在），所以代码比较丑。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(ll x){
int ans=0;
int p=0;
while(x/10){
int t=x%10;
t+=p;
ans+=t;
if(t!=9){
ans+=10;
p=-1;
}
x/=10;
}
x+=p;
ans+=x;
return ans;
}
int main(){
ll x,n;
cin>>x;
while(x--){
cin>>n;
cout<<f(n)<<endl;
}
} 第四题：算简单的分治吧……代码依然有点丑，可以优化一些，但是懒得优化了。 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e3+10;
ll a[maxn];
int n;
const ll inf=1e9+10;
ll f(int l,int r);
ll down(int l,int r){
ll m=inf;
for(int i=l;i<r;i++)m=min(m,a[i]);
for(int i=l;i<r;i++){a[i]-=m;}
ll ans=m;
int ll=-1,rr=-1;
for(int i=l;i<r;i++){
if(a[i]==0){
if(rr!=-1){
ans+=f(ll,rr);
}
ll=-1;rr=-1;
}else{
rr=i+1;
if(ll==-1)ll=i;
}
}
if(ll!=-1)ans+=f(ll,rr);
for(int i=l;i<r;i++){a[i]+=m;}
return ans;
}
ll f(int l,int r){
if(l==r)return 0;
ll ans=r-l;
ans=min(ans,down(l,r));
//cout<<l<<" "<<r<<" "<<ans<<endl;
return ans;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
ll ans=f(0,n);
cout<<ans<<endl;
} 附加：第三题新写法（没有验证正确性）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(ll x){
if(x<10)return x;
int t=x%10;
if(t==9)return f(x/10)+9;
else return f(x/10-1)+t+10;
}
int main(){
ll n;
while(cin>>n){
cout<<f(n)<<endl;
}
}
全部评论
(5) 回帖