网易笔试

题1

n 个顶点的无向图判断能否从 start 连通到 end

const int INF = 0x3f3f3f3f;
class Solution {
public:
    vector<vector<int>> edges;
    vector<int> dist;

    void bfs(int s) {
        dist[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : edges[u]) {
                if (dist[v] == INF) {
                    dist[v] = dist[u] + 1;
                    q.push(v);
                }
            }
        }
    }

    bool validPath(int n, vector<vector<int> >& sides, int start, int end) {
        edges = vector<vector<int>>(n);
        dist = vector<int>(n, INF);
        for (auto &e : sides) {
            edges[e[0]].push_back(e[1]);
            edges[e[1]].push_back(e[0]);
        }
        bfs(start);
        return dist[end] != INF;
    }
};
/*
4,[[0,1],[1,2],[2,3],[3,0]],0,2
true
*/

题2

三个数能否只用加减乘除凑24，可以交换数字位置

class Solution {
    constexpr static double eps = 1e-5;
public:
    bool dfs(vector<int>& nums, double res) { // init : dfs(nums, nums[0/1/2]
        for (int &i : nums) {
            if (i == -1)
                continue;
            int pre = i;
            i = -1;
            if (dfs(nums, res + pre) || dfs(nums, res - pre) || dfs(nums, res * pre) || dfs(nums, res / pre))
                return true;
            i = pre;
        }
        if (count(begin(nums), end(nums), -1) == 3 && abs(res - 24.0) < eps)
            return true;
        return false;
    }

    bool compute24(vector<int>& inputNumbers) {
        for (int i = 0; i < 3; i++) {
            int pre = inputNumbers[i];
            inputNumbers[i] = -1;
            if (dfs(inputNumbers, pre))
                return true;
            inputNumbers[i] = pre;
        }
        return false;
    }
};
/*
2 4 12
true
1 1 1
false
*/

题3

M*N的迷宫有一些位置有宝藏，两个人走迷宫最大能获得的宝藏数.
这题有点小坑，不能贪心两次dp做，所以我暴力枚举第一个人走的路径然后 dp 求第二个人能拿的最大宝藏，不知道有没有更好的做法。。下面代码给了个不能贪心的用例。。
麻了贪心找了一个小时bug。

#include <bits/stdc++.h>
#define IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
int M, N, K;
vvi mp;
int ans = 0;

int getMoney() {
    vvi dp = mp;
    for (int i = 1; i <= M; i++) {
        for (int j = 1; j <= N; j++) {
            if (j == 1 or dp[i - 1][j] > dp[i][j - 1]) {
                dp[i][j] += dp[i - 1][j];
            }
            else {
                dp[i][j] += dp[i][j - 1];
            }
        }
    }
    return dp[M][N];
}

void dfs(int x, int y, int sum) {
    sum += mp[x][y];
    int tmp = mp[x][y];
    mp[x][y] = 0;
    if (x + 1 <= M) {
        dfs(x + 1, y, sum);
    }
    if (y + 1 <= N) {
        dfs(x, y + 1, sum);
    }
    if (x == M and y == N) {
        int c = getMoney();
        if (sum + c > ans)
            ans = sum + c;
    }
    mp[x][y] = tmp;
}

int32_t main() {
    IO;
    cin >> M >> N >> K;
    mp = vector<vector<int>> (M + 1, vector<int>(N + 1, 0));
    while (K--) {
        int x, y, z;
        cin >> x >> y >> z;
        mp[x][y] += z;
    }
    dfs(1, 1, 0);
    cout << ans << "\n";
    return 0;
}
/*
6 5 9
1 4 1000
2 1 1000
2 2 1
2 3 1000
2 4 1
2 5 1000
3 3 1000
3 5 1
4 5 1
ans=5004（不能贪心）

3 5 10
1 2 1
1 3 5
1 5 10
2 1 8
2 2 10
2 3 4
2 4 3
3 1 10
3 3 2
3 4 8
ans=49
*/

题4

第一行：N层楼，从A出发到B的最小按开关次数
第二行：N个数，k[i] 表示第 i 层的时候按开关电梯可以上行或者下行 k[i] 层，如果目标楼层 i+k[i] 或者 i-k[i] 不在 1~N 之间，按开关无效

#include <bits/stdc++.h>
#define IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;

int32_t main() {
    IO;
    int n, a, b;
    cin >> n >> a >> b;
    --a;
    --b;
    vector<int> k(n);
    vector<int> vis(n, -1);
    for (int i = 0; i < n; i++) {
        cin >> k[i];
    }
    queue<int> q;
    q.push(a);
    vis[a] = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        int nx1 = cur - k[cur];
        int nx2 = cur + k[cur];
        if (0 <= nx1 and nx1 < n and vis[nx1] == -1) {
            q.push(nx1);
            vis[nx1] = vis[cur] + 1;
        }
        if (0 <= nx2 and nx2 < n and vis[nx2] == -1) {
            q.push(nx2);
            vis[nx2] = vis[cur] + 1;
        }
    }
    cout << vis[b] << "\n";
    return 0;
}

/*
5 1 5
3 3 1 2 5
ans=3
*/

#网易笔试##网易##笔经#