003 - 游戏客户端笔试002

因为没有一道题AC，被挂了。使用AI辅助复盘，结果不一定对。

算法题

最大有序同余对

定义同余对的概念：整数a和整数b除以非零整数n的余数相等，称a和b是 n的同余对，a与b的和为同余对的值，特别地，a<=b时称为有序同余对 给定一个整数列和一个整数 n，请在不使用模运算符%的前提下，输出值最大 的有序同余对。

输入描述：给定一行整数列，第二行为一个整数 n；

输出描述：值最大的有序同余对；

示例1：

// 输入:
5 11 8 7 2
3
// 输出:
8 11

AI生成代码：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

long long MyMod(long long a, long long n)
{
    if (n == 0) return 0; // 避免除零错误（题目已保证n非零）
    long long remainder = a - (a / n) * n;
    if (remainder < 0) remainder += abs(n); // 确保余数非负
    return remainder;
}

int main()
{
    string line;
    getline(cin, line);
    vector<long long> arr;

    string num;
    for (char ch: line)
    {
        if (isdigit(ch) || ch == '-')
        {
            num += ch;
        }
        else if (!num.empty())
        {
            arr.push_back(stoll(num));
            num.clear();
        }
    }
    if (!num.empty())
    {
        arr.push_back(stoll(num));
    }

    long long n;
    cin >> n;

    long long max_sum = -1;
    long long ansI = -1, ansJ = -1;

    for (long long i = 0; i < arr.size(); ++i)
    {
        for (long long j = i + 1; j < arr.size(); ++j)
        {
            if (MyMod(arr[i], n) == MyMod(arr[j], n))
            {
                long long current_sum = arr[i] + arr[j];
                if (current_sum > max_sum ||
                    (current_sum == max_sum && arr[i] <= arr[j] &&
                     (ansI == -1 || arr[i] < ansI || (arr[i] == ansI && arr[j] < ansJ))
                    )
                )
                {
                    max_sum = current_sum;
                    ansI = min(arr[i], arr[j]);
                    ansJ = max(arr[i], arr[j]);
                }
            }
        }
    }

    if (ansI != -1 && ansJ != -1)
    {
        cout << ansI << " " << ansJ;
    }
    return 0;
}

反思：MyMod逻辑混乱，烂完了，没什么好说的。

解析IPv4地址

IPv4 地址字符串为点(“.”)分隔的四段数字，每段数字取值范围 0~255，例如202.106.0.20，8.8.4.4。请编写函数将其转换为32比特无符号整数。其中字符串中最左边的一段在最高位侧，最右边的一段在最低位侧。例如上述两个IP地址转换完后分别为 0xCA6A0014 和 0x08080404。

输入数据：每行一个IPv4地址。

输出描述：解析后得到的整数的8位16进制表述，例如：

CA6A0014

08080404

注意不输出0x前缀，不够8位数用0补齐。对非法的输入，输出一个X。

示例1：

// 输入
202.106.0.20
6.7.8.999
8.8.4.4
    
// 输出
CA6A0014
X
08080404    

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <iomanip>
#include <cctype>

using namespace std;

bool isValidIPv4(const string& ipStr, vector<unsigned int>& ipNums) {
    stringstream ss(ipStr);
    string segment;
    int dotCount = 0;

    while (getline(ss, segment, '.')) {
        dotCount++;
        if (dotCount > 4) return false; // 超过4段

        // 检查是否为数字
        for (char ch : segment) {
            if (!isdigit(ch)) return false;
        }

        try {
            unsigned int num = stoul(segment);
            if (num > 255) return false; // 超出范围
            ipNums.push_back(num);
        } catch (...) {
            return false; // stoul转换失败（如空字符串）
        }
    }

    return (dotCount == 4 && ipNums.size() == 4); // 确保4段
}

int main() {
    string ipStr;
    while (getline(cin, ipStr)) {
        vector<unsigned int> ipNums;

        if (!isValidIPv4(ipStr, ipNums)) {
            cout << "X\n";
            continue;
        }

        // 合并为32位整数
        unsigned int ipInt = (ipNums[0] << 24) | (ipNums[1] << 16) |
                            (ipNums[2] << 8) | ipNums[3];

        // 输出8位十六进制，大写，补零
        cout << uppercase << setfill('0') << setw(8) << hex << ipInt << "\n";
    }
    return 0;
}

反思：忘记用异常捕获处理stoi，导致最后一个样例卡了。

求划任意条水平线后二叉树内独立闭合空间数量

给定一个无环的二叉树根节点，根节点所在行号为1，往下子节点所在行号递增。然后随机在若干行，划出无限长的水平线，要求输出划线后共分隔出多少个独立的闭合空间。(如图中长方形所在各个区域)

