2021复旦机试回顾

2021年复旦大学计算机专业预推免机试题,一共3道题,都比较常规,主要考察动态规划。

第一题

将 n 个正整数存放于一个一维数组中,编写一个程序,将数组中所有的奇数存放于所有的偶数之前,要求尽可能少用临时存储单元并使时间复杂度达到 O(n)。输入:一维数组;输出:符合要求的一维数组。

解题思路

使用类似快排的思想,定义前后2个指针,前指针向后移动直到指向一个偶数;后指针向前移动直到指向一个奇数,然后交换这2个数的位置。然后继续移动2个指针直到相遇。由于2个指针一共只需遍历一遍数组,所以时间复杂度是O(n),同时数字是原地交换的没有使用额外空间。

代码实现

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
/**
* 将 n 个正整数存放于一个一维数组中,编写一个程序,将数组中所有的奇数存放于所有的偶数之前,
* 要求尽可能少用临时存储单元并使时间复杂度达到 O(n)。
* 输入:一维数组;输出:符合要求的一维数组。
**/
#include <bits/stdc++.h>
using namespace std;

bool is_odd(int x)
{
return x % 2 == 1;
}

int main()
{
int a;
vector<int> nums;
while (cin >> a)
{
nums.push_back(a);
}

int n = nums.size();

int l = 0;
int r = n - 1;

while (l < r)
{
while (l < r && is_odd(nums[l])) // 从左到右遍历,直到一个偶数
{
l++;
}
while (l < r && !is_odd(nums[r])) // 从右到左遍历,直到一个奇数
{
r--;
}
if (l < r){
swap(nums[l++], nums[r++]); // 原地交换两数
}

}

for(auto& i:nums){
cout<<i<<" ";
}
}

测试用例

  1. 1
    2
    3
    4
    # in
    1 2 3 4 5 6 7
    # out
    1 7 3 5 4 6 2
  2. 1
    2
    3
    4
    # in
    2 4 6
    # out
    2 4 6
  3. 1
    2
    3
    4
    # in
    4 6 8 1 5
    # out
    5 1 8 6 4
  4. 1
    2
    3
    4
    # in
    <空>
    # out
    <空>

第二题

给定 n 个小区之间的交通图, 并用二维数组 A[n][n]表示,即若小区 i 与小区 j 之间有路,则 A[i][j]表示这条路的长度。现计划在这 n 个小区中选定一个小区建一所医院,使距离医院最远的小区到医院的路程尽可能缩短。编写一个程序解决上述问题。
输入:二维数组;输出:建医院的小区。

解题思路

本题要先以每个点为起点,找到到达其他点的最短路径,算出到达最远点的距离。然后选出最远点距离最短的那个点。所以本题是一个多源最短路径问题,我采用了Floyd 算法,用的是动态规划的思想,如果顶点i和j之间存在一条经过k点的路径,能得到一条更短的路径,则可以将 k 作为其最短路径的中间点,更新最短路径长度。

代码实现

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
55
56
57
58
59
60
61
62
63
64
65
66
/**
* 给定 n 个小区之间的交通图, 并用二维数组 A[n][n]表示,即若小区 i 与小区 j 之间有路,
* 则 A[i][j]表示这条路的长度。现计划在这 n 个小区中选定一个小区建一所医院,使距离医院
* 最远的小区到医院的路程尽可能缩短。编写一个程序解决上述问题。
* 输入:二维数组;输出:建医院的小区。
**/
#include <bits/stdc++.h>
using namespace std;


int main()
{
int n; // n 个城市
cin >> n;
// 每2个城市间的最短路径。初始:直达路长度 或 无穷远
vector<vector<int>> dist(n, vector<int>(n, INT_MAX));

// 输入
int tmp;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> tmp;
if (i == j) // 到自身的距离为0
{
dist[i][j] = 0;
continue;
}

if (tmp > 0)
dist[i][j] = tmp;
}
}

// 用 Floyd 算法,求每2个点之间的最短路
for (int k = 0; k < n; k++) // 中间点k
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
// 需要保证k到两点均存在通路
if (dist[i][k] < INT_MAX && dist[k][j] < INT_MAX && (dist[i][k] + dist[k][j] < dist[i][j]))
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}


