2021-10-19-华为机试

第二次参加华为机试：
前两题没有难度，第一题应该是用STL的map，但我时间不够，只写了一部分，最后得分只有300(总分400，第一题的100分没拿到)。
第三题比较有趣：
题目给的背景是堆积木(我改了下背景)，给你一些积木，它们宽和高相同但长度不同(有点类似于积木)，要求把它们堆成地面墙。
从数学角度来说，就是：
给你一些数，它们可以两两相加，也可以单独一个数，要求它们组合成同一个数。
比如：

3 3 6 6 

可以组合成3个6(两个6单独成一个数，两个3相加),也可以组合成2个9(6和3分别相加)。
然后要求最后能组合成相同的多少个数。

思路：(其实简单，相当于智力题，但当时我还是花了点时间才想明白，一开始以为是动态规划，后面以为是搜索，最终才想明白)
最终组合出来的数要么是最大的数，要么是最小的数和最大的数的和(仔细想想堆积木的时候是不是这样？)。
想通了这一点，题目就直接做出来了。

2021-11-13补充：
今天已经入职了，虽然是作为德科的od入职的。
其实之前机试的第一题在机试过后的一天便写出来了，但一直没有时间，那就现在补上吧。
题目大意是：
输入很多个字符串，你要把它们出现的次数记录下来，然后给你一个数字n的时候你要把出现次数前n多的字符串输出。

// URL select
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<typeinfo>

// using namespace std;

std::map <std::string,int> ma;
std::vector<std::pair<std::string,int>> v;

int check(char *input)
{
    if(strlen(input)==2)
    {
        // 10
        if(input[0]=='1'&&input[1]=='0')
            return 10;
        else
            return 0;
    }
    else if(strlen(input)==1 && '0' <= input[0] && input[0] <= '9')
    {
        // 0-9
        return input[0]-'0';
    }
    else
    {
        // URL
        return 0;
    }
    return 0;
}

void search(void)
{
    // int a b;
    std::map<std::string,int>::iterator itmap ; 
    std::vector<std::pair<std::string,int>>::iterator itvec;
    v.clear();
    for(itmap = ma.begin();itmap!=ma.end();itmap++)
    {
        for(itvec=v.end();itvec!=v.begin();itvec--)
        {
            if(itmap->second>itvec->second)
                continue;
            // NOTE: I forgot the problem 
            else if(itmap->second==itvec->second 
                // NOTE:dict order sort ,maybe it is not necessary for <map>
                && strcmp(itmap->first.c_str(),itvec->first.c_str())<0
                )
                continue;
            else
                break;
        }
        if(10>v.size())
        {
            if(itvec==v.end())
                v.push_back(*itmap);
            else
            {
                v.insert(++itvec,*itmap);
            }
        }
        else if(itvec!=v.end())
        {
            v.insert(++itvec,*itmap);
            v.pop_back();
        }
    }
    return ;
}

int main(void)
{
    char input[128];
    int n;
    for(;EOF!=scanf("%s",input);)
    {
        n = check(input);
        if(0==n)
        {
            // URL
            ma[input]++;
        }
        else
        {
            // num
            search();
            std::vector< std::pair< std::string , int > >::iterator itvec;
            for(int i=0;i<n;i++)
            {
                printf("%s",v[i].first.c_str());
                if(i==n-1)
                    printf("\n");
                else
                    printf(",");
            }
        }
    }
    return 0;
}

然后说下面试吧，第一次面试的时候没考虑到异常情况，翻车了，第二次的题目只是一个单纯的栈应用，比逆波兰式还要简单，是leetcode上的，过了。
那就补上第一次面试的代码吧。
题目大意是给你一些数字，把它们头尾拼接，要求输出最后值最大的。
我第一次失误是单纯的认为是字典序，没有考虑到：
3 32 34这样的情况，字典序会输出34323，正确结果应该是34332

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>

// using namespace std;

bool cmp(std::string a,std::string b)
{
    if(a.size()>b.size())
        return !cmp(b,a);
    int i;
    for(i=0;i*a.size()<b.size() && a==b.substr(i*a.size(),a.size());i++);
    if(i*a.size()==b.size())
        return true;
    if(a<b.substr(i*a.size(),a.size()))
        return false;
    if(a>b.substr(i*a.size(),a.size()))
        return true;
    return true;
}

int main(void)
{
    std::vector <std::string> v;
    char s[100];
    while(EOF!=scanf(" %s ",s))
    {
        v.push_back(s);
    }
    std::sort(v.begin(),v.end(),cmp);
    for(std::vector<std::string>::iterator it=v.begin();it!=v.end();it++)
    {
        printf("%s ",(*it).c_str());
    }
    return 0;
}