T1

题目描述

vivo游戏中心的运营小伙伴最近接到一款新游戏的上架申请，为了保障用户体验，运营同学将按运营流程和规范对其做出分析评估。经过初步了解后分析得知，该游戏的地图可以用一个大小为$n*n$的矩阵表示，每个元素可以视为一个格子，根据游戏剧情设定其中某些格子是不可达的（比如建筑、高山、河流或者其它障碍物等），现在请你设计一种算法寻找从起点出发到达终点的最优抵达路径，以协助运营小伙伴评估该游戏的可玩性和上手难度。

输入描述

第一行表示矩阵大小$n$，$5 < n < 10000$
第二行表示起点和终点的坐标
第三行起是一个用矩阵表示的游戏地图，其中#或者@表示障碍物，其它字母、非0数字、以及符号+、-、*等等均表示普通可达格子，共有$n$行$n$列

输出描述

输出最优路径的长度；若无法到达，则输出-1

示例1

样例输入

15
0 7 7 7
*5#++B+B+++++$3
55#+++++++###$$
###$++++++#+*#+
++$@$+++$$$3+#+
+++$$+++$+4###+
A++++###$@+$++A
+++++#++$#$$+++
A++++#+5+#+++++
+++$$#$++#++++A
+++$+@$###+++++
+###4+$+++$$+++
+#+3$$$+++$##++
+#*+#++++++#$$+
$####+++++++$##
3$+++B++B++++#5

样例输出

13

算法

(bfs) $O(n ^ 2)$

只过了70%，样例的答案应该是9而不是13

C++ 代码

#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second

const int N = 1e4 + 10;
typedef pair<int, int> PII;

int n;
char g[N][N];
unordered_map<int, int> dist;
PII s, e;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

int get(int x, int y) {
    return x * n + y;
}

int bfs() {
    dist[get(s.x, s.y)] = 0;

    queue<PII> q;
    q.push(s);

    while (q.size()) {
        auto t = q.front(); q.pop();

        int dis = dist[get(t.x, t.y)];
        if (t.x == e.x && t.y == e.y) return dis;

        for (int i = 0; i < 4; i ++ ) {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || b < 0 || a >= n || b >= n) continue;
            if (g[a][b] == '#' || g[a][b] == '@') continue;
            if (dist.count(get(a, b))) continue;
            dist[get(a, b)] = dis + 1;
            q.push({a, b});
        }
    }

    return -1;
}

int main() {
    cin >> n;
    cin >> s.x >> s.y >> e.x >> e.y;
    for (int i = 0; i < n; i ++ ) cin >> g[i];

    cout << bfs();

    return 0;
}

T2

题目描述

回文字符串就是把正读和反读都一样的字符串，如“viv”、“nexen”、“12321”、“qqq”、“翻身把身翻”等。给定一个非空字符串str，在最多可以删除一个字符的情况下请编程判定其能否成为回文字符串；如果可以则输出首次删除一个字符所能得到的回文字符串，如果不行则输出字符串“false”

输入描述

一个非空字符串

输出描述

一个回文字符串，或者“false”字符串（如果无法构造出回文字符串的话）

示例1

样例输入

abda

样例输出

ada

说明

删除字符串“abda”中的一个字符’b’后，得到“ada”是一个回文字符串；删除一个字符’d’后，得到“aba”也是一个回文字符串；所以最终输出为“ada”
备注： 1、输入仅包含数字或字母；2、当分别删除不同的字符后，均可得到回文字符串时，输出首次删除一个字符所得到的回文字符串；若无法构造出回文字符串，则输出字符串false

算法

(暴力枚举) $O(n ^ 2)$

100%

C++ 代码

#include <bits/stdc++.h>
using namespace std;

string s;

bool check(string s) {
    int l = 0, r = s.size() - 1;
    while (l <= r) {
        if (s[l] != s[r]) return false;
        l ++ , r -- ;
    }
    return true;
}

int main() {
    cin >> s;

    bool is_find = false;

    for (int i = 0; i < s.size(); i ++ ) {
        string t = s; t.erase(i, 1);
        if (check(t)) {
            cout << t;
            is_find = true;
            break;
        }
    }

    if (!is_find) puts("false");

    return 0;
}

T3

题目描述

一个完整的软件项目往往包含很多由代码和文档组成的源文件。编译器在编译整个项目的时候，可能需要按照依赖关系来依次编译每个源文件。比如，A.cpp依赖B.cpp，那么在编译的时候，编译器需要先编译B.cpp，才能再编译A.cpp。假设现有0，1，2，3四个文件，0号文件依赖1号文件，1号文件依赖2号文件，3号文件依赖1号文件，则源文件的编译顺序为2,1,0,3或2,1,3,0。现给出文件依赖关系，如1,2,-1,1，表示0号文件依赖1号文件，1号文件依赖2号文件，2号文件没有依赖，3号文件依赖1号文件。请补充完整程序，返回正确的编译顺序。注意如有同时可以编译多个文件的情况，按数字升序返回一种情况即可，比如前述案例输出为：2,1,0,3

示例1

样例输入

“1,2,-1,1”

样例输出

“2,1,0,3”

说明

-1表示当前文件没有依赖，输出结果英文逗号分隔。暂不考虑一个文件依赖多个文件的情况。

算法

(拓扑排序) $O(n)$

80%

C++ 代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 编译顺序
     * @param input string字符串 
     * @return string字符串
     */
    vector<int> a, d;
    vector<vector<int>> g;
    string ret;

    string compileSeq(string input) {
        // write code here
        stringstream ss(input);
        string s;
        while (getline(ss, s, ',')) a.push_back(stoi(s));

        int n = a.size();
        g.resize(n), d.resize(n);
        for (int i = 0; i < n; i ++ ) {
            if (a[i] == -1) continue;
            d[i] ++ , g[a[i]].push_back(i);
        }

        queue<int> q;
        for (int i = 0; i < n; i ++ ) if (!d[i]) q.push(i);

        while (q.size()) {
            int t = q.front(); q.pop();
            ret += to_string(t) + ',';
            for (auto j: g[t]) {
                if ( -- d[j] == 0)
                    q.push(j);
            }
        }
        ret.pop_back();
        return ret;
    }
};