输入：输入共两行。第一行是二叉树的各个节点值，以空格分隔，表示一个数组模拟的二叉树。null 表示空节点。节点值的取值范围为任意整数。第二行是一个行号数组，以空格分隔。表示哪几行划线，行号的取值范围为任意整数。

输出：输出划线后共分隔出的独立的闭合空间数量。

示例1：

// 输入
1 2 3 4 5 6 7
1 2 3
// 输出
4

示例2：

// 输入
1 2 3 4 null null 7
1 3
// 输出
1

GPT：

下面给出一种基于“栅格化+洪泛（flood fill）”的思路实现。

大体思路如下：

1. 构造二叉树并确定节点位置 根据题目给定的数组（层序）构造二叉树。 为保证绘制时左右不“重叠”，采用中序遍历给每个节点分配一个递增的横坐标，纵坐标就是节点所在层数（根层为 1）。
2. 栅格化绘制（rasterize） 为方便后续几何处理，将整棵树（包括节点和边，即父子连线）绘制到一个二维字符网格上。 为了使斜线连续，我们引入一个“缩放因子”（例如 4），把每单位距离细分为多个网格点。 同时，还在输入给定的若干行位置上绘制无限长的水平线（在网格中横跨全宽）。
3. 区域分割 由于树的外轮廓与水平线构成若干封闭区域，我们采用洪泛算法先“标记”网格边界处能连通到外部的区域，剩下的连通块就是完全封闭的区域。
4. 输出区域数目 遍历整个网格，对每个未被标记且不属于边界（由树或水平线绘出）的空格区域进行一次 DFS 计数一个闭合区域。

下面给出完整 C++ 实现代码。

注意：此代码主要用来演示基本思路，假设输入的二叉树规模不大，对绘图分辨率和细节作了简单处理，实际比赛中可能需要根据数据范围做相应调整。

// 定义二叉树节点
struct TreeNode {
    int val;
    int level;      // 层号（根1开始）
    int x;          // 中序赋值得到的横坐标
    TreeNode* left;
    TreeNode* right;
    TreeNode(int v) : val(v), level(0), x(0), left(nullptr), right(nullptr) { }
};

// 根据数组表示（层序）构造二叉树（采用下标递归构造，遇 "null" 返回 nullptr）
TreeNode* buildTree(const vector<string>& tokens, int idx, int level) {
    if (idx >= tokens.size() || tokens[idx] == "null")
        return nullptr;
    TreeNode* node = new TreeNode(stoi(tokens[idx]));
    node->level = level;
    node->left = buildTree(tokens, 2*idx+1, level+1);
    node->right = buildTree(tokens, 2*idx+2, level+1);
    return node;
}

// 中序遍历为每个节点赋横坐标
void inOrderAssign(TreeNode* root, int& counter) {
    if (!root) return;
    inOrderAssign(root->left, counter);
    root->x = counter++;
    inOrderAssign(root->right, counter);
}

// Bresenham 算法绘制直线（从 (x1,y1) 到 (x2,y2)）在 canvas 上标记字符为 ch
void drawLine(vector<vector<char>>& canvas, int x1, int y1, int x2, int y2, char ch) {
    int dx = abs(x2-x1);
    int dy = abs(y2-y1);
    int sx = (x1 < x2) ? 1 : -1;
    int sy = (y1 < y2) ? 1 : -1;
    int err = dx - dy;
    while (true) {
        // 边界检查
        if (y1 >= 0 && y1 < canvas.size() && x1 >= 0 && x1 < canvas[0].size())
            canvas[y1][x1] = ch;
        if (x1 == x2 && y1 == y2)
            break;
        int e2 = err * 2;
        if (e2 > -dy) { err -= dy; x1 += sx; }
        if (e2 < dx)  { err += dx; y1 += sy; }
    }
}
  
