哔哩哔哩2020校园招聘后端笔试卷编程题思路+实现(2.9)
第一题(100),将字符串a变成b,可以执行三种操作插入、删除、修改,求最少操作数
实际上就是一个最长公共子序列的模板题,这里不多说了
最后答案=max(len1,len2)-dp[len1][len2]
#include<iostream> #include<cstring> #include<algorithm> using namespace std; string s1,s2; int main() { cin>>s1>>s2; int len1=s1.size(); int len2=s2.size(); int dp[len1+1][len2+1]; memset(dp,0,sizeof(dp)); for(int i=0;i<len1;i++) { for(int j=0;j<len2;j++) { dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]); if(s1[i]==s2[j]) { dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1]); } } } cout<<max(len1,len2)-dp[len1][len2]<<endl; }
第二题(90),给定一个正整数N(1-1e9),为有多少组连续的正整数之和恰好等于N
这道题通过率90%,应该是有哪里没有考虑全,麻烦各位大佬帮忙看看
思路是这样的,假设一个连续的正整数序列,首项是x,项数是k,那么需要满足公式 (x+(x+k-1))*k/2=n
稍微变形一下,可以得到 2x+k-1=2n/k
说明项数k是2n的一个约数,于是我们可以以根号n的复杂度便利1-根号n,一对一对的找出2n的约数,
然后对于每一个约数将其视作项数k,然后求对应的首项x,对于的x需要满足是整数且>1的条件
然后计算对于的组数既可以了,因为x,k是一一对应关系的,对于固定的项数,至多有一组合法解,所以说不用担心遗漏
便利的时候再特殊判断一下2*n是完全平方数的情况,不要将同一组答案记录两次就可以了,但是通过率是90%,应该还是有一点问题的,这里先放代码了
#include<iostream> #include<cstring> #include<algorithm> using namespace std; int n; int main() { cin>>n; n<<=1; int ans=0; for(int i=1;i*i<=n;i++) { if(n%i==0) { int k=i; int temp1=n/k; temp1=temp1+1-k; if((temp1%2)==0&&temp1/2>=1&&(temp1/2+k-1)<=n/2) ans++; if(i*i==n) break; k=n/i; temp1=n/k; temp1=temp1+1-k; if((temp1%2)==0&&temp1/2>=1&&(temp1/2+k-1)<=n/2) ans++; } } cout<<ans<<endl; }
第三题(100),处理键值对,键值对之间用字符1分割,键和值之间用字符2分割,问“合法”的键值对数量,并且按顺序输出
这道题有个坑,就是说合法的键值对,就是说键和值都不能是空字符串,不检查这个的话只有20%
具体的做法基本上就是写一个自动机来处理读入,最开始输入键,输入到字符2开始输入值,输入字符1之后判断键值对是不是合法的,合法的话存下来,继续开始输入键,以此类推
#include<iostream> #include<cstring> #include<algorithm> using namespace std; char c1,c2; string s; string k,v; int cnt; string k1[1111],v1[1111]; int main() { cin>>c1>>c2>>s; s=s+c1; int len=s.size(); k=""; v=""; int flag=0; for(int i=0;i<len;i++) { if(s[i]==c2) { flag=1; } else if(s[i]==c1) { flag=0; if(k!=""&&v!="") { k1[cnt]=k; v1[cnt]=v; cnt++; } k=""; v=""; } else if(flag==0) { k=k+s[i]; } else { v=v+s[i]; } } cout<<cnt<<endl; for(int i=0;i<cnt;i++) cout<<k1[i]<<" "<<v1[i]<<endl; }