华为机试510暑假实习，本次机考题目简单！可以来练练

第一题：空栈压数

题目描述

向一个空栈压入正整数，每当压入一个整数时，执行以下规则(设: 栈顶至栈底整数依次编号为 $n1\mathrm{、}n\mathrm{2...}nxn1、n2...nx$， $n1n1$ 为最新压入的整数)

1. 如果 $n1=n2n1=n2$，则 $n1n1$、$n2n2$ 全部出栈，压入新数据 $m(m=2\ast n1)m(m=2*n1)$

2. 如果 $n1=n2+\mathrm{.}\mathrm{.}\mathrm{.}+nyn1=n2+...+ny$( $yy$ 的范围为$[3,x][3,x]$) ，则 $n1\mathrm{、}n\mathrm{2...}nyn1、n2...ny$全部出栈，压入新数据 $m(m=2\ast n1)m(m=2*n1)$。

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

如: 依次向栈压入 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,2^\{31\}-1]$。

• 正整数个数为$[1,1000][1,1000]$。

输出

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

示例一

输入

10 20 50 80 1 1

输出

2 160

说明

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

第二题：解密敌占区传出字符串

题目描述

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

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

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

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

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

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

输入

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

(加密字符串 M) 748443217098

(秘钥数字 N) 123

(运算符 k) +

输出

满足计算结果所有位数相同，且计算结果最大的值。

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

(目标字符串) 44321

示例一

输入

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。

第三题：最短染色时间

题目描述

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

通常，我们会把一些服务治理相关的字段(例 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<=rsTimes.length<=5000 1<=srcSerivce<=100 1<=dstService<=100 1<=rsTime<=100

输出

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

示例一

输入

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

5

38