华为 秋招 2023.09.20 编程题目与题解

发表于 分类于 阅读次数： 本文字数： 2k 阅读时长 ≈ 2 分钟

1、丢失报文的位置

某通信系统持续向外发送报文，使用数组\(\texttt{nums}\)保存\(n\)个最近发送的报文，用于在报文未达到对端的情况下重发。报文使用序号\(sn\)表示，序号\(sn\)按照报文发送顺序从小到大排序，相邻报文\(sn\)不完全连续且有可能相同。报文使用循环覆盖的方式保存，即\(\texttt{nums}\)数组填满后，从头开始保存新的报文。假设需要重发序号为\(sn\)的报文。请找出序号为\(sn\)的报文在数组中的开始位置和结束位置。

输入

第一行输入：数组\(\texttt{nums}\)的大小\(n\)，取值范围\([0,10000]\)。

第二行输入：数组中的所有报文的序号\(sn\)，\(sn\)取值范围\([0,100000]\)。

第三行输入：需要重发的报文序号\(sn\)，取值范围\([0,100000]\)。

输出

\(\texttt{start end}\)

说明：\(\texttt{start}\)和\(\texttt{end}\)代表需要重发的报文序号\(sn\)在数组中的起始下标和结束下标。

样例

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
输入：
7
0 0 1 2 2 5 6
1

输出：
2 2

提示：
nums数组大小为7。
保存了7个报文，sn分别是0 0 1 2 2 5 6。
sn为1的报文在数组中仅有1个，下标是2，因此输出2 2。

输入：
7
0 0 1 2 2 5 6
2

输出：
3 4

提示：
nums数组大小为7。
保存了7个报文，sn分别是0 0 1 2 2 5 6。
sn为2的报文在数组中有2个，下标分别是3，4，因此输出3 4。

输入：
7
4 4 7 8 2 3 4
4

输出：
6 1

提示：
nums数组大小为7。
保存了7个报文，sn分别是4 4 7 8 2 3 4。
sn为4的报文在数组中有3个，下标分别是0，1，6，说明数组存在记录满了从头开始记录的情况，输出6 1。

输入：
7
4 4 7 8 2 3 4
6

输出：
-1 -1

提示：
nums数组大小为7。
保存了7个报文，sn分别是4 4 7 8 2 3 4。
数组中不存在sn为6的报文，因此输出-1 -1。

输入：
5
5 5 5 5 5
5

输出：
0 4

提示：
nums数组大小为5
保存了5个报文，sn分别是5 5 5 5 5
数组中所有报文sn都是5，这种情况下认为0是start，4是end，输出0 4。

解答

这题我们只需要找到最小的那个数的下标，然后以它为起点，每个数都遍历一次即可（需要遍历回开头）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
int a[N],n;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int x;
    scanf("%d",&x);
    int p=min_element(a,a+n)-a;
    int l=-1,r=-1;
    for(int i=0;i<n;i++){
        int q=(p+i)%n;
        if(a[q]==x){
            if(l==-1) l=q;
            r=q;
        }
    }
    printf("%d %d\n",l,r);
}

2、快速传球

班级组织传球活动，男女同学随机排成\(m\)行\(n\)列队伍，第一列中的任意一个男同学都可以作为传球的起点，要求最终将球传到最后一列的任意一个男同学手里，求所有能够完成任务的传球路线中的最优路线（传球次数最少的路线）的传球次数。传球规则：

  1. 男同学只能将球传给男同学，不能传给女同学。
  2. 球只能传给身边前后左右相邻的同学。
  3. 如果游戏不能完成，返回\(-1\)。

说明：

  1. 传球次数最少的路线为最优路线。
  2. 最优路线可能不唯一，不同最优路线都为最少传球次数。

输入

班级同学随机排成的\(m\)行\(n\)列队伍，\(1\)代表男同学，\(0\)代表女同学。