int min_dis = INT_MAX; // 路径的最小值
int city=0; // 所选城市编号
for(int i=0;i<n;i++){ // 假设以每个城市作为中心点,计算其他城市到 i 点最远的距离
int max_dis_to_i=0; // 到 i 点最远的距离
for(int j=0;j<n;j++){
if(i==j)continue;
max_dis_to_i=max(max_dis_to_i,dist[i][j]);
}
if(max_dis_to_i<min_dis){
min_dis=max_dis_to_i;
city=i;
}
}

cout<<city;
}

测试用例

  1. 1
    2
    3
    4
    5
    6
    7
    # in
    3
    0 1 2
    1 0 3
    2 3 0
    # out
    0

    image-20210923110756745

  2. 1
    2
    3
    4
    5
    6
    7
    # in (0,1间没路)
    3
    0 0 2
    0 0 3
    2 3 0
    # out
    2

    image-20210923110815131

  3. 1
    2
    3
    4
    5
    6
    7
    8
    # in
    4
    0 7 2 5
    7 0 0 2
    2 0 0 1
    5 2 1 0
    # out
    2

    image-20210923110909811

第三题

给定一个长为 n 的序列, 其中序列中的元素都是 0~9 之间的整数。 现在要从序列的第一个位置走到最后一个位置,每次要么往后走一步,要么走到下一个与当前位置元素相同的位置, 编写一个程序求所需要的最少步数, 要求时间复杂度 O(n)。
输入: 整数序列;输出: 最少步数。

解题思路

本题我采用了动态规划的思路,假设$dp[i]$表示从位置0走到位置i的最少步数,$last[i]$表示i位置的数上一次出现的位置,由于每一步有2种选择,那么可以写出递推式$dp[i]=\min(dp[i-1]+1,dp[last[i]]+1)$。最终答案即为$dp[n-1]$.

所以问题就转化为求解$last[]$数组,由于本题规定只有0~9之间的数字,所以不妨定义一个长度为10的滚动数组$digit_last[]$记录每个数字上次出现的位置,这样只需遍历一遍原始数组,就能构造出$last[]$.

总体而言,构造$last[]$数组时间复杂度为O(n),求解dp的复杂度同样是O(n),所以总体复杂度为O(n).

代码实现

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
/**
* 给定一个长为 n 的序列, 其中序列中的元素都是 0~9 之间的整数。 现在要从序列的第一个位置走到最后一个位置,每次要么往后走一步,要么走到下一个与当前位置元素相同的位置, 编写一个程序求所需要的最少步数, 要求时间复杂度 O(n)。
* 输入: 整数序列;输出: 最少步数。
**/
#include <bits/stdc++.h>
using namespace std;

int main()
{
int a;
vector<int> nums;
while (cin >> a)
{
nums.push_back(a);
}

int n = nums.size();
if (n == 0)
{
cout << 0;
return 0;
}
vector<int> digit_last(10, -1); // 记录每个*数字*上一次出现的位置
vector<int> last(n, -1); // 记录与该*位置*数字相同的上一个位置

// 构造last[]数组
for (int i = 0; i < n; i++)
{
last[i] = digit_last[nums[i]];
digit_last[nums[i]] = i;
}

vector<int> dp(n);
dp[0] = 0;

for (int i = 1; i < n; i++)
{
dp[i] = dp[i - 1] + 1; // 往后走一步

if (last[i] != -1) // 如果可以跳跃到此处
{
dp[i] = min(dp[i], dp[last[i]] + 1); // 2种走法的最小值
}
}

cout << dp[n - 1];
}

测试用例

  1. 1
    2
    3
    4
    5
    6
    7
    # in
    0 1 0 3 4 1
    # out
    2

    # 解释:
    0->1->1
  2. 1
    2
    3
    4
    5
    6
    # in
    0 1 2 3 4 5
    # out
    5
    # 解释:
    0->1->2->3->4->5
  3. 1
    2
    3
    4
    5
    6
    # in
    9 8 9 5 9 2 5 1
    # out
    4
    # 解释:
    9->9->5->5->1
  4. 1
    2
    3
    4
    # in
    <空>
    # out
    0
作者

江风引雨

发布于

2021-10-07

更新于

2022-08-11

许可协议

CC BY 4.0

评论