华为 暑期实习 2023.05.10 机试题目与题解

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

1、空栈压数

向一个空栈压入正整数，每当压入一个整数时，执行以下规则(设:栈顶至栈底整数依次编号为\(n_1,n_2,\dots,n_x\)，\(n_1\)为最新压入的整数)

如果\(n_1=n_2\)，则\(n_1\)、\(n_2\)全部出栈，压入新数据\(m(m=2∗n_1)\)。

如果\(n_1=n_2+\dots+n_y\)(\(y\)的范围为\([3,x]\))，则\(n_1,n_2,\dots,n_y\)全部出栈，压入新数据\(m(m=2∗n_1)\)。

如果上述规则都不满足，则不做操作。

如: 依次向栈压入6、1、2、3，当压入2时，栈顶至栈底依次为[2,1,6]; 当压入3时，3=2+1，3、2、1全部出栈，重新入栈整数6，此时栈顶至栈底依次为[6,6]; 6=6，两个6全部出栈，压入12，最终栈中只剩个元素12。 向栈中输入一串数字，请输出应用此规则后栈中最终存留的数字。

输入

使用单个空格隔开的正整数的字符串，如"5 6 7 8"，左边的数字先入栈。

  • 正整数大小为\([1,2^{31}−1]\)。

  • 正整数个数为\([1,1000]\)。

输出

最终栈中存留的元素值，元素值使用单个空格隔开，如"8 7 6 5"，从左至右依次为栈顶至栈底的数字。

样例

1
2
3
4
5
6
7
8
输入：
10 20 50 80 1 1

输出：
2 160

提示：
向栈压入80时，10+20+50=80，数据合并后入栈160，压入两个1时，合并为2，最终栈顶至栈底的数字为2和160。

解答

直接使用数组模拟这个栈的行为。在每次添加前，先判断是否存在一个后缀和（假设下标为\(j\)）恰好为下一个输入值\(x\)，如果存在\(j\)，那么将\(j\)之后的元素全部弹出即可，并将\(2x\)入栈（这里使用的是数组模拟，直接改动最后一个元素的下标即可），否则将\(x\)直接入栈。

代码

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
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll s[1004];
int main(){
    int p=0;
    ll x;
    while(~scanf("%lld",&x)){
        int j;
        ll sum=0;
        for(j=p;j>0;j--){
            sum+=s[j];
            if(sum==x){
                break;
            }
        }
        if(j==0) s[++p]=x;
        else{
            p=j;
            s[p]=x*2;
        }
    }
    for(int i=p;i>0;i--)
        printf("%lld%c",s[i]," \n"[i==1]);
}

2、解密敌占区传出字符串

敌占区地下工作者冒死提供了加密后的字符串，需要你根据预先定好的方式进行解密，得到其中真正的密码。加密后字符串\(M\)是由\(0\sim9\)这10个数字组成的字符串，你手上是一个给定秘钥数字N和一个运算符k(加减乘中的一个)，需要按如下规则找出直正的密码。

截取M中的某一段数字x，和数字N进行k运算（x k N），如果结果是一个所有位数相同的数，则这段数字有可能就是所找密码，例如x为222，N为3，k为，则计算结果是2223=666，满足要求，x是所寻目标密码串之一。

如果存在满足第1点的多种情况，则以计算结果最大的为准;

如果没有找到符合条件的密码串，则输出-1，表示密码串不存在；

M的长度<100，N为正整数，且N<=9999999999，3<=所找密码长度<=12。k为+或-或*中的一种，不考虑除法。

为避免数据过于庞大，约定在乘法场景下，乘数最大为3位数。

输入

提供加密后字符串M，秘钥数字N和运算符k，例如： (加密字符串M)748443217098 (秘钥数字N)123 (运算符k)+

输出

满足计算结果所有位数相同，且计算结果最大的值。 例如:上述例子截取44321，和123相加，则为44321+123=44444，结果所有位的数字字符相同，包括个位数、十位数、百位数、千位数和万位数都是同一个数字字符4，且其值最大。 (目标字符串)44321

样例

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
输入：
6833023887793076998810418710
2211
-

输出：
9988

提示：
通过计算，8877-2211=6666，而9988-2211=7777，因为7777>6666，则目标密码串为9988。


输入：
68846787793076946788418710
4210
+

输出：
884678

提示：
通过计算，符合条件有两个，884678+4210=888888，4678+4210=8888。则目标密码串为884678。


输入：
139804444677899222
2
*

输出：
4444

提示：
作为乘法场景，乘数最大值为3位数，本用例乘数为2。按要求，44442=8888，2222=444，均符合基本条件，从中选择结果最大值，则目标密码串是4444。

解答

