百度算法岗笔试-0329
投的是2022的暑期实习 计算机视觉算法研发工程师实习生
笔试编程两道题 全部AC
第一题:最长回文串01(leetcode : 5类似)
解题思路:中心扩展法求解最长回文串,分别以一个字符为中心和两个字符为中心,然后选择其中最长的那个
注意的点:这个题如果是 11111 or 000 返回0 所以有一个判断需要判断是否全为一样的值
代码:
#include <bits/stdc++.h>
using namespace std;
/*
1、回文串 判断
2、最长子串
3、双指针 中心扩展法
找回文串的难点在于，回文串的的长度可能是奇数也可能是偶数，
解决该问题的核心是从中心向两端扩散的双指针技巧。
*/
// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
string palindrome(string &s, int l, int r) {
// 防止索引越界 并且还要是回文
while (l >= 0 && r < s.length() && s[l] == s[r]) {
// 双指针，向两边展开
l--; r++;
}
// 返回以 s[l] 和 s[r] 为中心的最长回文串
// 这里要注意 l和r都是越界了的才会跳出while 所以 要把 l拉回界内 然后返回 r-l长度的子串
return s.substr(l+1, r-1-l);
}
string longestPalindrome(string s) {
string res = "";
for (int i = 0; i < s.length(); i++) {
// 以 s[i] 为中心的最长回文子串
string s1 = palindrome(s, i, i);
// 以 s[i] 和 s[i+1] 为中心的最长回文子串
string s2 = palindrome(s, i, i + 1);
// res = longest(res, s1, s2)
res = res.length() > s1.length() ? res : s1;
res = res.length() > s2.length() ? res : s2;
}
return res;
}
int main(){
string s;
string ans;
cin>>s; //输入一个 字符串s
map<char,int> mp; // 统计01出现的个数
int len = s.size();
for(int i=0; i<len; i++){
mp[s[i]]++;
}
// 如果0/1出现的次数和字符串长度一样那就输出0 返回
if(mp[s[0]]==len){
cout<<0;
return 0;
}
ans = longestPalindrome(s);
cout<<ans<<endl;
return 0;
} 第二题:礼物组合 (原题原题原题 去年百度就考了) 礼物分为a，b两个品种。组合的方式包括两种，一种是组合里有x件a类礼物加y件b类礼物，一种是组合里有x件b类礼物加y件a类礼物。求组合数最多
输入abxy 分别表示a的数量b的数量x和y的值
解题思路:贪心 大的-大的 小的-小的 直到a或b的数量为0
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b, x, y;
cin >> a >> b >> x >> y;
long long int ans=0;
// 大-大 小-小
while(a && b){
// a始终是大的
if(a<b){
int temp = a;
a = b;
b = temp;
}
// x始终是大的
if(x<y){
int temp = x;
x = y;
y = temp;
}
a = a-x;
b = b-y;
ans++;
}
cout<<ans;
return 0;
} 
查看17道真题和解析