sitJac's Blog
0%

华为2022校园招聘软件专业类4.08-机试题三道

Posted on In
  • 第一题考察模拟：涉及到对实际问题或过程的计算机算法模拟。
  • 第二题是DFS在二维网格上的应用：岛屿的最大面积、连通区域的最大面积等经典题目的变体，主要考察对DFS算法和二维网格操作的理解。
  • 第三题是一维动态规划：DP中经典问题跳跃游戏的一个变种，考察DP的基本知识点。

第一题（100）

给出多个房间编号，两个房间之间存在单向门，根据单向门输出只能进不能出的房间编号，有且仅有一个只能进不能出的房间。

输入描述：

1.第一行是单向门的数量N。
2.第二行开始的N行，是使用空格分隔的两个房间号，代表一个单向门。

说明：
1 <= 单向门数量 <= 100
房间号为int类型数字

输出描述：

房间的编号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#输出只进不出的唯一的一个门🚪

'''
Input:
5
1 2
2 3
3 4
2 5
5 4

Output:
4
'''

n = int(input())
from_list = []
to_list = []
for i in range(n):
    a, b = map(int, input().split())
    from_list.append(a)
    to_list.append(b)
for i in to_list:
    if i not in from_list:
        print(i)
        break

第二题（200）

给定一个二维数组，每个元素代表地形的高度。山体是由连续的、高度大于0的格子组成的，每个山体的体积是其包含的所有格子的高度之和。请找出体积最大的山体。

输入描述：

第一行包含两个整数n和m，表示二维数组的行数和列数（1 <= n, m <= 1000）。 接下来的n行，每行包含m个整数，表示地形的高度（0 <= 高度 <= 1000）。

输出描述：

输出一个整数，表示体积最大的山体的体积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 岛屿的最大山体体积 dfs

/*
Input:
5 5
0 1 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 1 2 3
0 0 1 3 9

Output:
19
*/

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

int n, m;
int grid[1005][1005];
bool visited[1005][1005];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int dfs(int x, int y) {
    visited[x][y] = true;
    int volume = grid[x][y];
    for(int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] > 0 && !visited[nx][ny]) {
            volume += dfs(nx, ny);
        }
    }
    return volume;
}

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    int maxVolume = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(grid[i][j] > 0 && !visited[i][j]) {
                maxVolume = max(maxVolume, dfs(i, j));
            }
        }
    }
    cout << maxVolume << endl;
    return 0;
}

第三道（300）

原题：大致是在讲给出一些网络传输设备，每台设备都有其能传输数据的最大传输距离，问从第一台设备传输数据到最后一台数据所用到的最少中转次数为多少。

翻译：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

输入描述：

第入参通过多行字符串方式表示，例如：
4
2 3 1 1
字符串含义：
1.第一行表示总共中转设备台数：总计4台
2.第二行表述中转设备的最大传输能力：第一台设备最大传输距离为2km，第二胎设备最大传输距离为3km，第三台设备最大传输距离为1km，第四台设备最大传输距离为1km。

输出描述：

2
解释：
数据从第一台设备中转到第三台设备，再从第三台设备中转到第四台设备，传输结束，中共需中转2次。

解题思路：

这个题目主要考察的是动态规划的知识点。
在这个问题中，我们使用一个动态规划数组dp，其中dp[i]表示从位置i跳跃到数组的最后一个位置的最少跳跃次数。
我们从数组的倒数第二个位置开始，向前遍历，对于每个位置，如果它可以一步跳到最后一个位置，那么dp[i]就是1，否则，dp[i]就是它可以跳到的所有位置的dp值加1的最小值。
最后，dp[0]就是我们要求的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// LeetCode 45.跳跃游戏（Jump Game Ⅱ）的一个变种题目

/*
Input:
4
2 3 1 1

Output:
2
*/

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

const int MAXN = 1000;
int n;
int a[MAXN];
int dp[MAXN];   //dp[i]表示以i为开始到达最后一个节点的最小步数

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    //初始化
    dp[n-1] = 0;
    //遍历顺序
    for(int i = n - 2; i >= 0; i--){
        //递推公式
        if(n-1-i <= a[i]){  //当前位置一步就可以到达最后一个节点
            dp[i] = 1;
        }
        else{   //当前位置无法一步到达最后一个节点 此时需要遍历求得最小的步数
            int min_temp = 10000;
            for(int j = 1; j <= a[i]; j++){
                int temp = dp[i + j] + 1;
                min_temp = min(min_temp, temp);
            }
            dp[i] = min_temp;
        }
    }
    //打印输出目标dp
    cout << dp[0];
    return 0;
}