讨论/技术交流/阿里巴巴暑期实习算法岗笔试2021年4月7号讨论/
阿里巴巴暑期实习算法岗笔试2021年4月7号讨论

第一次做线上笔试,就凉透了QAQ两道都没做出来。
第一题:数字对应字符1-!,2-@,3-#,4-$,5-%,6-^,7-&,8-*,9-(,0-),可以理解为编码题。字符串表示的数字是十进制,且可能用负号表示负数。
输入n对字符串, 计算每对字符串对应数字之和、之差,输出计算得到的和、差转换字符串的结果。
解题思路:利用哈希表存数字与字符的转换关系,自己写string to number和number to string的子函数。
注意:求和或求差时有可能超过int范围,可能需要用long long,
参考代码(不一定完全对,思路仅供参考):

#include<iostream>
#include<unordered_map>
#include<string>
#include<vector>
using namespace std;

unordered_map <char, int> char2int = {//将字符转成数字
    {')', 0},
    {'!', 1},
    {'@', 2},
    {'#', 3},
    {'$', 4},
    {'%', 5},
    {'^', 6},
    {'&', 7},
    {'*', 8},
    {'(', 9}
};

unordered_map <int, char> int2char = {//将数字转成字符
    {0, ')'},
    {1, '!'},
    {2, '@'},
    {3, '#'},
    {4, '$'},
    {5, '%'},
    {6, '^'},
    {7, '&'},
    {8, '*'},
    {9, '('}
};

int Str2num(string str) {//将字符串转成数字
    bool fuhao = true;
    int number = 0;
    for (int i = 0; i < str.size(); i++) {
        if (i == 0) {
            if (str[0] == '-') {
                fuhao = false;
            }
        }
        number = number * 10 + char2int[str[i]];
    }
    if (!fuhao) number = -number;

    return number;
}

string Num2str(int num) {//将数字转成字符串
    string ans;
    bool fuhao = true;
    if (num < 0) {
        fuhao = false;
        num = -num;
    }
    while (num > 0) {
        int tmp = num % 10;
        ans.push_back(int2char[tmp]);
        num /= 10;
    }
    if (!fuhao) ans.push_back('-');

    return ans;
}

int main() {
    //输入数据
    int num = 0;
    cin >> num;

    string str1, str2;

    while (num > 0) {
        //输入字符串
        cin >> str1 >> str2;
        int number1 = 0;
        int number2 = 0;

        number1 = Str2num(str1);
        number2 = Str2num(str2);

        int sum = 0;
        int cha1 = 0;
        int cha2 = 0;

        sum = number1 + number2;
        cha1 = number1 - number2;
        cha2 = number2 - number1;

        string sum_str;
        string cha1_str;
        string cha2_str;

        sum_str = Num2str(sum);
        cha1_str = Num2str(cha1);
        cha2_str = Num2str(cha2);
        
        //输出
        for (int i = sum_str.size()-1; i >= 0; i--) {
            cout << sum_str[i];
        }
        cout << endl;

        for (int i = cha1_str.size() - 1; i >= 0; i--) {
            cout << cha1_str[i];
        }
        cout << endl;

        for (int i = cha2_str.size() - 1; i >= 0; i--) {
            cout << cha2_str[i];
        }
        cout << endl;

        num--;
    }

    return 0;
}

第二题:求数段最大和
给一组数,限制每个数段最大长度为m,从数组中选择两段不重叠的数段,其和最大,输出该最大和值。
这道题没什么思路,如果用回溯搜索做的话可能会超时,动态规划应该可以,但我还没想出来代码怎么实现。

欢迎大家交流讨论!
欢迎各位大佬批评指正!
欢迎大家一起吐槽(不是)!

第二题据说0分80%,好像是算法竞赛进阶指南里一道原题。。。●‿●

展开全部 2 讨论