复盘：广州某游戏公司后端校招笔试

LN游戏笔试复盘

0. 写在前面

这次笔试应该算是我第一次正式的笔试。这次笔试复盘即使为了查漏补缺，也是为了纪念第一次笔试吧。试题是HR和我约好时间通过邮箱给我发送的，是一份word文档。首先要吐槽一下试卷的格式：竟然是用word文档的方式，现在大家不都是使用第三方公司或者自己研发的考试系统嘛= =。算了看一下题目：一共十道题，时间给了40分钟。其中C++基础概念题（简答题）3道，基础算法题7道。整体来说难度不大，但是题量十分巨大！

1. C++基础概念题

1. 请解释封装、继承和多态。
   封装：
   ??封装就是将数据和行为相结合，抽象为一个整体，形成一个类。类中的数据和函数都是类的成员。我们可以使一部分成员充当类与外部的接口，而将其它的成员隐藏起来。这样就限制了外部对成员的访问，也使不同类之间的影响度降低。目的在于将对象的使用者和设计者分开，以提高软件的可维护性和可修改性。
   继承：
   ??继承就是新类从已有类那里得到已有的特性。类的派生指的是从已有类产生新类的过程。原有的类成为基类或父类，产生的新类称为派生类或子类。子类继承基类后，可以创建子类对象来调用基类函数，变量等。继承是代码重用的重要工具。
   多态：
   ??多态就是一个接口，多种实现。具体体现在调用同一个函数名，可以根据需要实现不同的功能。多态分为两种编译时多态和运行时多态。
   ??静态多态（早绑定、编译时多态、重载）：程序在编译之前就知道用哪个函数，即在一个类中有相同的函数名，也就是函数重载。
   ??动态多态（晚绑定、运行期多态、覆盖 、重写）：程序在运行过程中，根据调用函数的对象实体，决定具体使用哪一个函数。运行期多态的实现依赖于虚函数机制。当某个类声明了虚函数时，编译器将为该类对象安插一个虚函数表指针，并为该类设置一张唯一的虚函数表，虚函数表中存放的是该类虚函数地址。运行期间通过虚函数表指针与虚函数表去确定该类虚函数的真正实现。

2. 请描述 new / delete 和 malloc / free 的区别。
   • 本质：new/delete 在C++中是运算符不是函数，需要编译器支持。malloc/free是库函数，需要头文件支持，在C语言中使用。
   • 开辟内存大小：用 new 操作符申请内存分配时无须指定内存块的大小，编译器会根据提供的类型信息自行计算。而malloc则需要先计算出所需内存的尺寸。
   • 返回类型：new 操作符内存分配成功时，返回的是提供的对象类型的指针，类型严格与对象匹配，无须进行类型转换，故new是符合类型安全性的操作符。
   • 分配失败：内存分配失败时，会抛出bac_alloc异常。malloc分配内存失败时返回NULL。
   • 自定义类型：new会先调用operator new函数，申请足够的内存（通常底层使用malloc实现）。然后调用类型的构造函数，初始化成员变量，最后返回自定义类型指针。delete先调用析构函数，然后调用operator delete函数释放内存（通常底层使用free实现）。
3. 请写出指针和引用的区别。
   • 引用在定义时必须初始化，指针没有要求
   • 引用只能初始化引用一个实体，而指针可以在任何时候指向任何一个同类型实体
   • 没有NULL引用，但有NULL指针
   • 在sizeof中含义不同：引用结果为引用类型的大小，指针始终是地址空间所占字节个数(32位:4字节? ?64位:8字节)
   • 引用自加即引用的实体增加1，指针自加即指针向后偏移一个类型的大小
   • 有多级指针，但是没有多级引用
   • 访问实体方式不同，指针需要显式解引用，引用编译器自己处理
   • 引用比指针使用起来简洁、安全

2. 基础算法题

1. 定义一个函数，输入一个单链表的头结点，然后反转该链表并输出反转后链表的头结点。
   这一题考的是链表的基本操作，简单的翻转。

