• 9.20华为机试-后端

    1、丢失报文的位置

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

    输入

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

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

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

    输出

    start end

    说明：start 和 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. import java.util.Scanner;
    2.  
    3. public class test {
    4.     public static void main(String[] args) {
    5.         Scanner scanner = new Scanner(System.in);
    6.         int n = scanner.nextInt();
    7.         int[] a = new int[n];
    8.  
    9.         for (int i = 0; i < n; i++) {
    10.             a[i] = scanner.nextInt();
    11.         }
    12.  
    13.         int x = scanner.nextInt();
    14.         int p = minElementIndex(a);
    15.         int l = -1, r = -1;
    16.  
    17.         for (int i = 0; i < n; i++) {
    18.             int q = (p + i) % n;
    19.             if (a[q] == x) {
    20.                 if (l == -1) {
    21.                     l = q;
    22.                 }
    23.                 r = q;
    24.             }
    25.         }
    26.  
    27.         System.out.println(l + " " + r);
    28.     }
    29.  
    30.     public static int minElementIndex(int[] arr) {
    31.         int minIndex = 0;
    32.         for (int i = 1; i < arr.length; i++) {
    33.             if (arr[i] < arr[minIndex]) {
    34.                 minIndex = i;
    35.             }
    36.         }
    37.         return minIndex;
    38.     }
    39. }
    40.  
    41.

    2、快速传球

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

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

    说明：

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

    输入

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

    输入第一行包含两个用空格分开的整数 m(m∈[1,30]) 和 n(n∈[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列的男同学作为起点，无法实现按规则将球到最后一列男同学手里。

    解答

    解答

    声明一个d[][]去计算和存储到达最后一列男生的步数，d[][]同时也起到了记录该点位是否被访问的作用

    在初始化阶段将第一列男生入队列，实现多元的bfs遍历。

    最终打印最后一列所有男生中d[][]最小的那个值

    代码

    1. import java.util.LinkedList;
    2. import java.util.Queue;
    3. import java.util.Scanner;
    4.  
    5. public class test {
    6.     static final int N = 35;
    7.     static final int[] dx = {0,0,1,-1};
    8.     static final int[] dy = {1,-1,0,0};
    9.     public static void main(String[] args) {
    10.         Scanner in = new Scanner(System.in);
    11.         int n = in.nextInt();
    12.         int m = in.nextInt();
    13.  
    14.         int[][] s = new int[N][N]; // 记录地图
    15.         int[][] d = new int[N][N]; // 计算到达最后一列男生的最小步
    16.  
    17.         for(int i = 1;i<=n;i++){
    18.             for (int j = 1;j<=m;j++ ){
    19.                 s[i][j] = in.nextInt();
    20.                 d[i][j] = -1;
    21.             }
    22.         }
    23.  
    24.         Queue<int []> q = new LinkedList<>();
    25.         for(int i=1;i<=n;i++){ // 初始化第一列，将第一列男生入队列
    26.             if (s[i][1] == 1){
    27.                 d[i][1] = 0;
    28.                 q.offer(new int[]{i,1});
    29.             }
    30.         }
    31.  
    32.         while (!q.isEmpty()){  // bfs搜索
    33.             int[] front = q.poll();
    34.             int sx = front[0];
    35.             int sy = front[1];
    36.  
    37.             for(int i=0;i<4;i++){
    38.                 int x = sx+dx[i];
    39.                 int y = sy+dy[i];
    40.                 if((x < 1) || (y < 1) || (x > n) || (y > m) || d[x][y]!=-1 || s[x][y]==0){
    41.                     continue;
    42.                 }
    43.                 d[x][y] = d[sx][sy]+1;
    44.                 q.offer(new int[]{x,y});
    45.  
    46.             }
    47.         }
    48.  
    49.         int ans = Integer.MAX_VALUE;
    50.         for (int i = 1; i<=n;i++){
    51.             if(s[i][m] == 1){
    52.                 ans = Math.min(ans,d[i][n]);
    53.             }
    54.         }
    55.  
    56.         if(ans == Integer.MAX_VALUE){
    57.             ans = -1;
    58.         }
    59.  
    60.         System.out.println(ans);
    61.  
    62.     }
    63. }

    3、简易计算器

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

    1支持 let 关键字。

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

    例如：

    1
2

    let var1 = 123
let var = 123

    3.变量需要先定义再引用，在表达式中引用未定义的变量，则表达式的结果也是未定义的。

    例如：

    1
2
3
4

    let var1 = 1
let var2 = var1 + 1 // var1是定义的
let var3 = var4 + 1 // var4是未定义的
let var4 = 1

    4.支持整数类型数据，整数数据的输入格式只需要支持十进制，支持负整数，整数取值范围 −2147483648≤≤2147483647。

    例如：

    1
2

    let var3 = 10
let var3 = -10

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

    例如：

    1

    let var4 = 1 + 2 * var3

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

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

    例如：

    1
2

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

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

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

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

    例如：

    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 输出的变量未定义，则打印 
    4. 如果表达式结果发生了整数上溢或者下溢，则对该变量的 out 输出表达式输出  或者 
    5. 如果表达式非法，则打印 

    样例

    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)

输出：


提示：
输出的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

    解答

    大型模拟，定义相关函数，校验各个字符的正确性之后进行相关运算，

    在计算算式的时候采用跨越一个字符的方法遍历，实现计算

    代码

    1. # coding=utf-8
    2. ls = []
    3. mn = -(1<<31)
    4. mx = (1<<31) - 1
    5. inf = 10 ** 50
    6. SYNTAX_ERROR = ""
    7. UNDEFINED = ""
    8. UNDERFLOW = ""
    9. OVERFLOW = ""
    10. mp = {}
    11.  
    12. try:
    13.     while True:
    14.         s = input()
    15.         ls.append(s)
    16. except EOFError:
    17.     pass # ctrl+d结束输入
    18.  
    19. # 变量命名符合通用语言变量规范，必须是以下划线 (_) 或者字母开头，遇到标点符号或者空格符时结束。
    20. def is_variable_name(name):
    21.     if len(name) == 0:
    22.         return False
    23.     if not (name[0].isalpha() or name[0]=='_'):
    24.         return False
    25.     for ch in name[1:]:
    26.         if not (ch.isalpha() or ch.isdigit() or ch == "_"):
    27.             return False
    28.     return True
    29.  
    30.  
    31. # 支持整数类型数据，整数数据的输入格式只需要支持十进制，支持负整数，
    32. def is_int(s):
    33.     try:
    34.         int(s)
    35.         return True
    36.     except ValueError:
    37.         return False
    38.  
    39. # 将字符串转化为数字，如果他本身就是数字，返回这个数字，如果他是字母，则返回字典中他对应的数据
    40. def convert_int(s):
    41.     if is_int(s):
    42.         return int(s)
    43.     elif s in mp.keys():
    44.         return mp[s]
    45.     else:
    46.         return None
    47.  
    48. # 处理let后面的字符串
    49. def parse_let(s):
    50.     s = s.strip()  #消除空白字符
    51.     l,r = s.split('=')
    52.     l,r = l.strip(),r.strip()
    53.     if not is_variable_name(l):
    54.         return SYNTAX_ERROR
    55.     ls = r.split(' ')
    56.     if len(ls) % 2 == 0: # 如果右侧的元素个数为偶数，则说明有问题
    57.         return SYNTAX_ERROR
    58.  
    59.     for i in range(0,len(ls),2): #校验右侧的字符
    60.         if not is_variable_name(ls[i]) and not is_int(ls[i]):
    61.             return SYNTAX_ERROR
    62.  
    63.     for i in range(1,len(ls),2): #校验右侧的运算符
    64.         if not (len(ls[i])==1 and ls[i] in "+-*/"):
    65.             return SYNTAX_ERROR
    66.  
    67.     v = convert_int(ls[0])
    68.     for i in range(1,len(ls),2): # 进行加减运算
    69.         op,w = ls[i],convert_int(ls[i+1])
    70.         if w is None:
    71.             return
    72.         if op == '+':
    73.             v += w
    74.         elif op == '-':
    75.             v -= w
    76.         elif op == '*':
    77.             v *= w
    78.         else:
    79.             v //= w
    80.  
    81.         if v>mx:
    82.             v = inf
    83.             break
    84.         elif v
    85.             v = -inf
    86.             break
    87.  
    88.     mp[l] = v
    89.  
    90. # 输出字符串对应的数字
    91. def parse_out(s):
    92.     s = s[1:-1] # 去除括号
    93.     if s in mp.keys():
    94.         x = mp[s]
    95.         if x>mx:
    96.             return OVERFLOW
    97.         elif x
    98.             return UNDEFINED
    99.         return x
    100.     else:
    101.         return UNDEFINED
    102.  
    103.  
    104. for s in ls:
    105.     if len(s) >= 3 and s[:3] == "let":
    106.         t = parse_let(s[3:])
    107.         if t is not None:
    108.             print(t) #报错处理
    109.  
    110.     elif len(s) >= 3 and s[:3] == "out":
    111.         print(parse_out(s[3:]))
    112.     else:
    113.         print(SYNTAX_ERROR)

  • 相关阅读:
    如何用好Nginx的gzip指令
    DVWA系列4：XSS 跨站脚本攻击之 DOM型 和 反射型
    【ASM】字节码操作 工具类与常用类 InstructionAdapter 介绍
    2022软件测试面试题 最新字节跳动50道真题面试题 刷完已拿下15k 附讲解+答疑
    进程线程深入理解
    基于ARM+FPGA的ISA总线／MMи总线接口转换设计在轨道交通的应用
    01-java入门了解--cmd命令、jdk、java的认识
    LeetCode/LintCode 题解丨一周爆刷字符串：文字并排
    苹果CMS主题 MXonePro二开优化修复开源版影视网站源码
    反射常用方法
  • 原文地址：https://blog.csdn.net/qq_51118755/article/details/133248567