2022-3-22 百度笔试移动端Android岗(3/3)
题型
- 30个选择题,大概涉及到操作系统、计算机网络、安卓、数据库、数据结构、组合数/方案数、Java基础。30分。
- 问答题,安卓的场景题,30分。
- 编程题,3道,20*3=60分
编程题1
题意:
给出一个字符串,长度为1e6,每次操作可以删除或增加一个字符,求最小的操作数使得这个字符串里出现的字母个数都相同。保证字符串长度是出现的字母个数的倍数。
思路:
大概题意读出来有点假,可能是最后要求的字符串长度是不变?
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll cnt[26]; int main(){ string s; cin>>s; ll n=s.size(); memset(cnt,0,sizeof cnt); for(int i=0;i<n;i++){ int t=s[i]-'a'; cnt[t]++; } ll ans=0; ///长度只能为n? ll m=0; for(int i=0;i<26;i++){ if(cnt[i]!=0){ m++; } } ll tmp=n/m; for(int i=0;i<26;i++){ if(cnt[i]!=0){ ans+=abs(tmp-cnt[i]); } } cout<<ans<<endl; return 0; }
编程题2
多重背包的模板题,就是约束了每种物品最多用两次。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+7; int weight[maxn],value[maxn]; int dp[maxn]; int main(){ int n,w;cin>>n>>w; for(int i=1;i<=n;i++) cin>>weight[i]>>value[i]; for(int i=1;i<=n;i++){ for(int j=w;j>=weight[i];j--){ for(int k=1;k<=2&&j-weight[i]*k>=0;k++){ dp[j]=max(dp[j],dp[j-weight[i]*k]+value[i]*k); } } } int ans=0; for(int i=0;i<=w;i++) ans=max(ans,dp[i]); cout<<ans<<endl; return 0; }
编程题3
昨天学长刚出的题。
给出长度为1000的一个数删除k位使得剩下数值最大。
赛时写了一个O(nk)的写法。
贪心的考虑,数值最大就是高位的数越大越好。
那考虑什么时候才会删除,比如564,要删除一个的话,是删除5比较优的,因为5<6,所以6在前面更优。
然后每次都遍历一遍,如果当前位的数小于下一位的数,就删除当前位的数。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e6+7; int vis[maxn]; int main(){ string s;cin>>s; int k=s[0]-'0',n=s.size(); while(k--){ int i=0; for(i=0;i<n-1;i++){ if( (s[i]-'0') < (s[i+1]-'0') ){ break; } } for(int j=i;j<n-1;j++) s[j]=s[j+1]; n--; } for(int i=0;i<n;i++) cout<<s[i]; return 0; }
优化:
大体贪心思路跟朴素版的一样,如果k不为0,就将当前位的数跟之前的数比较,如果之前保存的数位小,就说明用当前数更优,也就是删除之前保存的数位,这样直到k为0.维护出来一个单调非递减的序列。
如果最后k还不为0,就从后面开始删。
时间复杂度O(n)
#include <bits/stdc++.h> using namespace std; #define ll long long string str; int main(){ int k; cin>>str>>k; ll len=str.size(); ll l=1,r=0; char c[len]; c[0]=str[0]; int flag=0; while(l<len){ if(k<=0) flag=1; if(flag) { c[++r]=str[l++]; } else { while(r>=0&&c[r]<str[l]){/// r--;k--; if(k<=0){ flag=1;break; } } c[++r]=str[l++]; } } for(int i=0;i<=r-k;i++){ printf("%c",c[i]); } return 0; }#百度实习##百度##笔经#