筆試時間：2025年04月02日

歷史筆試傳送門：

2023春招秋招筆試合集

2024春招秋招筆試合集

第一題

題目：分割等和數(shù)組

給定一個只包含正整數(shù)的非空數(shù)組 nums，判斷該數(shù)組是否可以被分割成兩個子集，使得兩個子集的元素和相等。

樣例輸入

[1,5,11,5]

樣例輸出

true

參考題解

*******************************************************************************

第二題

題目：二叉樹遍歷

給你一個全部節(jié)點(diǎn)是正整數(shù)的二叉樹，逐層的從左到右訪問所有節(jié)點(diǎn)，輸出為一個二維數(shù)組；注：# 代表該節(jié)點(diǎn)沒有值

樣例輸入

{5,20,11,#,7}

樣例輸出

[[5],[20,11],[7]]

參考題解

二叉樹的層序遍歷，直接bfs即可。

第三題

題目：艾爾羅大迷宮

設(shè)計一個迷宮游戲系列艾爾羅,在設(shè)計初期為了方便,使用n*n矩陣表示.0代表可到達(dá)區(qū)域,1表示不可到達(dá)區(qū)域.例如有:[[0, 1, 0, 0][0, 0, 0, 0][0, 1, 0, 1][0, 0, 1, 0]]在這個例子中,因?yàn)閙ap[3] [2] = 1和map[2] [3] =1.所以相對于起點(diǎn)map[0] [0]來說,map[3] [3]的位置是不可達(dá)的(只允許左右上下移動).為了方便評估設(shè)計的艾爾羅迷宮的難易程度,需要有一個方便的算法統(tǒng)計每個迷宮不可到達(dá)的網(wǎng)格有多少個.比如上面的不可達(dá)區(qū)域?yàn)?個原生不達(dá)的區(qū)域加上1個衍生的map[3] [3].總數(shù)為5.約束:起點(diǎn)統(tǒng)一定義為[0,0].給定的迷宮二維數(shù)組矩陣形式是n*n,且[0,0]也總是可達(dá)(值為0),原生不可達(dá)的用值1表示。

樣例輸入

[[0,1,1,0],[1,0,0,0],[0,1,0,1],[0,1,1,0]]

樣例輸出

15

說明：[0,0]被困,所以都不可達(dá)。

參考題解

統(tǒng)計原生障礙數(shù)量：遍歷二維矩陣，統(tǒng)計所有值為1的元素數(shù)量。廣度優(yōu)先搜索（BFS）標(biāo)記可達(dá)區(qū)域：從起點(diǎn)[0,0]出發(fā)，使用BFS遍歷所有可達(dá)的0區(qū)域，并標(biāo)記已訪問的位置。計算不可達(dá)的0區(qū)域：遍歷整個矩陣，統(tǒng)計所有未被訪問且值為0的元素數(shù)量。總不可達(dá)數(shù)：原生障礙數(shù) + 不可達(dá)的0區(qū)域數(shù)。

C++：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int apply(vector<vector<int>>& generated_map) {
        int n = generated_map.size();
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        queue<pair<int, int>> q;
        q.push({0, 0});
        visited[0][0] = true;

        // 定義四個方向
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (auto [dx, dy] : directions) {
                int nx = x + dx;
                int ny = y + dy;
                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (!visited[nx][ny] && generated_map[nx][ny] == 0) {
                        visited[nx][ny] = true;
                        q.push({nx, ny});
                    }
                }
            }
        }

        // 統(tǒng)計障礙物數(shù)量
        int count_ones = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (generated_ma