输入第一行包含两个用空格分开的整数\(m(m\in [1,30])\)和\(n(n\in [1,30])\)，表示\(m\)行\(n\)列的队伍，接下来是\(m\)行每行包含\(n\)个用空格分开的整数\(1\)或\(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
输入：
4 4
1 1 1 0
1 1 1 0
0 0 1 0
0 1 1 1

输出：
5

提示：
  图一            图二             图三
. . . 0         . . 1 0         1 1 1 0
1 1 . 0         1 . . 0         . . . 0
0 0 . 0         0 0 . 0         0 0 . 0
0 1 . .         0 1 . .         0 1 . .
图一传球路线需要传球6次。
图二传球路线需要传球6次。
图三传球路线需要传球5次，传球次数最少，为最优传球路线。

输入：
3 4
1 0 1 1
1 1 0 0
0 0 1 0

输出：
-1

提示：
选择第1行第1列的男同学作为起点，无法实现按规则将球到最后一列男同学手里。
选择第2行第1列的男同学作为起点，无法实现按规则将球到最后一列男同学手里。

解答

本题是一道多源BFS题目。将第\(1\)列的所有元素为\(1\)的格子作为起点，将最后一列所有的格子都作为终点，最终只需要找一个距离最短的终点即可。

代码

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
#include <bits/stdc++.h>
# define pi pair<int,int>
using namespace std;
typedef long long ll;
const int N=44;

int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int s[N][N],d[N][N];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    memset(d,-1,sizeof(d));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d",&s[i][j]);
            assert(s[i][j]==1||s[i][j]==0);
        }
    queue<pi>q;
    for(int i=1;i<=n;i++){
        if(s[i][1]==1){
            d[i][1]=0;q.push(pi(i,1));
        }
    }
    while(!q.empty()){
        auto [sx,sy]=q.front();q.pop();
        for(int i=0;i<4;i++){
            int x=sx+dx[i],y=sy+dy[i];
            if(x<1||y<1||x>n||y>m||d[x][y]!=-1||s[x][y]==0) continue;
            d[x][y]=d[sx][sy]+1;
            q.push(pi(x,y));
        }
    }
    int ans=1e9;
    for(int i=1;i<=n;i++)
        if(s[i][m]==1) ans=min(ans,d[i][m]);
    if(ans==1e9) ans=-1;
    printf("%d\n",ans);
}

3、简易计算器

设计一款计算器软件，支持以下功能：

  1. 支持let关键字。

  2. 支持通过let赋值表达式定义变量并初始化。

例如：

1
2
let var1 = 123
let var = 123
  1. 变量需要先定义再引用，在表达式中引用未定义的变量，则表达式的结果也是未定义的。

例如：

1
2
3
4
let var1 = 1
let var2 = var1 + 1 // var1是定义的
let var3 = var4 + 1 // var4是未定义的
let var4 = 1
  1. 支持整数类型数据，整数数据的输入格式只需要支持十进制，支持负整数，整数取值范围\(-2147483648 \le x \le 2147483647\)。

例如：

1
2
let var3 = 10
let var3 = -10
  1. 支持整数的加(+)、减(-)、乘(*)、除(/)四则运算，四则运算符之间没有优先级，运算数遵循左结合律，用例不考虑括号。

例如：

1
let var4 = 1 + 2 * var3

上述表达式的计算顺序是，先计算\(1+2\)结果为\(3\)，再将\(3\)乘以var3得到表达式的结果。

  1. 支持通过out函数打印变量的值，函数参数只接受\(1\)个变量，不需要支持表达式。

例如：

1
2
let var4 = 12
out(var4)       // 将会输出12

  1. 表达式中如果引用了未定义的变量，则表达式的结果是未定义的。

  2. 如果计算结果溢出，则表达式结果是溢出。

  3. 变量命名符合通用语言变量规范，必须是以下划线(_)或者字母开头，遇到标点符号或者空格符时结束。

例如：

1
2
3
4
5
6
7
8
let _ = 1       // 变量名_是合法的
let _abc = 1    // 合法
let abc = 1     // 合法
let Abc_1 = 1   // 合法
let abc.x = 1   // 非法
let abc,x = 1   // 非法
let 12abc = 1   // 非法
let abc x = 1   // 非法

输入

  1. 每一行只有一个表达式。
  2. 最多支持\(24\)行输入。
  3. 每个用例输入至少有一个out输出表达式，可以有多个out输出表达式。
  4. 每个变量只会赋值\(1\)次。