枚举\(M\)中所有长度在\(3\)到\(12\)之间的所有子串得到\(x\)，并且使用eval函数方便地计算得到计算结果\(w\)，再将其转换成字符串并判断是否结果为同一个数位即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
m, n, op = input(), input(), input()
ans = '-1'
res = -1
for l in range(3, 13):
    for i in range(0, len(m) - l + 1):
        if m[i] != '0':
            x = m[i:i + l]
            w = eval(x + op + n)
            if w > res and len(set(str(w))) == 1:
                ans, res = x, w
print(ans)

3、最短染色时间

在微服务架构中，一个请求可能会经过若干个服务节点，其所经过的路径，我们称之为请求调用链路。

通常，我们会把一些服务治理相关的字段(例：traceld)，通过请求头的方式在整个链路中透传。

当我们把有特定含义的请求头透传到整个链路，然后链路中每个服务会针对这个请求头做一些特殊的处理，我们把这种行为称之为链路染色。

现给出在某一请求下其经过所有微服务节点的响应时长列表rsTimes，其中rsTimes[i]=(srcSerivce,dstService,rsTime)，其中srcSerivce为调用方服务,dstService为被调用方服务，所有服务名称由一个1到n范围内的整数表示，rsTime为接口调用响应耗时。

如果srcSerivce与dstService相同，则表示系统自身计算耗时。

所以如果服务srcService到dstService的染色总时长为srcService到dstService响应时长+dstService计算耗时，现给出一个调用源头服务名称service，请给出以这个服务作为源头服务发起调用，最终可实现染色的服务个数，并给出这些服务全部完成染色的最短时间。

输入

第一行表示服务节点总数m； 第二行表示服务间调用响应耗时或者服务自身计算耗时rsTmes的长度n； 接下来n行表示具体的服务间调用响应耗时或者服务自身计算耗时； rsTmes[i]，每个数字间用空格隔开，比如10 20 3，则表示10号服务调用20号服务的耗时为3秒； 最后一行表示调用方源服务名称

输出

输出分为两行，第一行输出最终可实现染色的微服务个数，第二行输出这些服务全部完成染色的最短时间。

样例

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
输入：
5
9
1 1 3
1 2 6
1 3 10
3 3 8
2 2 7
2 4 12
2 5 20
5 5 5
4 4 9
1

输出：
5
38

提示：
以服务1为起点计算最长耗时链路，分析可能会存在三条最大耗时链路，分别为1->3以及1->2->5以及1-2-4
第一条路径1->3路径下，总耗时为10(1->3耗时)+8(3自身耗时)=18秒
第二条路径1->2->5路径下，总耗时为6(1->2耗时)+7(2自身耗时)+20(2->5耗时)+5(5自身耗时)=38秒
第三条路径1->2->4路径下，总耗时为6(1->2耗时)+7(2自身耗时)+12(2->4耗时)+9(4自身耗时)=34秒
所以在此场景下，服务5完成染色的最短时间为38秒，为可以染色的所有服务节点的最长时间
最终输出结果分两行输出，最终1 2 3 4 5四个服务节点都可以实现染色，所以最终输出结果如下
5
38

输入：
3
5
1 2 5
2 3 10
1 3 3
3 1 2
3 2 9
3

输出：
3
7

提示

  • 1<=rsTimes.length<=5000
  • 1<=srcSerivce<=100
  • 1<=dstService<=100
  • 1<=rsTime<=100

解答

由于点的数量比较少，可以考虑使用不带堆优化的Dijkstra算法来求解最短路来求解最短路问题。需要注意的地方只有一个：

  • 遇到自环，需要额外用一个变量\(c\)进行存储。当使用某一条边对\(v\)进行松弛时，需要将\(c[v]\)加上这条边的边权中。

最终只需要统计能够可达的节点数以及最大的最短路距离即可。

代码

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
# include <bits/stdc++.h>
using namespace std;
const int N=104;

int d[N],INF=0x3f3f3f3f;
int vis[N],mp[N][N],c[N];
int main(){
    int n,m,x,y,z;
    memset(c,0x3f,sizeof(c));
    memset(d,0x3f,sizeof(d));
    memset(mp,0x3f,sizeof(mp));
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&x,&y,&z);
        if(x==y) c[x]=min(c[x],z);
        else mp[x][y]=min(mp[x][y],z);
    }
    for(int i=1;i<=n;i++)
        if(c[i]==INF) c[i]=0;
    int r;
    scanf("%d",&r);
    d[r]=0;
    for(int _=0;_<n;_++){
        int d_r=INF;
        for(int j=1;j<=n;j++){
            if(!vis[j]&&d[j]<d_r){
                d_r=d[j];r=j;
            }
            vis[r]=1;
            for(int j=1;j<=n;j++)
                d[j]=min(d[j],d[r]+mp[r][j]+c[j]);
        }
    }
    int cnt=0,ans=0;
    for(int i=1;i<=n;i++){
        if(d[i]!=INF){
            ++cnt;
            ans=max(ans,d[i]);
        }
    }
    printf("%d\n%d\n",cnt,ans);
}
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