// 洪泛算法，填充外部区域，用 marker 记录已访问的点，遇到边界字符（例如 '#'）则不能穿过
void floodFill(vector<vector<char>>& grid, vector<vector<bool>>& visited, int startY, int startX) {
    int n = grid.size(), m = grid[0].size();
    queue<pair<int,int>> q;
    q.push({startY, startX});
    visited[startY][startX] = true;
    int dirs[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
    while(!q.empty()){
        auto [cy, cx] = q.front(); q.pop();
        for(auto& d: dirs){
            int ny = cy + d[0], nx = cx + d[1];
            if(ny<0 || ny>= n || nx<0 || nx >= m) continue;
            if(visited[ny][nx]) continue;
            // 只有当格子不是边界（绘制处）才可流动
            if(grid[ny][nx] == ' ') {
                visited[ny][nx] = true;
                q.push({ny, nx});
            }
        }
    }
}

// DFS 用于计数内部闭合区域（即没有外部连通）
int dfsCount(vector<vector<char>>& grid, vector<vector<bool>>& visited, int y, int x) {
    int n = grid.size(), m = grid[0].size();
    int count = 1;
    visited[y][x] = true;
    int dirs[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
    for(auto& d: dirs) {
        int ny = y + d[0], nx = x + d[1];
        if(ny<0 || ny>= n || nx<0 || nx>= m) continue;
        if(!visited[ny][nx] && grid[ny][nx] == ' ')
            count += dfsCount(grid, visited, ny, nx);
    }
    return count;
}
  
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
  
    // 读入第一行：二叉树节点数组（用空格分隔）
    string treeLine;
    getline(cin, treeLine);
    istringstream issTree(treeLine);
    vector<string> nodes;
    string token;
    while(issTree >> token)
        nodes.push_back(token);
  
    // 读入第二行：水平线所在的行号
    string lineLine;
    getline(cin, lineLine);
    istringstream issLine(lineLine);
    vector<int> horLines;
    int num;
    while(issLine >> num)
        horLines.push_back(num);
    // 排序水平线便于后续绘制
    sort(horLines.begin(), horLines.end());
  
    // 构造二叉树
    TreeNode* root = buildTree(nodes, 0, 1);
    // 中序遍历赋横坐标
    int counter = 0;
    inOrderAssign(root, counter);
  
    // 获取树的高度和横坐标范围
    int maxLevel = 0;
    int maxX = 0;
    // 层序遍历获取最大值
    queue<TreeNode*> qu;
    if(root) qu.push(root);
    while(!qu.empty()){
        TreeNode* cur = qu.front(); qu.pop();
        maxLevel = max(maxLevel, cur->level);
        maxX = max(maxX, cur->x);
        if(cur->left) qu.push(cur->left);
        if(cur->right) qu.push(cur->right);
    }
  
    // 设置缩放因子和画布边界
    const int SCALE = 4;  
    const int MARGIN = 10;
    int width = (maxX + 1) * SCALE + 2 * MARGIN;
    int height = (maxLevel + 1) * SCALE + 2 * MARGIN;
  
    // 初始化画布
    vector<vector<char>> canvas(height, vector<char>(width, ' '));
  
    // 计算节点在画布中的坐标
    // 同时存储节点的画布坐标以便绘制边
    vector<pair<int,int>> nodePos; // (canvas_x, canvas_y)（不单独存树结构了，边直接从树中用递归遍历绘制）
    // 辅助：递归遍历树进行绘制边
    function<void(TreeNode*)> drawTree = [&](TreeNode* node) {
        if (!node) return;
        int cx = MARGIN + node->x * SCALE;
        int cy = MARGIN + node->level * SCALE;
        // 标记节点点（用数字字符的'*'表示）
        canvas[cy][cx] = '*';
        if(node->left){
            int nx = MARGIN + node->left->x * SCALE;
            int ny = MARGIN + node->left->level * SCALE;
            // 绘制连线
            drawLine(canvas, cx, cy, nx, ny, '#');
            drawTree(node->left);
        }
        if(node->right){
            int nx = MARGIN + node->right->x * SCALE;
            int ny = MARGIN + node->right->level * SCALE;
            drawLine(canvas, cx, cy, nx, ny, '#');
            drawTree(node->right);
        }
    };
    drawTree(root);
  
    // 在画布上绘制水平线（将对应行的所有像素设为边界字符）
    for (int L : horLines) {
        // 在树的坐标中，L 代表第 L 行，即画布中的 y = MARGIN + L * SCALE
        int y = MARGIN + L * SCALE;
        if(y < 0 || y >= height) continue;
        for (int x = 0; x < width; x++) {
            canvas[y][x] = '#';
        }
    }
  
    // （可选）调试输出画布
    // for(auto& row : canvas) {
    //     for(auto ch : row)
    //         cout << ch;
    //     cout << "\n";
    // }
  
    // flood fill 从画布边界（外部）进行标记，标记所有能流出（外部区域）的空格
    vector<vector<bool>> visited(height, vector<bool>(width, false));
    // 四条边作为起点
    for (int x = 0; x < width; x++) {
        if(!visited[0][x] && canvas[0][x]==' ')
            floodFill(canvas, visited, 0, x);
        if(!visited[height-1][x] && canvas[height-1][x]==' ')
            floodFill(canvas, visited, height-1, x);
    }
    for (int y = 0; y < height; y++) {
        if(!visited[y][0] && canvas[y][0]==' ')
            floodFill(canvas, visited, y, 0);
        if(!visited[y][width-1] && canvas[y][width-1]==' ')
            floodFill(canvas, visited, y, width-1);
    }
  
    // 遍历整个画布，遇到没有被 flood fill 过的空白区域即为一个闭合区域
    int regions = 0;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if(canvas[i][j]==' ' && !visited[i][j]) {
                // DFS 填充该闭合区域
                dfsCount(canvas, visited, i, j);
                regions++;
            }
        }
    }
  
    cout << regions << "\n";
  
    // 注意：本程序未释放动态分配的二叉树内存（测试时可忽略）  
    return 0;
}

