网易互娱游戏笔试题--游戏研发工程师(2018.9.8)
AC了前两道题,推销下自己的博客,陆陆续续会有笔试面试总结,欢迎博客留言:https://bodycoder101.github.io/
第一题(压缩字符串)
解题思路:
- 只需找到连续字母的下标[i,j);判断之间的差值是否j-i>=4;
- 如果差值大于等于4,则按规则进行压缩,否则将子串substr(i,j-i)加入result;
- 只需遍历一遍字符串即可,时间复杂度为O(n)。
参考代码:
#include<iostream> #include<string> using namespace std; string compressionString(string str) { int len = str.size(); string result = ""; for (int i = 0; i <len;) { if (i< len-1 && str[i] == str[i + 1] - 1) { int j; //连续的区间[i, j-1],共有j-i个元素 for (j = i + 1; j < len && str[j] - str[j - 1] == 1; j++); if (j - i >= 4) { result.append(str[i]); result.append('-'); result.append(str[j - 1]); } else result += str.substr(i, j - i); i = j; } else result.append(str[i++]); } return result; } int main(int argc, char const *argv[]){ string str; int t; cin >> t; for (int i = 0; i < t; i++) { string str; cin >> str; str = compressionString(str); cout << str <<endl; } return 0; }
第二题(有关xy进制混合的)
解题思路:
- 使用对撞指针left,right,分别指向两端,相向扫描,维持两个区间求值va1=[0,left] ,va2=[right,end];
- if va1<va2 then left++;
- if va1>va2 then right--;
- if va1 == va2 && left+1 == right then return va1; 输出va1即为结果;
- 时间复杂度为o(n)。
参考代码:
#include <stdio.h> #include <iostream> #include <string>; using namespace std; int solutionForTwo(int x, int y, string z){ int length = z.length(); int left = 0; int right = length-1; int* reserve = new int [length]; for (int i = 0; i < length; i++) { if(isdigit(z[i])){ reserve[i] = z[i] - '0'; }else{ reserve[i] = z[i] - 'A' + 10; } } long xbase = reserve[left]; long ybase = reserve[right]; long ten = 1; while (left < right) { if (xbase == ybase) { if (left + 1 == right) { delete[] reserve; return xbase; } left++; right--; xbase = xbase*x + reserve[left]; ten *= y; ybase = ten*reserve[right] + ybase; } else if (xbase < ybase) { left++; xbase = xbase*x + reserve[left]; } else { right--; ten *= y; ybase = ten*reserve[right] + ybase; } } delete[] reserve; return -1; } int main(int argc, char const *argv[]) { int T,X,Y; string Z; std::cin >> T; for (int i = 0; i < T; i++) { cin>>X>>Y>>Z; std::cout << solutionForTwo(X,Y,Z)<<endl; } return 0; }#笔试题目##网易##网易互娱##题解#