首页 > 小菜鸡第一次编程题ac,百度笔试(9.3)
头像
根号7
编辑于 2020-09-04 05:16
+ 关注

小菜鸡第一次编程题ac,百度笔试(9.3)

rt,比较激动,不过百度的前两题感觉挺简单的,基本一遍过。
第一题忘了是啥了。。
第二题 演员期望值:两个数组,一个表示演员期望值,一个表示角色属性值,角色属性值大于等于演员期望即匹配,要求输出匹配最多时的角色属性值索引(按演员输入顺序,没有匹配的为-1)
两个数组,用pair存一下值和索引,然后排序,贪心就ok了,代码甚至都没存。。凭记忆写了一下
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int m, n;
cin >> n >> m;
vector<pair<int, int> > person(n);
vector<pair<int, int> > role(m);
vector<int> res(n);
for (int i = 0; i < n; i++) {
cin >> person[i].first;
person[i].second = i;
}
for (int i = 0; i < m; i++) {
cin >> role[i].first;
role[i].second = i;
}
//
sort(person.begin(), person.end());
sort(role.begin(), role.end());
int index1 = 0, index2 = 0;
while (index1 < n) {
if (index2 < m) {
if (person[index1].first <= role[index2].first) {
res[person[index1++].second] = role[index2].second + 1;
}
index2++;
}
else {
res[person[index1++].second] = -1;
}
}
for (int i = 0; i < n; i++) {
cout << res[i] << ' ';
}
cout << endl;
}
return 0;
}
第三题 上楼梯,一次可以走1~m阶,共n阶,每次走的步数不能和前面两次相同,问到最后一阶有几种走法(输出对1e9+7取余数)
思路就是动态规划,本来想的是dp数组,dp[i]存一个map,键值是前两次走的步数,然后依次更新即可。但是unordered_map没有pair作为键值的构造函数,还好以前特意写过
#include<iostream>
#include <vector>
#include <unordered_map>
using namespace std;
struct pair_hash {
template<class t1, class t2>
std::size_t operator () (const std::pair<t1, t2>&p) const
{
auto h1 = std::hash<t1>{}(p.first);
auto h2 = std::hash<t2>{}(p.second);
return h1^h2;
}
};
int mod = 1000000007;
int main() {
int m, n;
cin >> n >> m;
vector<unordered_map<pair<int, int>, int, pair_hash> > dp(n + 1);    //first 上一步, second 上两步
dp[0][{mod + 1, mod + 1}] = 1;
for (int i = 1; i <= n; i++) {
int j;
for (j = i - 1; j >= 0 && i - j <= m; j--) {
for (auto& it : dp[j]) {
if (it.first.first != i - j&&it.first.second != i - j) {
dp[i][{i - j, it.first.first}] = (dp[i][{i - j, it.first.first}] + it.second) % mod;
}
}
}
while (j >= 0 && !dp[j].empty()) {
dp[j--].clear();
}
}
int res = 0;
for (auto& it : dp[n]) {
res = (res + it.second) % mod;
}
cout << res << endl;
return 0;
}
不过一直卡在80%、90%,想了半天,应该是空间超了,于是加了
while (j >= 0 && !dp[j].empty()) {
dp[j--].clear();
}
这一段去清除多余的dp占用的内存。最后还剩10分钟惊险过关。
看了看别的大佬的思路,可以不用哈希表,而用三维数组来实现,而且dp数组只需要维护长度为m的一段就可以了,所以这个代码还是有优化空间的。
总的感觉还是选择题比较难,好几个都不会。。。希望自己再接再厉,早日被捞,也祝愿大家offer多多,早日上岸。

全部评论

(5) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