例如：

1
2
3
4
let var1 = 1
let var2 = 3
let var3 = var1 + var2
out(var3)

输出

  1. 每遇到\(1\)个out输出表达式，则打印输出变量的值。
  2. 对于out行，只会输出一个out表达式的值。
  3. 如果out输出的变量未定义，则打印<undefined>
  4. 如果表达式结果发生了整数上溢或者下溢，则对该变量的out输出表达式输出<underflow>或者<overflow>
  5. 如果表达式非法，则打印<syntax-error>

样例

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
输入：
let var1 = 1
out(var1)

输出：
1

输入：
out(var)

输出：
<undefined>

提示：
输出的var变量未定义。

输入：
let var1 = 1
let var2 = 3
let var3 = var1 + var2
out(var3)
out(var2)
out(var)
let var4 = -2147483649
let var5 = 2147483648
out(var4)
out(var5)
let x.y = 1

输出：
4
3
<undefined>
<underflow>
<overflow>
<syntax-error>

解答

本题是一道让人难受的字符串大模拟题，为了完成本题，需要编写很多个函数用于各种操作，如：

  • is_variable_name用于判断一个字符串是不是一个合法的变量名，按第9点的要求实现即可。

  • is_int用于判断一个字符串是否为一个合法的十进制整数。

  • convert_int用于将表达式中的变量名或者是数字字符串映射成一个真正的数。

  • parse_let用于解析let命令。首先判断等号左侧是否为一个合法标识符，然后判断右侧是不是一个合法的算术表达式，如果是再做计算，进一步需要判断是否使用了未引用变量。

  • parse_out用于解析out命令。根据对应的变量值打印对应的结果，同时处理各种溢出、未定义问题。

代码

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
ls = []
mn = - (1 << 31)
mx = (1 << 31) - 1
inf = 10 ** 50
SYNTAX_ERROR = "<syntax-error>"
UNDEFINED = "<undefined>"
OVERFLOW = "<overflow>"
UNDERFLOW = "<underflow>"
mp = dict()
try:
    while True:
        s = input()
        ls.append(s)
except EOFError:
    pass


def is_variable_name(name):
    if len(name) == 0:
        return False
    if not (name[0].isalpha() or name[0] == '_'):
        return False
    for ch in name[1:]:
        if not (ch.isalpha() or ch.isdigit() or ch == '_'):
            return False
    return True


def is_int(s):
    try:
        int(s)
        return True
    except ValueError:
        return False


def convert_int(s):
    if is_int(s):
        return int(s)
    elif s in mp.keys():
        return mp[s]
    else:
        return None


def parse_let(s):
    s = s.strip()
    l, r = s.split('=')
    l, r = l.strip(), r.strip()
    if not is_variable_name(l):
        return SYNTAX_ERROR
    ls = r.split(' ')
    if len(ls) % 2 == 0:
        return SYNTAX_ERROR
    for i in range(0, len(ls), 2):
        if not is_int(ls[i]) and not is_variable_name(ls[i]):
            return SYNTAX_ERROR
    for i in range(1, len(ls), 2):
        if not (len(ls[i]) == 1 and ls[i] in "+-*/"):
            return SYNTAX_ERROR
    v = convert_int(ls[0])
    for i in range(1, len(ls), 2):
        op, w = ls[i], convert_int(ls[i + 1])
        if w is None:
            return
        if op == '+':
            v += w
        elif op == '-':
            v -= w
        elif op == '*':
            v *= w
        elif op == '/':
            v //= w
        if v > mx:
            v = inf
            break
        elif v < mn:
            v = -inf
            break
    mp[l] = v


def parse_out(s):
    s = s[1:-1]
    if s in mp.keys():
        x = mp[s]
        if x > mx:
            return OVERFLOW
        elif x < mn:
            return UNDERFLOW
        else:
            return x
    else:
        return UNDEFINED


for s in ls:
    if len(s) >= 3 and s[:3] == "let":
        t = parse_let(s[3:])
        if t is not None:
            print(t)
    elif len(s) >= 3 and s[:3] == "out":
        print(parse_out(s[3:]))
    else:
        print(SYNTAX_ERROR)
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