网易互娱 游戏研发工程师 笔试题
第二次发帖，也是网易第二次笔试，依然是4道做出来3道。哎，其实不是自己实力涨了，是网易笔试考察的主要是编程基本功，这次笔试就感觉没有深入考察算法，就是给一个游戏场景，写一个小任务。
再接再厉，秋招不易，算法得练！
第4题的大神，可以分享下题目和代码，谢谢啦！
- 七星不靠
147 | 258 | 369
万 | 饼 | 条
上述9张数字牌，配合（万 | 饼 | 条），从中随便丢掉2张，剩下的牌，是可以胡牌的。
现在，输入N个7张牌，判断能不能胡牌。
#include <bits/stdc++.h>
using namespace std;
bool check(int i, unordered_map<int, char> &num2tp)
{
char tt = 'A';
for (int i = 1; i < 10; i += 3)
{
if (num2tp.find(i) != num2tp.end())
{
if (tt == 'A')
tt = num2tp[i];
else
{
if (tt != num2tp[i])
{
printf("NO\n");
return false;
}
}
}
}
return true;
}
int main(int argc, char const *argv[])
{
int t;
cin >> t;
int num;
char tp;
while (t--)
{
unordered_map<int, char> num2tp;
unordered_set<char> allTypeOk;
bool ok = true;
for (int i = 0; i < 7; ++i)
{
scanf("%d%c", &num, &tp);
allTypeOk.insert(tp);
if (num2tp.find(num) != num2tp.end())
ok = false;
else
num2tp[num] = tp;
}
if (!ok || allTypeOk.size() != 3)
printf("NO\n");
else
{
bool ok = check(1, num2tp);
if (!ok)
continue;
ok = check(2, num2tp);
if (!ok)
continue;
ok = check(3, num2tp);
if (!ok)
continue;
printf("YES\n");
}
}
return 0;
} 2. 行列最大和 删除
给你一个N*N的矩阵，每次删除（行列和）最大的一行、一列，直到删完。求，每一步删除的行i和列j。请注意，行列交点处的数字，求和只算一次。
#include <bits/stdc++.h>
using namespace std;
void dfs(vector<vector<int>> &nums, vector<int> &colSum, vector<int> &rowSum)
{
if (nums.size() == 0)
return;
if (nums.size() == 1)
{
printf("1 1\n");
return;
}
int maxI = 0, maxJ = 0, maxSum = -1;
for (int i = 0; i < rowSum.size(); ++i)
{
for (int j = 0; j < colSum.size(); ++j)
{
if (rowSum[i] + colSum[j] - nums[i][j] > maxSum)
{
maxSum = rowSum[i] + colSum[j] - nums[i][j];
maxI = i, maxJ = j;
}
}
}
printf("%d %d\n", maxI + 1, maxJ + 1);
// delete row
for (int j = 0; j < colSum.size(); ++j)
{
colSum[j] -= nums[maxI][j];
}
nums.erase(nums.begin() + maxI);
rowSum.erase(rowSum.begin() + maxI);
// delete col
for (int i = 0; i < rowSum.size(); ++i)
{
rowSum[i] -= nums[i][maxJ];
}
colSum.erase(colSum.begin() + maxJ);
for (int i = 0; i < nums.size(); ++i)
{
nums[i].erase(nums[i].begin() + maxJ);
}
dfs(nums, colSum, rowSum);
}
int main(int argc, char const *argv[])
{
int n;
cin >> n;
vector<vector<int>> nums(n, vector<int>(n));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
scanf("%d", &nums[i][j]);
}
vector<int> colSum(n, 0);
vector<int> rowSum(n, 0);
for (int j = 0; j < n; ++j)
{
for (int i = 0; i < n; ++i)
{
colSum[j] += nums[i][j];
rowSum[i] += nums[i][j];
}
}
dfs(nums, colSum, rowSum);
return 0;
} 3. 明日之后 找出自身耗费时间最长的活动
比如，想要造一个柜子，需要3块木板，木板有需要伐木，和找树枝，大概这个样子，理解下父与子。
说白了，用括号表示就是，((())) 和 ((()()())())，所以要用栈啊。
#include <bits/stdc++.h>
using namespace std;
stack<pair<long long, long long>> st;
int main(int argc, char const *argv[])
{
long long T;
cin >> T;
while (T--)
{
long long n;
cin >> n;
long long t, e, s;
long long id = -1, maxTime = -1;
bool preIsEnd = false;
for (long long i = 0; i < n; ++i)
{
scanf("%lld %lld %lld", &t, &e, &s);
if (!s)
{
st.push(make_pair(t, 0));
preIsEnd = false;
}
else
{
pair<long long, long long> &item = st.top();
long long allTime = t - item.first;
long long selfTime = allTime - item.second;
if (selfTime > maxTime || selfTime == maxTime && id > e)
{
id = e;
maxTime = selfTime;
}
st.pop();
if (!st.empty())
{
if (preIsEnd)
st.top().second += allTime;
else
st.top().second += selfTime;
}
preIsEnd = true;
}
}
printf("%lld\n", id);
while (!st.empty())
st.pop();
}
return 0;
}
全部评论
(9) 回帖