反思：完全没头绪，看了题解也不会，等哪天学了Flood Fill算法再回来看看吧。

编写归并排序迭代器

已实现代码如下：

struct Iterator
{
    virtual bool hasNext() = 0;
    virtual int next() = 0;
};

class MergeIterator : public Iterator
{
public:
    MergeIterator() {
        // TODO
    }
    
    bool hasNext() {
        // TODO
    }
    
    int next() {
        // todo
    }
};

class MockIterator : public Iterator
{
    int m_current, m_step, m_endvalue;
public:    
    MockIterator(int step, int endValue)
    {
        m_step = step;
        m_endValue = endvalue;
        m_current = endValue % step;
    }
    
    bool hasNext() { return m_current < m_endValue; }
    int next() { return m_current += m_step; }
};

待实现的效果如下：

Mocklterator ita(参数1,参数2),itb(参数1,参数2);//输入2 10 2 9
Mergelteratorit(&ita, &itb);//输出2 3 4 5 6 7 8 9 10

请使用C++作答，将所需代码复制到代码框中。并补全Mergelterator 类中的函数，达到预想的实现效果。

请获取输入的参数并根据参数新建迭代器，并将选代器的排序结果输出(元素之间以空格分开，最后一个元素后无空格)。

class MergeIterator : public Iterator
{
private:
    MockIterator* m_pIta = nullptr, *m_pItb = nullptr;
    vector<int> m_arr;
    set<int> m_nums;
    int m_idx = 0;

    void PushBack(int val)
    {
        if (!m_nums.contains(val))
        {
            m_arr.push_back(val);
            m_nums.insert(val);
        }
    }

public:
    MergeIterator(MockIterator* _pIta, MockIterator* _pItb)
        : m_pIta(_pIta), m_pItb(_pItb)
    {
        int curA = -114514, curB = -114514;
        while (m_pIta->hasNext() && m_pItb->hasNext())
        {
            if (curA == -114514) curA = m_pIta->next();
            if (curB == -114514) curB = m_pItb->next();

            if (m_arr.empty())
            {
                if (curA <= curB)
                {
                    PushBack(curA);
                    curA = -114514;
                }
                else
                {
                    PushBack(curB);
                    curB = -114514;
                }
            }
            else
            {
                if (m_arr.back() < curA && curA <= curB)
                {
                    PushBack(curA);
                    curA = -114514;
                }
                else
                {
                    PushBack(curB);
                    curB = -114514;
                }
            }
        }

        while (m_pIta->hasNext())
        {
            if (curB != -114514)
            {
                curA = m_pIta->next();
                int before = min(curA, curB);
                int after = max(curA, curB);
                PushBack(before);
                PushBack(after);

                curA = -114514;
                curB = -114514;
            }

            if (m_pIta->hasNext())
            {
                PushBack(m_pIta->next());
            }
        }
        while (m_pItb->hasNext())
        {
            if (curA != -114514)
            {
                curB = m_pItb->next();
                int before = min(curA, curB);
                int after = max(curA, curB);
                PushBack(before);
                PushBack(after);

                curA = -114514;
                curB = -114514;
            }

            if (m_pItb->hasNext())
            {
                PushBack(m_pItb->next());
            }
        }
    }

    bool hasNext() {
        return m_idx < m_arr.size();
    }

    int next() {
        return m_arr[m_idx++];
    }
};

int main()
{
    int aStep, aEndval, bStep, bEndval;
    cin >> aStep >> aEndval >> bStep >> bEndval;

    MockIterator ita(aStep, aEndval);
    MockIterator itb(bStep, bEndval);
    MergeIterator ans(&ita, &itb);

    while (ans.hasNext())
    {
        cout << ans.next();
        if (ans.hasNext())
        {
            cout << " ";
        }
    }

    return 0;
}

反思：代码有漏洞，例如：允许存在重复元素，这是错的；元素排序可能出现错误，在其中一个MockIterator耗尽时。