西山居笔试4月14日

岗位

游戏客户端开发

试卷类型

西山居2024春招技术开发D卷

题目分配

4 道单选，6 道不定项，2 道填空，2 道编程，1 道问答

作答时间

120 分钟

做题感受

• 题目类型较为丰富，难度中等偏低，主要考察数据结果，其他部分较少

• 编程题整体较为简单

• 第一题并查集

  给你一个 $n*n$ 的邻接矩阵，描述的是有 $n$ 个节点的无向图，求该无向图里有多少个联通图。

  class Node
  {
  public:
      int id;
      Node* next;
      Node(int id) :id(id)
      {
          next = this;
      }
  
      Node* head()
      {
          Node* temp = next;
          while (temp->next != temp)
          {
              temp = temp->next;
          }
          return temp;
      }
  
      void join(Node* node)
      {
          if (node == this)
              return;
          head()->next = node->head();
      }
  };
  class Solution {
  public:
      /**
       * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
       *
       * 统计岛群数量
       * @param connectedArray int整型vector<vector<>> 小岛连接关系
       * @return int整型
       */
      int getIsLandGroupCount(vector<vector<int> >& connectedArray) {
          int n = connectedArray.size();
          if (n <= 1)
              return n;
          vector<Node*> vec(n);
          for (int i = 0;i < n;++i)
          {
              vec[i] = new Node(i);
          }
          for (int i = 0;i < n;++i)
          {
              for (int j = i + 1;j < n;++j)
              {
                  if (connectedArray[i][j] == 1)
                  {
                      vec[j]->join(vec[i]);
                  }
              }
          }
          unordered_set<int> set;
          for (auto& node : vec)
          {
              set.insert(node->head()->id);
          }
          return set.size();
      }
  };

• 第二题 DFS

  给你一个目标字符串和一个字符串数组，你需要用该数组内的元素拼成该目标字符串（元素可以重复使用）返回一个数组数组表示拼接顺序。

  #include <string>
  #include <vector>
  using namespace std;
  class Solution {
  public:
      /**
       * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
       *
       * 返回使用 elements 内容拼接成 destStr 的组合方案
       * @param destStr string字符串 需要拼接目标字符串
       * @param elements string字符串vector 用于拼接的元素列表，允许重复使用同一元素
       * @return int整型vector
       */
      vector<int> StringAssemble(string destStr, vector<string>& elements) {
          // write code here
          return dfs(destStr, 0, elements);
      }
  
      vector<int> dfs(const string& destStr, int curIndex, vector<string>& elements)
      {
          if (curIndex == destStr.size())
              return {};
          vector<int> ans;
          int index = 0;
          for (const string& s : elements)
          {
              int size = s.size();
              if (curIndex + size <= destStr.size())
                  if (destStr.substr(curIndex, size) == s)
                  {
                      vector<int> ret = dfs(destStr, curIndex + size, elements);
                      if (ret.size()==0 ||ret[ret.size() - 1] != -1)
                      {
                          ans.push_back(index);
                          for (auto& i : ret)
                              ans.push_back(i);
                          return ans;
                      }
                  }
              index++;
          }
          return { -1 };
      }
  };
  int main()
  {
  	Solution s;
  	vector<string> elements = { "4395", "e9", "e903", "cebd" };
  	vector<int> ans = s.StringAssemble("e9cebd4395", elements);
  	return 0;
  }

• 问答题比较有意思，是给了一个种田游戏的玩法，然后让你从程序的角度去看写一些系统、类、函数，以及如果地块很大的优化思路。