网易笔试
题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
*/#网易笔试##网易##笔经#
