2020/4/11 网易游戏后台开发笔试，4道编程题
好像不同的岗位做的题也不一样，我报的是后台开发，做了下面四题。第一题ac，第二题40%，第三题没做，第四题70%
1.九进制加法
2.聪明的厂长
3.组队
4.整理快递盒
---------------------------------------------------------------------------
第一题
我的C++解法：
class Solution {
public:
/**
* 接收两个表示9进制数的字符串，返回表示它们相加后的9进制数的字符串
* @param num1 string字符串 第一个加数
* @param num2 string字符串 第二个加数
* @return string字符串
*/
string add(string num1, string num2) {
string s1, s2, z1, z2;
s1 = findSmallPart(num1);
s2 = findSmallPart(num2);
z1 = findZhengPart(num1);
z2 = findZhengPart(num2);
int rest = 0;
string small = handleSmallPart(s1, s2, rest);
string zheng = handleZhengPart(z1, z2, rest);
if (small.size() == 0) {
return zheng;
}
return zheng + '.' + small;
}
char itos(int i) { // 将int 转换成 char
stringstream s;
string str;
s << i;
str = s.str();
return str[0];
}
string handleZhengPart(string z1, string z2, int rest) {
// 处理成等长
if (z1.size() != z2.size()) {
if (z1.size() > z2.size()) {
while (z1.size() > z2.size()) { z2.insert(0, 1, '0'); }
}
else if (z2.size() > z1.size()) {
while (z2.size() > z1.size()) { z1.insert(0, 1, '0'); }
}
}
string tmp(z1.size(), '0');
if (z1.size() != z2.size()) { cout << "mark2" << endl; return tmp; }
for (int i = z1.size() - 1; i >= 0; --i) {
int x1 = z1[i] - '0';
int x2 = z2[i] - '0';
int sum = x1 + x2 + rest;
if (sum < 9) {
tmp[i] = itos(sum);
rest = 0;
}
else {
tmp[i] = itos(sum - 9);
rest = 1;
}
}
if (rest != 0) {
tmp.insert(0, 1, itos(rest));
}
return tmp;
}
string handleSmallPart(string s1, string s2, int& rest) {
if (s1.size() == 0 && s2.size() == 0) {
return "";
}
// 处理成等长
if (s1.size() != s2.size()) {
if (s1.size() > s2.size()) {
while (s1.size() > s2.size()) { s2 += '0'; }
}
else if (s2.size() > s1.size()) {
while (s2.size() > s1.size()) { s1 += '0'; }
}
}
string tmp(s1.size(), '0');
if (s1.size() != s2.size()) { cout << "mark1" << endl; return tmp; }
for (int i = s1.size() - 1; i >= 0; --i) {
int x1 = s1[i] - '0';
int x2 = s2[i] - '0';
int sum = x1 + x2 + rest;
if (sum < 9) {
tmp[i] = itos(sum);
rest = 0;
}
else {
tmp[i] = itos(sum - 9);
rest = 1;
}
}
return tmp;
}
string findSmallPart(string num) {
string tmp;
int pointPos = -1;
for (size_t i = 0; i < num.size(); ++i) {
if (num[i] == '.') {
pointPos = i;
break;
}
}
if (pointPos == -1) {
return tmp;
}
for (size_t i = pointPos + 1; i < num.size(); ++i) {
tmp += num[i];
}
return tmp;
}
string findZhengPart(string num) {
string tmp;
int pointPos = -1;
for (size_t i = 0; i < num.size(); ++i) {
if (num[i] == '.') {
pointPos = i;
break;
}
}
if (pointPos == -1) {
return num;
}
for (int i = 0; i < pointPos; ++i) {
tmp += num[i];
}
return tmp;
}
};
int main() {
Solution sss;
string num1 = "1.28";
string num2 = "1.71";
cout << sss.add(num1, num2) << endl;
system("pause");
}
-------------------------------------------------------------------------
第二题
我用回溯法做的，通过40%，超时了。应该是可以继续剪枝，我不知道该怎么写了，希望评论区有大佬告知。
void DFS(vector<int> workPower, vector<int> staffHard, int worker, vector<int> hasDone, int& count) {
if (hasDone.size() == staffHard.size()) {
++count;
return;
}
for (size_t i = 0; i < staffHard.size(); ++i) {
if (workPower[worker] < staffHard[i] || find(hasDone.begin(), hasDone.end(), i) != hasDone.end()) {
continue;
}
hasDone.push_back(i);
DFS(workPower, staffHard, worker + 1, hasDone, count);
hasDone.pop_back();
}
}
int main() {
int n, m;
cin >> n;
vector<int> workPower(n);
vector<int> staffHard(n);
for (int i = 0; i < n; ++i) {
cin >> workPower[i];
}
for (int i = 0; i < n; ++i) {
cin >> staffHard[i];
}
cin >> m;
sort(workPower.begin(), workPower.end());
sort(staffHard.begin(), staffHard.end());
for (int i = 0; i < n; ++i) {
if (workPower[i] < staffHard[i]) {
cout << 0 << endl;
//system("pause");
return 0;
}
}
vector<int> hasDone;
int count = 0;
DFS(workPower, staffHard, 0, hasDone, count);
cout << count % m << endl;
//system("pause");
return 0;
} ------------------------------------------------------------------------
第三题，我没做，题目都很难看懂，不愧是游戏公司，出题都这么游戏化
----------------------------------------------------------------------------
第四题
我先将所有盒子按某一尺度（长宽高、体积）进行排序，然后从大到小遍历所有盒子，看能不装下前面更小的盒子。通过70%
我这方法纯属硬凑，希望有大佬解惑
class Solution {
public:
/**
*
* @param boxes int整型二维数组
* @param boxesRowLen int boxes数组行数
* @param boxesColLen int* boxes数组列数
* @return int整型
*/
int maxBoxes(int** boxes, int boxesRowLen, int* boxesColLen) {
// 转为vector
vector<vector<int> > Boxes;
int row = boxesRowLen, col = *boxesColLen;
for (int i = 0; i < row; ++i) {
vector<int> rowTmp;
for (int j = 0; j < col; ++j) {
rowTmp.push_back(boxes[i][j]);
}
Boxes.push_back(rowTmp);
}
// 1
sort(Boxes.begin(), Boxes.end(), sortByL);
vector<int> bigBox = Boxes.back();
int count1 = 1;
for (int i = Boxes.size() - 2; i >= 0; --i) {
if (leftContainRight(bigBox, Boxes[i])) {
++count1;
bigBox = Boxes[i];
}
}
// 2
sort(Boxes.begin(), Boxes.end(), sortByW);
bigBox = Boxes.back();
int count2 = 1;
for (int i = Boxes.size() - 2; i >= 0; --i) {
if (leftContainRight(bigBox, Boxes[i])) {
++count2;
bigBox = Boxes[i];
}
}
// 3
sort(Boxes.begin(), Boxes.end(), sortByH);
bigBox = Boxes.back();
int count3 = 1;
for (int i = Boxes.size() - 2; i >= 0; --i) {
if (leftContainRight(bigBox, Boxes[i])) {
++count3;
bigBox = Boxes[i];
}
}
// 4
sort(Boxes.begin(), Boxes.end(), sortByV);
bigBox = Boxes.back();
int count4 = 1;
for (int i = Boxes.size() - 2; i >= 0; --i) {
if (leftContainRight(bigBox, Boxes[i])) {
++count4;
bigBox = Boxes[i];
}
}
int count = max(max(max(count1, count2), count3), count4);
return count;
}
static bool sortByL(const vector<int>& b1, const vector<int>& b2) {
return b1.front() < b2.front();
}
static bool sortByW(const vector<int>& b1, const vector<int>& b2) {
return b1[1] < b2[1];
}
static bool sortByH(const vector<int>& b1, const vector<int>& b2) {
return b1[2] < b2[2];
}
static bool sortByV(const vector<int>& b1, const vector<int>& b2) {
return b1[0]*b1[1]*b1[2] < b2[0] * b2[1] * b2[2];
}
static bool leftContainRight(const vector<int>& b1, const vector<int>& b2) {
if (b1.size() != 3 || b2.size() != 3) {
cout << "Wrong data!" << endl;
return false;
}
if (b2[0] < b1[0] && b2[1] < b1[1] && b2[2] < b1[2]) {
return true;
}
else {
return false;
}
}
}; 
烽火星空一面4人在聊