ListNode* turnup(ListNode* head){
  //哑节点
  ListNode emp(0);
  emp.next = NULL;
  
  while(head != NULL){
      //记录当前节点
      ListNode* now = head;
      //头插法
      head = head->next;
      now->next = emp.next;
      emp.next = now;
  }

  //返回当前头结点    
  return emp.next;
}

1. 定义一个函数，输入一个随机数，判断是否是回文数（6,696, 686），不能使用字符串库。
   这题考的是字符串的遍历和回文数判断，挺简单的。
   思路：使用字符串存储每一个数位的数字，然后判断是否为回文数。

bool check(int input){
  //特殊情况
  if(input < 0)
      return false;
  if(input == 0)
      return true;
  //使用字符串存储数字，这里存下来是逆序的，不过不要紧，只是判断回文
  string str;
  while(input){
      str += input+'0';
      input /= 10;
  }
  //从两头开始向中间扫描，直至左右下标相遇
  int l=0;
  int r=str.length()-1;
  while(l<r){
      //如果某一次不一样，直接返回假
      if(str[l] != str[r])
          return false;
      ++l;
      --r;
  }
  return true;
}

1. String 的具体实现，已知String的定义如下，尝试写出类的成员函数实现。
   这道题是整个笔试最有意思的一道题了，同时也是我写得比较烂的一道题。考的是 String 类的底层实现，构造函数、析构函数，还有赋值运算符的编写。思路其实很清晰，就是使用 C 的字符串库，完成 C++ 中 String 类的实现，关键是有很多需要注意的小细节。

/* 题目部分 */
class String
{
public:
  String(const char *str = NULL); // 通用构造函数 
  String(const String &another); // 拷贝构造函数 
  ~ String(); // 析构函数 
  String & operater =(const String &rhs); // 赋值函数 
private:
  char *m_data; // 用于保存字符串 
};
/* 题目部分 */
//通用构造函数
String::String(const char *str = NULL){
  //不知道要不要对空指针进行特殊处理= =
  //查了一下好像是要的QAQ
  //字符串非空的时候需要申请相同大小的空间进行初始化
  if(str){
      int length = strlen(str);
      m_data = new char[length + 1];
      //使用strcpy函数进行字符串复制
      strcpy(m_data, str);
  }
  //字符串为空的时候申请大小为1字节的空间进行初始化
  else{
      m_data = new char[1];
      *m_data = '\0';
  }
}

//拷贝构造函数：这里我们需要进行深复制，即重新申请内存空间
String::String(const String &another){
  //计算原字符串长度len（包括结束符）
  int len = strlen(another.m_data);
  //动态分配内存
  m_data = new char[len + 1];
  //进行字符串拷贝，也可以使用strcpy函数进行拷贝
  strcpy(m_data, another.m_data);
}

//析构函数
String::~String(){
  //需要记得进行非空判断吗？不管了，严谨一点hhh。
  if(m_data)
      delete[] (m_data);
}

//拷贝运算符
String& String::operater=(const String &rhs){
  //记得判断相等，否则释放了自己的内存，就找不到需要拷贝的内容了。
  if(this == &rhs)
      return *this;

  //释放原内存空间
  delete[] (m_data);
  m_data = nullptr;

  //字符串拷贝
  int len = strlen(another.m_data);
  m_data = new char[len + 1];
  strcpy(m_data, rhs.m_data);

  //返回引用
  return *this;
}

1. 重力加速度为g（负整数），定义一个函数，输入当前高度h（正整数），需要上升的高度h_up（正整数），输出完成这个抛物线需要的时间（高度为0算完成）和上升初速速度。
   题目有点表述不明，我做的时候有点看不懂题目，所以直接跳过了没有完成。
   这道题是一到初中物理题的编程实现，我猜测大概是求解最小上升初速度和完成到达顶部时间的问题。

const int g = -9.8;
void calTime(double h, double h_up){
  double t = 0.0;
  double v = 0.0;
  //根据公式vt^2 - v0^2 = 2as
  //vt是最高点速度vt = 0, v0是需要求解的初速度, a是重力加速度, s是需要上升的高度
  //因此v = v0 = sqrt(-2*g*h_up)
  v0 = sqrt(-2*g*h_up);
  t = -v0/g;
  cout<<"v0="<<v0<<", t="<<t<<endl;
}

