华为软件算法笔试5-10

校招一对一进阶提高，带领学员斩获大厂实习秋招春招offer！！！

笔试科目一帮助，踢踢饲料沃！！！

订阅专栏，方便查阅，时刻更新各厂软件算法笔试https://blog.nowcoder.net/zhuanlan/0oDWVm

题目1：

1、数据合并

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

1.如果n1=n2，则n1、n2全部出栈，压入新数据m(m=2*n1)。

2.如果n1=n2+...+ny(y的范国为[3,x]) ，则n1、n2...ny全部出栈，压入新数据m(m=2*n1).

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

如: 依次向栈压入6、1、2、3，当压入2时，栈顶至栈底依次为[2、1、6];当压入3时，3=2+1，3、2、1全部出栈，重新入栈整数6(此时n1=3，因此m=2*3=6)，此时栈顶至栈底依次为[6、6];6=6，两个6全部出栈，压入12(此时n1=6，因此m=2*6=12)，最终栈中只剩一个元素12.

向栈中输入一串数字，请输出应用此规则后栈中最终存留的数字

输入

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

输出

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

样例1

输入: 10 20 50 80 1 1

输出: 2 160

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

样例2

输入: 6 4 8 13 9

输出: 9 13 8 4 6

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

vector<int> st;

void solve() {
    if (st.size() > 1 && st.back() == st[st.size() - 2]) {
        int num = st.back();
        st.pop_back();
        st.pop_back();
        st.push_back(2 * num);
        solve();
    } else if (st.size() >= 3) {
        int sum_ = 0;
        for (int i = 0; i < st.size() - 1; ++i) {
            sum_ += st[st.size() - i - 2];
            if (sum_ >= st.back()) {
                if (sum_ == st.back()) {
                    for (int j = 0; j < i+2; ++j) st.pop_back();
                    st.push_back(2 * sum_);
                    solve();
                }
                break;
            }
        }
    }
}

int main() {
    string line;
    getline(cin, line);
    istringstream iss(line);

    int num;
    while (iss >> num) {
        st.push_back(num);
        solve();
    }

    while (!st.empty()) {
        cout << st.back();
        st.pop_back();
        if (!st.empty()) cout << " ";
        else cout << "\n";
    }

    return 0;
}

题目2：

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

1.截取M中的某一段数字x，和数字N进行k运算 (x 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

样例1

输入:

6833023887793076998810418710

2211

-

输出:9988

解释: 通过计算，8877-2211=6666，而9988-2211=7777，因为7777>6666 则目标密码串为9988

样例2

输入:

688467877930769467884187104210

4210

+

输出: 884678

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

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool isAllDigitsSame(long long num) {
    int digit = num % 10;
    while (num) {
        if (num % 10 != digit) return false;
        num /= 10;
    }
    return true;
}

string findMaxSameDigitsSubstr(string M, long long N, char k) {
    int len = M.size();
    string maxSubstr = "-1";
    long long maxResult = -1;
    for (int i = 0; i < len; ++i) {
        for (int j = 3; j <= min(12, len - i); ++j) {  
            if (k == '*' && j > 3) break;  
            string substr = M.substr(i, j);
            long long num = stoll(substr);
            long long result;
            if (k == '+') result = num + N;
            else if (k == '-') result = num - N;
            else result = num * N;
            if (isAllDigitsSame(result) && result > maxResult) {
                maxResult = result;
                maxSubstr = substr;
            }
        }
    }
    return maxSubstr;
}

int main() {
    string M;
    long long N;
    char k;
    cin >> M >> N >> k;
    cout << findMaxSameDigitsSubstr(M, N, k);
    return 0;
}

题目3：

在微服务架构中，一个请求可能会经过若干个服务书点，其所经过的路径，我们称之为请求调用链路。通常，我们会把0些服务治理相关的字段(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，第二行输出0。

样例1

输入：

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

样例2

输入：

3

5

1 2 5

2 3 10

1 3 3

3 1 2

3 2 9

3

输出：

3

7

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <limits>

using namespace std;

const int MAXN = 1e5 + 5;
const int INF = numeric_limits<int>::max();

struct Edge {
    int to, time;
};

int n, m, start;
vector<Edge> adj[MAXN];
map<int, int> sysTime;
int dis[MAXN];

void solve() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    fill(dis, dis + n + 1, INF);
    dis[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        pair<int, int> top = pq.top(); pq.pop();
        int d = top.first, u = top.second;

        if (d != dis[u]) continue;

        for (Edge e : adj[u]) {
            int v = e.to, next_d = d + sysTime[v] + e.time;
            if (dis[v] > next_d) {
                dis[v] = next_d;
                pq.push({next_d, v});
            }
        }
    }
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int s, d, t;
        cin >> s >> d >> t;

        if (s != d) adj[s].push_back({d, t});
        else sysTime[s] = t;
    }

    cin >> start;
    
    solve();

    int cnt = 0, res = 0;
    for (int i = 1; i <= n; ++i) {
        if (dis[i] != INF) {
            cnt++;
            res = max(res, dis[i]);
        }
    }

    cout << cnt << " " << res << "\n";

    return 0;
}