1. 定义一个函数，判断X年X月X日是X年的第几天。
   提示：判定公历闰年遵循的规律为:四年一闰,百年不闰,四百年再闰.
   公历闰年的简单计算方法:（符合以下条件之一的年份即为闰年）
   a 能被4整除而不能被100整除.（如2004年就是闰年,1900年不是）
   b 能被400整除.（如2000年是闰年）
   

int calDay(int year, int month, int day){
  //使用数组存储每个月的日期
  int months[13]{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  //通过判断是否是闰年，完成对二月的修改
  if(year%4==0 && year%100!=0){
      months[2] = 28;
  }
  if(year%400==0){
      months[2] = 28;
  }
  //计算已经过去的完整月份的天数和
  int ans = 0;
  for(int i=1; i<month; i++){
      ans += months[i];
  }
  //加上当前这个月已经过去的天数
ans += day;

  return ans;
}

1. 定义一个函数，随机输入一串二进制数字，输出十进制整数结果，例如101 = 5，110 = 6，11011= 27。

//假设二进制数字通过数组输入
int change(string input){
  int bit = 1;    //记录当前数位
  int ans = 0;    //记录答案
  //翻转字符串，从最低位开始遍历
  reverse(input.begin(), input.end());
  for(char c : input){
  //如果当前数位是1，则加上当前数位
  ans += c=='1' ? bit : 0;
  //当前数位进行左移
  bit = bit<<1;
  }
  return ans;
}    

1. 0,1,2,3…,n - 1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第 x 个数字。定义一个函数，输入 n (n>1) 和 m (x>1) ，求出这个圆圈里剩下的最后一个数字。

//方法一：使用vector存储数字，调用erase方法删除元素，对过程进行模拟
int LastRemaining_Solution(int n, int m)
{    
  //特殊情况判断
  if(n == 0)
      return -1;
  //构建vector记录数字
  vector<int> arr(n, 0);
  for(int i=0; i<n; i++){
      arr[i] = i;
  }
  
  int now = 0;    //当前位置
  int len = n;    //总数
  while(len > 1){
      //计算当前下标，对总数进行取余，求出第几个数字出局
      now = (now + m - 1) % len;
      //删除vector中的这个数字
      arr.erase(arr.begin() + now);
      //总数减一
      len--;
  }
  return arr[0];
}

//方法二：使用环形链表存储数字
int LastRemaining_Solution(int n, int m)
{
  if(n == 0)
      return -1;
  //构造环形链表，返回环形链表的尾部，因为删除节点需要使用尾部
  ListNode* nTail = createCircle(n);
  
  //记录当前数字个数len
  int len = n;
  while(len > 1){
      //因为第m个元素是0-m-1，并且环的长度是len，即以len为周期
      //所以当m-1=len时，应该取余数，利用周期减少搜索时间。
      int nm = (m-1)%len;
      //向前nm步，寻找指定元素
      for(int i=0; i<nm; i++){
          //尾部指针往前
          nTail = nTail->next;
      }
      //此时尾部指针nTail指向指定元素的前一个元素
      ListNode* found = nTail->next;
      //删除环形链表中指定元素，指定元素的前一个元素的next指向指定元素的next
      nTail->next = found->next;
      //释放指定元素的空间
      delete(found);
      //环形链表长度减少
      len--;
  }
  //返回剩下的第一个
  return nTail->next->val;
}
//构建长度为num的环形链表
ListNode* createCircle(int num){
  if(num == 0)
      return nullptr;
  ListNode emp(-1);
  ListNode* now = &emp;
  for(int i=0; i<num; i++){
      now->next = new ListNode(i);
      now = now->next;
  }
  //成环
  now->next = emp.next;
  //返回环的尾部
  return now;
}   

复盘：广州某游戏公司后端校招笔试

原文：https://www.cnblogs.com/azhao/p/12013512.html